CAM Colloquium - Fengqi You: Projection-based Reformulation and Decomposition Algorithm for Mixed-Integer Bilevel Linear Programs

Mixed-Integer Bilevel Linear Program (MIBLP) is a class of most challenging optimization problems that has a bilevel optimization structure and include integer variables in both upper and lower optimization problems. MIBLP stems from hierarchical decision-making processes and the Stackelberg game, and finds applications in various areas, such as energy systems design, transportation planning, robust optimization, revenue management, manufacturing systems operations, etc. Despite the growing applications of MIBLPs, there is no efficient solution algorithm for large-scale MIBLPs; existing MIBLP algorithms are either subject to simplifying assumptions on the integrity of parameters/variables or restrictions on the presence of upper-level connecting constraints. The complexity of bilevel optimization lies in the property that constraint region of the upper-level program is partially determined by the solutions to a lower-level program. MIBLP problems further complicate the matter because 1) the bilevel feasible region can be nonconvex and disconnected; 2) removing the integrality constraints does not necessarily provide a valid relaxation of the original MIBLP problem; 3) lower-level optimal solutions are not always feasible to the original MIBLP when upper-level connecting constraints are present (i.e., issue of relatively complete response). All these challenges make MIBLPs much more difficult to solve than single-level mixed-integer linear programs, which are already NP-hard problems. In this talk, we will explore recent theoretical, algorithmic and computational results on global optimization of MIBLPs. I’ll specifically introduce an efficient MIBLP algorithm that deals with the least restricted form of MIBLPs. The proposed algorithm requires only two basic assumptions: 1) the MIBLP constraint region is a nonempty compact set; and 2) the inducible region is nonempty. To address this class of MIBLPs, we first reformulate the original MIBLP into an equivalent Generalized Semi-Infinite Program, which is further reformulated into an equivalent single-level optimization problem. The issue of relatively complete response is tackled using a projection-based formulation with Fourier-Motzkin elimination and disjunctive programming. Based on this single-level reformulation, a decomposition-based optimization algorithm is developed that iteratively solves a master problem and two subproblems until a solution within ε-global optimality is obtained within finite iterations. The master problem provides a valid lower bound, while two subproblems are used to provide a valid upper bound or to test the feasibility of lower-level solutions. A KKT-condition-based cut is generated using the solutions to the subproblems and added to the master problem at the end of each iteration, so that non-decreasing lower bounds can be obtained successively. Implementation of the algorithm is described along with applications on two examples adapted from the literature and a number of randomly generated numerical examples.