Abstract
Multiparametric programming considers optimization problems where the data are functions of a parameter vector and describes the optimal value and an optimizer as explicit functions of the parameters. In this paper, we consider a linear program where the right-hand side is an affine function of a parameter vector; we propose an algorithm for approximating its solution. Given a full-dimensional simplex in the parameter space and an optimizer for each simplex vertex, the algorithm formulates the linear interpolation of the given solutions as an explicit function of the parameters, giving a primal feasible approximation of an optimizer inside the simplex. If the resulting absolute error in the objective exceeds a prescribed tolerance, then the algorithm subdivides the simplex into smaller simplices where it applies recursively. We propose both a basic version and a refined version of the algorithm. The basic version is polynomial in the output size, provided a polynomial LP solver is used; the refined version may give a smaller output. A global error bound for the optimizer is derived and some computational tests are discussed.
Similar content being viewed by others
References
Morari, M., and Lee, J., Model Predictive Control: Past, Present, and Future, Computers and Chemical Engineering, 23, pp. 667-682, 1999.
Mayne, D., Rawlings, J., Rao, C., and Scokaert, P., Constrained Model Predictive Control: Stability and Optimality, Automatica, 36, pp. 789-814, 2000.
Bemporad, A., Morari, M., Dua, V., and Pistikopoulos, E. N., The Explicit Linear-Quadratic Regulator for Constrained Systems, Automatica, 38, pp. 3-20, 2002.
Tøndel, P., Johansen, T. A., and Bemporad, A., An Algorithm for Multiparametric Quadratic Programming and Explicit MPC Solutions, Proceedings of the 40th IEEE Conference on Decision and Control, Orlando, Florida, pp. 1199-1204, 2001.
Gal, T., Postoptimal Analysis, Parametric Programming, and Related Topics, 2nd Edition, de Gruyter, Berlin, Germany, 1995.
Gal, T., and Nedoma, J., Multiparametric Linear Programming, Management Science, 18, pp. 406-422, 1972.
Bemporad, A., Borrelli, F., and Morari, M., A Geometric Algorithm for Multiparametric Linear Programming, Journal of Optimization Theory and Applications, 118, pp. 515-541, 2003.
Filippi, C., and Romanin-Jacur, G., Multiparametric Demand Linear Transportation Problem, European Journal of Operational Research, 139, pp. 206-219, 2002.
Bemporad, A., and Filippi, C., Suboptimal Explicit Receding-Horizon Control via Approximate Multiparametric Quadratic Programming, Journal of Optimization Theory and Applications, 117, pp. 9-38, 2003.
Fiacco, A. V., Introduction to Sensitivity and Stability Analysis in Nonlinear Programming, Academic Press, London, UK, 1983.
Schrijver, A., Theory of Linear and Integer Programming, Wiley-Interscience, Chichester, UK, 1986.
Murty, K. G., Linear Programming, Wiley-Interscience, New York, NY, 1983.
Walkup, D. W., and Wets, R. J. B., A Lipschitzian Characterization of Convex Polyhedra, Proceedings of the American Mathematical Society, 23, pp. 167-173, 1969.
Robinson, S. M., A Characterization of Stability in Linear Programming, Operations Research, 25, pp. 435-447, 1977.
Avis, D., and Fukuda, K., A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra, Discrete Computational Geometry, 8, pp. 295-313, 1992.
Bemporad, A., Fukuda, K., and Torrisi, F. D., Convexity Recognition of the Union of Polyhedra, Computational Geometry, 18, pp. 141-154, 2001.
Murty, K. G., Computational Complexity of Parametric Linear Programming, Mathematical Programming, 19, pp. 213-219, 1980.
Cormen, T. H., Leiserson, C. E., and Rivest, R. L., Introduction to Algorithms, McGraw-Hill, New York, NY, 1990.
Borrelli, F., Baotic, M., Bemporad, A., and Morari, M., Efficient Online Computation of Constrained Optimal Control Laws, Proceedings of the 40th IEEE Conference on Decision and Control, Orlando, Florida, pp. 1187-1192, 2001.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Filippi, C. An Algorithm for Approximate Multiparametric Linear Programming. Journal of Optimization Theory and Applications 120, 73–95 (2004). https://doi.org/10.1023/B:JOTA.0000012733.44020.54
Issue Date:
DOI: https://doi.org/10.1023/B:JOTA.0000012733.44020.54