(568d) Solving General Mixed Integer Bilevel Linear Programs (MIBLP): A Decomposition Algorithm

In spite of the fact that a wide range of applications fit the bilevel programming framework, real-world implementations of bilevel programming are still relatively scarce. This is mainly due to the lack of efficient algorithms for solving bilevel programming problems. The complexity of bilevel optimization lies in the property that the constraint region of the upper-level program is partially determined by the solutions to another optimization problem. Therefore, bilevel optimization problems are typically formulated as a lower-level program embedded in an upper-level program. In this work, we propose a novel algorithm for solving mixed-integer bilevel linear programming (MIBLP) problems, which is a class of bilevel programming problems. MIBLP is intrinsically difficult to solve because 1) the bilevel feasible region can be non-convex and disconnected; 2) the supremum (infimum) can be unattainable; and 3) removing the integrality constraints does not necessarily provide a valid relaxation of the original MIBLP problem . Relevant literature also includes studies on mixed-integer bilevel nonlinear programming (MIBNLP) problems.

To the best of our knowledge, existing algorithms for MIBLPs are either subject to several simplifying assumptions or designated to special classes of MIBLP problems. The algorithm proposed in this work is the first practical algorithm that deals with the most general form of MIBLPs. The development of our algorithm involves two major steps: reformulation and decomposition. An iterative solution procedure is proposed that converges to the global optimal solution in finite iterations. Detailed solution procedures are presented for solving two classical literature examples. We propose 50 randomly-generated numerical instances. The computational results show that the proposed algorithm can MIBLP problems within reasonable computational times with up to 100 upper-level continuous variables, 100 upper-level binary variables, 100 lower-level continuous variables, 100 lower-level binary variables, 80 upper-level constraints, and 80 lower-level constraints. To demonstrate a real-world application, we further apply the algorithm to a hierarchical supply chain planning problem, formulated as an MIBLP. A total of 35 case instances are proposed with varying numbers of plants and products. Computational results show that the proposed algorithm can solve these MIBLP problems within reasonable computational times with up to 12 upper-level continuous variables, 12 upper-level binary variables, 144 lower-level continuous variables, 144 lower-level binary variables, 13 upper-level constraints, and 180 lower-level constraints.