A branch-and-bound method for discretely-constrained mathematical programs with equilibrium constraints

• DOI: 10.1007/s10479-012-1191-5
• Publication Date: 2012-07-27T17:47:40Z
• Authors: Yohan Shim; Marte Fodstad; Steven A. Gabriel; Asgeir Tomasgard
• Keywords: Benders' decomposition; Theory of computation; Convexity; Branch and bound; Branch and cut

We present a branch-and-bound algorithm for discretely-constrained mathematical programs with equilibrium constraints (DC-MPEC). This is a class of bilevel programs with an integer program in the upper-level and a complementarity problem in the lower-level. The algorithm builds on the work by Gabriel et al. (Journal of the Operational Research Society 61(9):1404–1419, 2010) and uses Benders decomposition to form a master problem and a subproblem. The new dynamic partition scheme that we present ensures that the algorithm converges to the global optimum. Partitioning is done to overcome the non-convexity of the Benders subproblem. In addition Lagrangean relaxation provides bounds that enable fathoming in the branching tree and warm-starting the Benders algorithm. Numerical tests show significantly reduced solution times compared to the original algorithm. When the lower level problem is stochastic our algorithm can easily be further decomposed using scenario decomposition. This is demonstrated on a realistic case.