10.30495/ijm2c.2023.1951076.1244

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

PDF
  • Maryam Mahmoudi*1,
  • Aghileh Heydari1,
  • Ali Karimpour2,
  1. Department of Mathematics, Payame Noor University (PNU), P. O. BOX 19395-4697, Tehran, Iran.
  2. Department of Electrical Engineering, Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran.

Received: 31-01-2022

Accepted: 01-03-2023

Published in Issue 01-03-2023

Copyright (c) 2024 International Journal of Mathematical Modeling & Computations

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

Mahmoudi, M., Heydari, A., & Karimpour, A. (2023). Approximate Solution of General mp-MILP Problems and Its Application in Urban Traffic Networks. International Journal of Mathematical Modelling & Computations, 13(1), 0-0. https://doi.org/10.30495/ijm2c.2023.1951076.1244
Crossref
Scopus
Google Scholar
Europe PMC

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.
PDF

References

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

Most read articles by the same author(s)