Enhanced Cutting Plane Techniques for Bi-Level Optimization Algorithms

Abstract : Bi-level optimization algorithms have been developed for use in a variety of problems, including network design and defense systems and optimization under uncertainty, and network interdiction applications. These algorithms often employ a technique that divides the decision-making process into a first-stage master problem wherein one set of decisions are determined, after which a set of separable second-stage problems are based on the first-stage decisions. The master problem determines an optimistic assessment of the costs incurred in the second stage; this assessment is then refined by a set of linear functions called cutting planes, which provide cause-and-effect relationships between the first- and second-stage decisions. However, these cutting planes are often ineffective in practical problems. The improvement of these cutting planes is the subject of this proposal. The investigator encountered a surprising feature of some bi-level problems, in which an exponential number of cutting planes may need to be generated at each stage. By reformulating the first-stage problem using slightly more variables and constraints, it was possible to capture all of these cutting planes with a single inequality in the new variable space. Problems that were thought to be impossible to optimality are shown to in fact be solvable within reasonable computational limits.