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

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.