×

zbMATH — the first resource for mathematics

Computational approaches for mixed integer optimal control problems with indicator constraints. (English) Zbl 1405.49002
Summary: Optimal control problems with mixed integer control functions and logical implications, such as a state-dependent restriction on when a control can be chosen (so-called indicator or vanishing constraints) frequently arise in practice. A prominent example is the optimal cruise control of a truck. As every driver knows, admissible gear choices critically depend on the current velocity. A large variety of approaches has been proposed on how to numerically solve this challenging class of control problems. We present a computational study in which the most relevant of them are compared for a reference model problem, based on the same discretization of the differential equations. This comprehends dynamic programming, implicit formulations of the switching decisions, and a number of explicit reformulations, including mathematical programs with vanishing constraints in function spaces. We survey all of these approaches in a general manner, where several formulations have not been reported in the literature before. We apply them to a benchmark truck cruise control problem and discuss advantages and disadvantages with respect to optimality, feasibility, and stability of the algorithmic procedure, as well as computation time.

MSC:
49-04 Software, source code, etc. for problems pertaining to calculus of variations and optimal control
49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C30 Nonlinear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C39 Dynamic programming
90C59 Approximation methods and heuristics in mathematical programming
90C90 Applications of mathematical programming
93B40 Computational methods in systems theory (MSC2010)
49L20 Dynamic programming in optimal control and differential games
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abichandani, P., Benson, H.Y., Kam, M.: Multi-vehicle path coordination under communication constraints. In: 2008 American Control Conference, pp. 650-656. IEEE (2008)
[2] Achtziger, W.; Kanzow, C., Mathematical programs with vanishing constraints: optimality conditions and constraint qualifications, Math. Program. Ser. A, 114, 69-99, (2008) · Zbl 1151.90046
[3] Anitescu, M.; Tseng, P.; Wright, SJ, Elastic-mode algorithms for mathematical programs with equilibrium constraints: global convergence and stationarity properties, Math. Program. Ser. A, 110, 337-371, (2007) · Zbl 1119.90050
[4] Balas, E., Disjunctive programming and a Hierarchy of relaxations for discrete optimization problems, SIAM J. Algebraic Discrete Methods, 6, 466-486, (1985) · Zbl 0592.90070
[5] Baumrucker, BT; Biegler, LT, MPEC Strategies for optimization of a class of hybrid dynamic systems, J. Process Control, 19, 1248-1256, (2009)
[6] Bellman, R., The theory of dynamic programming, Bull. Am. Math. Soc., 60, 503-515, (1954) · Zbl 0057.12503
[7] Bellman, R.E.: Dynamic Programming, 6th edn. University Press, Princeton (1957)
[8] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, JT; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numer., 22, 1-131, (2013) · Zbl 1291.65172
[9] Bertsekas, D.P.: Dynamic Programming and Optimal Control, 3rd edn., vol. 1. Athena Scientific, Belmont (2005)
[10] Bertsekas, D.P.: Dynamic Programming and Optimal Control, 4th edn., vol. 2. Athena Scientific, Belmont (2012)
[11] Bock, HG; Kirches, C.; Meyer, A.; Potschka, A., Numerical solution of optimal control problems with explicit and implicit switches, Optim. Methods Softw., 33, 450-474, (2018) · Zbl 1458.49024
[12] Buchner, A.: Auf Dynamischer Programmierung Basierende Nichtlineare Modellprädiktive Regelung Für LKW. Diploma thesis, Ruprecht-Karls-Universität Heidelberg (2010)
[13] Burger, Michael; Gerdts, Matthias; Göttlich, Simone; Herty, Michael, Dynamic Programming Approach for Discrete-Valued Time Discrete Optimal Control Problems with Dwell Time Constraints, 159-168, (2016), Cham
[14] Burgschweiger, J.; Gnädig, B.; Steinbach, MC, Nonlinear programming techniques for operative planning in large drinking water networks, Open Appl. Math. J., 3, 14-28, (2009) · Zbl 1322.90013
[15] Ceria, S.; Soares, J., Convex programming for disjunctive convex optimization, Math. Program. Ser. A, 86, 595-614, (1999) · Zbl 0954.90049
[16] Claeys, M.; Daafouz, J.; Henrion, D., Modal occupation measures and LMI relaxations for nonlinear switched systems control, Automatica, 64, 143-154, (2016) · Zbl 1329.49051
[17] Facchinei, F.; Jiang, H.; Qi, L., A smoothing method for mathematical programs with equilibrium constraints, Math. Program. Ser. A, 85, 107-134, (1999) · Zbl 0959.65079
[18] Fang, H-R; Leyffer, S.; Munson, TS, A pivoting algorithm for linear programming with linear complementarity constraints, Optim. Methods Softw., 27, 89-114, (2012) · Zbl 1311.90152
[19] Fletcher, R.; Leyffer, S., Solving mathematical programs with complementarity constraints as nonlinear programs, Optim. Methods Softw., 19, 15-40, (2004) · Zbl 1074.90044
[20] Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming. Duxbury Press, USA (2002) · Zbl 0701.90062
[21] Frangioni, A.; Gentile, C., Perspective cuts for a class of convex 0-1 mixed integer programs, Math. Program. Ser. A, 106, 225-236, (2006) · Zbl 1134.90447
[22] Fügenschuh, A.; Herty, M.; Klar, A.; Martin, A., Combinatorial and continuous models for the optimization of traffic flows on networks, SIAM J. Optim., 16, 1155-1176, (2006) · Zbl 1131.90015
[23] Fukushima, M., Qi, L. (eds.): Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods. Kluwer Academic, Dordrecht (1999) · Zbl 0909.00046
[24] Gerdts, M., Solving mixed-integer optimal control problems by branch&bound: a case study from automobile test-driving with gear shift, Optim. Control Appl. Methods, 26, 1-18, (2005)
[25] Gerdts, M., A variable time transformation method for mixed-integer optimal control problems, Optim. Control Appl. Methods, 27, 169-182, (2006)
[26] Gerdts, M., Sager, S.: Mixed-integer DAE optimal control problems: Necessary conditions and bounds. In: Biegler, L., Campbell, S.L., Mehrmann, V. (eds.) Control and Optimization with Differential-Algebraic Constraints, Chapter 9, pp. 189-212. SIAM (2012) · Zbl 1317.90323
[27] Grossmann, IE, Review of nonlinear mixed-integer and disjunctive programming techniques, Optim. Eng., 3, 227-252, (2002) · Zbl 1035.90050
[28] Gugat, M.; Herty, M.; Klar, A.; Leugering, G., Optimal control for traffic flow networks, J. Optim. Theory Appl., 126, 589-616, (2005) · Zbl 1079.49024
[29] Günlük, O.; Linderoth, JT, Perspective reformulations of mixed integer nonlinear programs with indicator variables, Math. Program. B, 124, 183-205, (2010) · Zbl 1229.90106
[30] Hellström, E.; Ivarsson, M.; Aslund, J.; Nielsen, L., Look-ahead control for heavy trucks to minimize trip time and fuel consumption, Control Eng. Pract., 17, 245-254, (2009)
[31] Hoheisel, T.: Mathematical Programs with Vanishing Constraints. PhD thesis, Julius-Maximilians-Universität Würzburg (2009) · Zbl 1162.90560
[32] Jung, M.: Relaxations and Approximations for Mixed-Integer Optimal Control. PhD thesis, University Heidelberg (2013)
[33] Jung, Michael N.; Kirches, Christian; Sager, Sebastian, On Perspective Functions and Vanishing Constraints in Mixed-Integer Nonlinear Optimal Control, 387-417, (2013), Berlin, Heidelberg · Zbl 1320.49011
[34] Jung, MN; Reinelt, G.; Sager, S., The Lagrangian relaxation for the combinatorial integral approximation problem, Optim. Methods Softw., 30, 54-80, (2015) · Zbl 1325.49028
[35] Kawajiri, Y.; Biegler, LT, Nonlinear programming superstructure for optimal dynamic operations of simulated moving bed processes, Ind. Eng. Chem. Res., 45, 8503-8513, (2006)
[36] Kirches, C.: Fast Numerical Methods for Mixed-Integer Nonlinear Model-Predictive Control. Advances in Numerical Mathematics. Springer Vieweg, Wiesbaden (2011) · Zbl 1312.65101
[37] Kirches, C., Bock, H.G., Leyffer, S.: Modeling mixed-integer constrained optimal control problems in AMPL. In: Breitenecker, F., Troch, I. (eds.) Proceedings of MATHMOD 2012, Vienna. ARGESIM Report No. S38 (2012)
[38] Kirches, C., Bock, H.G., Schlöder, J.P., Sager, S.: Mixed-integer NMPC for predictive cruise control of heavy-duty trucks. In: 2013 European Control Conference (ECC), pp. 4118-4123 (2013)
[39] Kirches, C., Lenders, F.: Approximation properties and tight bounds for constrained mixed-integer optimal control. Optimization Online (Technical Report) 5404 (2015)
[40] Kirches, C.; Leyffer, S., TACO: A toolkit for AMPL control optimization, Math. Program. Comput., 5, 227-265, (2013) · Zbl 1302.49043
[41] Kirches, C.; Potschka, A.; Bock, HG; Sager, S., A parametric active-set method for QPs with vanishing constraints arising in a robot motion planning problem, Pac. J. Optim., 9, 275-299, (2013) · Zbl 1270.90042
[42] Kirches, C.; Sager, S.; Bock, HG; Schlöder, JP, Time-optimal control of automobile test drives with gear shifts, Optim. Control Appl. Methods, 31, 137-153, (2010) · Zbl 1204.49033
[43] Kirches, C.; Wirsching, L.; Bock, HG; Schlöder, JP, Efficient direct multiple shooting for nonlinear model predictive control on long horizons, J. Process Control, 22, 540-550, (2012)
[44] Kirchner, C.; Herty, M.; Göttlich, S.; Klar, A., Optimal control for continuous supply network models, Netw. Heterog. Media, 1, 675-688, (2007) · Zbl 1131.90009
[45] Koch, T., Hiller, B., Pfetsch, M.E., Schewe, L. (eds.): Evaluating Gas Network Capacities. SIAM-MOS series on Optimization. SIAM (2015) · Zbl 1322.90007
[46] Leyffer, S.: Complementarity constraints as nonlinear equations: Theory and numerical experiences. In: Dempe, S., Kalashnikov, V (eds.) Optimization with Multivalued Mappings. Springer Optimization and Its Applications, vol. 2, pp. 169-208. Springer, Boston, MA (2006) · Zbl 1190.90240
[47] Leyffer, S., Munson, T.S.: A globally convergent filter method for MPECs. Preprint ANL/MCS-p1457-0907, Mathematics and Computer Science Division, Argonne National Laboratory, 9700 South Cass Avenue, Argonne, IL 60439 USA (2007)
[48] Moehle, N.; Boyd, S., A perspective-based convex relaxation for switched-affine optimal control, Syst. Control Lett., 86, 34-40, (2015) · Zbl 1325.93026
[49] Oldenburg, J.; Marquardt, W., Disjunctive modeling for optimal control of hybrid systems, Comput. Chem. Eng., 32, 2346-2364, (2008)
[50] Palagachev, K.; Gerdts, M., Mathematical programs with blocks of vanishing constraints arising in discretized mixed-integer optimal control problems, Set-valued Var. Anal., 23, 149-167, (2015) · Zbl 1312.49036
[51] Prata, A.; Oldenburg, J.; Kroll, A.; Marquardt, W., Integrated scheduling and dynamic optimization of grade transitions for a continuous polymerization reactor, Comput. Chem. Eng., 32, 463-476, (2008)
[52] Raghunathan, AU; Biegler, LT, Mathematical programs with equilibrium constraints (MPECs) in process engineering, Comput. Chem. Eng., 27, 1381-1392, (2003)
[53] Raghunathan, AU; Diaz, MS; Biegler, LT, An MPEC formulation for dynamic optimization of distillation operations, Comput. Chem. Eng., 28, 2037-2052, (2004)
[54] Ralph, D.; Wright, SJ, Some properties of regularization and penalization schemes for MPECs, Optim. Methods Softw., 19, 527-556, (2004) · Zbl 1097.90054
[55] Sager, S.: Numerical Methods for Mixed-Integer Optimal Control Problems. Der Andere Verlag, Lübeck (2005) · Zbl 1094.65512
[56] Sager, S.: A Benchmark library of mixed-integer optimal control problems. In: Lee, J., Leyffer, S. (eds.) Mixed Integer Nonlinear Programming. The IMA Volumes in Mathematics and Its Applications, vol. 154, pp. 169-208. Springer, New York (2012) · Zbl 1242.90309
[57] Sager, S.; Bock, HG; Diehl, M., The integer approximation error in mixed-integer optimal control, Math. Program. Ser. A, 133, 1-23, (2012) · Zbl 1259.90077
[58] Sager, S.; Claeys, M.; Messine, F., Efficient upper and lower bounds for global mixed-integer optimal control, J. Glob. Optim., 61, 721-743, (2015) · Zbl 1323.49018
[59] Sager, S.; Jung, M.; Kirches, C., Combinatorial integral approximation, Math. Methods Oper. Res., 73, 363-380, (2011) · Zbl 1220.90073
[60] Sager, S.; Bock, HG; Reinelt, G., Direct methods with maximal lower bound for mixed-integer optimal control problems, Math. Program., 118, 109-149, (2009) · Zbl 1160.49032
[61] Sawaya, NW; Grossmann, IE, Computational implementation of non-linear convex hull reformulation, Comput. Chem. Eng., 31, 856-866, (2007)
[62] Scholtes, S., Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM J. Optim., 11, 918-936, (2001) · Zbl 1010.90086
[63] Scholtes, S., Nonconvex structures in nonlinear programming, Oper. Res., 52, 368-383, (2004) · Zbl 1165.90597
[64] Sherali, HD, RLT: A unified approach for discrete and continuous nonconvex optimization, Ann. Oper. Res., 149, 185-193, (2007) · Zbl 1213.90029
[65] Sonntag, C., Stursberg, O., Engell, S.: Dynamic optimization of an industrial evaporator using graph search with embedded nonlinear programming. In: Cassandras, C., et al. (eds.) Analysis and Design of Hybrid System 2006. IPV-IFAC Proceedings Volume, pp. 211-216. Elsevier (2006)
[66] Stein, O.; Oldenburg, J.; Marquardt, W., Continuous reformulations of discrete-continuous optimization problems, Comput. Chem. Eng., 28, 1951-1966, (2004)
[67] Stubbs, RA; Mehrotra, S., Generating convex polynomial inequalities for mixed 0-1 programs, J. Glob. Optim., 24, 311-332, (2002) · Zbl 1046.90053
[68] Terwen, Stephan; Back, Michael; Krebs, Volker, Predictive Powertrain Control for Heavy Duty Trucks, IFAC Proceedings Volumes, 37, 105-110, (2004)
[69] Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57, (2006) · Zbl 1134.90542
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.