Approximate Solution of General mp-MILP Problems and Its Application in Urban Traffic Networks

Subject Areas : International Journal of Mathematical Modelling & Computations

Maryam Mahmoudi ^{1 *} , Aghileh Heydari ² , Ali Karimpour ³

1 - Department of Mathematics, Payame Noor University (PNU), P. O. BOX 19395-4697, Tehran, Iran.
2 - Department of Mathematics, Payame Noor University (PNU), P. O. BOX 19395-4697, Tehran, Iran.
3 - Department of Electrical Engineering, Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran.

Received: 2022-01-31 Accepted : 2023-03-01 Published : 2023-03-01

Keywords: Multi-parametric programming (mp-P), Optimization under uncertainty, Mixed-integer programming (MIP), Explicit model predictive control (EMPC), Urban traffic network,

Abstract :

The multi-parametric programming (mp-P) is designed to minimize the number of unnecessary calculations to obtain the optimal solution under uncertainty, and since we widely encounter that kind of problem in mathematical models, its importance is increased. Although mp-P under uncertainty in objective function coefficients (OFC) and right-hand sides of constraints (RHS) has been highly considered and numerous methods have been proposed to solve them so far, uncertainty in the coefficient matrix (i.e., left-hand side (LHS) uncertainty) has been less considered. In this work, a new method for solving multi-parametric mixed integer linear programming (mp-MILP) problems under simultaneous uncertainty OFC, RHS, and LHS is presented. The method consists of two stages which in the first step, using tightening McCormick relaxation, the boundaries of the bilinear terms in the original mp-MILP problem are improved, the approximate model of the problem is obtained based on the improved boundaries of the first stage, and finally, an algorithm is presented to solve these kinds of problems. The efficiency of the proposed algorithm is investigated via different examples and the number of required calculations for solving the problem in different partitioning factors is compared. Also, model predictive control (MPC) using mp-P is designed for an example of an urban traffic network to examine the practical application of the proposed algorithm.

References:

[1] Aboudolas, K., Papageorgiou, M., and Kosmatopoulos, E. (2009). Store-and-forward based methods
for the signal control problem in large-scale congested urban road networks. Transportation Research
REFERENCES 21
Part C: Emerging Technologies, 17(2):163–174.
[2] Aboudolas, K., Papageorgiou, M., Kouvelas, A., and Kosmatopoulos, E. (2010). A rolling-horizon
quadratic-programming approach to the signal control problem in large-scale congested urban road
networks. Transportation Research Part C: Emerging Technologies, 18(5):680 – 694.
[3] Avis, D. and Fukuda, K. (1992). A pivoting algorithm for convex hulls and vertex enumeration of
arrangements and polyhedra. Discrete & Computational Geometry, 8(3):295–313.
[4] Avraamidou, S. and Pistikopoulos, E. N. (2017). A multiparametric mixed-integer bi-level optimization
strategy for supply chain planning under demand uncertainty. IFAC-PapersOnLine, 50(1):10178 –
10183.
[5] Avraamidou, S. and Pistikopoulos, E. N. (2019a). Multi-parametric global optimization approach for
tri-level mixed-integer linear optimization problems. Journal of Global Optimization, 74(3):443–465.
[6] Avraamidou, S. and Pistikopoulos, E. N. (2019b). A multi-parametric optimization approach for bilevel
mixed-integer linear and quadratic programming problems. Computers & Chemical Engineering, 125:98
– 113.
[7] Borrelli, F. (2003). Constrained Optimal Control of Linear and Hybrid Systems. Springer-Verlag Berlin
Heidelberg.
[8] Borrelli, F., Bemporad, A., and M.Morari (2017). Predictive Control for Linear and Hybrid Systems.
Cambridge University Press.
[9] Castro, P. (2015). Tightening piecewise mccormick relaxations for bilinear problems. Computers &
Chemical Engineering, 72:300–311.
[10] Charitopoulos, V. M., Papageorgiou, L. G., and Dua, V. (2018). Multi-parametric mixed integer
linear programming under global uncertainty. Computers & Chemical Engineering, 116:279 – 295.
[11] Dinkelbach, W. (1969). Sensitivittsanalysen und parametrische Programmierung. Springer-Verlag
Berlin Heidelberg.
[12] Dua, V. and Pistikopoulos, E. N. (2000). An algorithm for the solution of multiparametric mixed
integer linear programming problems. Annals of Operations Research, 99:123–139.
[13] Fa´ısca, N. P., Kouramas, K. I., Saraiva, P. M., Rustem, B., and Pistikopoulos, E. N. (2008). A
multi-parametric programming approach for constrained dynamic programming problems. Optimization
Letters, 2:267–280.
[14] Flavell, R. and Salkin, G. R. (1975). An approach to sensitivity analysis. Journal of the Operational
Research Society, 26(4):857–866.
[15] Gounaris, C. E., Misener, R., and Floudas, C. A. (2009). Computational comparison of piecewiselinear
relaxations for pooling problems. Industrial & Engineering Chemistry Research, 48(12):5742–5766.
[16] Hao, Z., Boel, R., and Li, Z. (2018). Model based urban traffic control, part ii: Coordinated model
predictive controllers. Transportation Research Part C: Emerging Technologies, 97:23 – 44.
[17] Henderson, H. and Searle, S. (1981). On deriving the inverse of a sum of matrices. SIAM Review,
23(1):53–60.
[18] Herceg, M., Kvasnica, M., Jones, C., and Morari, M. (2013). Multi-parametric toolbox 3.0. 2013
European Control Conference,, pages 502–510.
[19] Jia, Z. and Ierapetritou, M. (2006). Uncertainty analysis on the righthand side for milp problems.
AIChE Journal, 52:2486 – 2495.
[20] Khalilpour, R. and Karimi, I. (2014). Parametric optimization with uncertainty on the left hand side
of linear programs. Computers & Chemical Engineering, 60:31 – 40.
[21] Le, T., Vu, H. L., Nazarathy, Y., Vo, Q. B., and Hoogendoorn, S. (2013). Linear-quadratic model
predictive control for urban traffic networks. Transportation Research Part C: Emerging Technologies,
36:498 – 512.
[22] Li, Z. and Ierapetritou, G. M. (2007). A new methodology for the general multiparametric
mixed-integer linear programming (milp) problems. Industrial & Engineering Chemistry Research,
46(15):5141–5151.
[23] Li, Z. and Ierapetritou, M. (2008). Process scheduling under uncertainty: Review and challenges.
Computers & Chemical Engineering, 32(4):715 – 727.
[24] L¨ofberg, J. (2004). Yalmip : A toolbox for modeling and optimization in matlab. In In Proceedings
of the CACSD Conference, Taipei, Taiwan.
[25] Lopez, P. A., Behrisch, M., Bieker-Walz, L., Erdmann, J., Fl¨otter¨od, Y.-P., Hilbrich, R., L¨ucken, L.,
Rummel, J., Wagner, P., and Wießner, E. (2018). Microscopic traffic simulation using sumo. In The
21st IEEE International Conference on Intelligent Transportation Systems. IEEE.
[26] Lu, K., Du, P., Cao, J., Zou, Q., He, T., and Huang, W. (2019). A novel traffic signal split approach
based on explicit model predictive control. Mathematics and Computers in Simulation, 155:105 – 114.
[27] McCormick, G. P. (1976). Computability of global solutions to factorable nonconvex programs: Part
i — convex underestimating problems. Mathematical Programming, 10(1):147–175.
[28] Mitsos, A. and Barton, P. I. (2009). Parametric mixed-integer 01 linear programming: The general
case for a single parameter. European Journal of Operational Research, 194(3):663–686.
[29] Oberdieck, R., Diangelakis, N., Papathanasiou, M., Nascu, I., and Pistikopoulos, E. (2016). Pop -
parametric optimization toolbox. Industrial & Engineering Chemistry Research, 55(33):8979–8991.
[30] Oberdieck, R., Diangelakis, N. A., and Pistikopoulos, E. N. (2017). Explicit model predictive control:
A connected-graph approach. Automatica, 76:103 – 112.
[31] Oberdieck, R. and Pistikopoulos, E. N. (2015). Explicit hybrid model-predictive control: The exact
solution. Automatica, 58:152 – 159.
[32] Pistikopoulos, E. N., Dua, V., Bozinis, N. A., Bemporad, A., and Morari, M. (2000). On-line optimization via off-line parametric optimization tools. Computers & Chemical Engineering, 24(2):183 –
188.
[33] Ryu, J., Dua, V., and Pistikopoulos, E. N. (2007). Proactive scheduling under uncertainty: a parametric optimization approach. Industrial & Engineering Chemistry Research, 46(24):8044–8049.
[34] Sakizlis, V., Kakalis, N. M., Dua, V., Perkins, J. D., and Pistikopoulos, E. N. (2004). Design of robust
model-based controllers via parametric programming. Automatica, 40(2):189 – 201.
22 REFERENCES
[35] Winkler, B. (1998). Grbner Bases and Applications. London Mathematical Society Lecture Note
Series. Cambridge University Press.
[36] Wittmann-Hohlbein, M. and Pistikopoulos, E. N. (2012). A two-stage method for the approximate solution of general multiparametric mixed-integer linear programming problems. Industrial & Engineering
Chemistry Research, 51(23):8095–8107.
[37] Wittmann-Hohlbein, M. and Pistikopoulos, E. N. (2014). Approximate solution of mp-milp problems
using piecewise affine relaxation of bilinear terms. Computers & Chemical Engineering, 61:136 – 155