A Two-Stage Method for the Approximate Solution of General Multiparametric Mixed-Integer Linear Programming Problems

In this work, we focus on the approximate solution of multiparametric mixed-integer linear programming (mp-MILP) problems involving uncertainty in the objective function coefficients and in the entries of the constraint matrices and vectors. A two-stage algorithmic procedure is proposed. In the first stage, the model is partially immunized against uncertainty using the worst-case oriented approach which leads to a partially robust mp-MILP model, whereas in the second stay explicit solutions of the robust model are derived by applying a suitable multiparametric programming algorithm for mp-MILP problems. Computational studies are presented, demonstrating that the proposed two-stage robust optimization/multiparametric programming procedure is computationally efficient and that it provides an upper bound on the overall solution of the general mp-MILP problem.