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

Abstract:   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.

Biography:   Fengqi You is the Roxanne E. and Michael J. Zak Professor in the Smith School of Chemical and Biomolecular Engineering at Cornell University. Prior to his appointment at Cornell in 2016, he served on the faculty of Northwestern University for five years and was an Argonne Scholar at Argonne National Laboratory from 2009 to 2011. He has published over 100 peer-reviewed journal articles, some of which have been editorially highlighted in Nature, featured on journal covers (e.g. Energy & Environmental Science and ACS Sustainable Chemistry & Engineering), and covered by major media outlets (e.g. The New York Times, BBC, BusinessWeek, and National Geographic). He has received several competitive awards, including the 2011 W. David Smith, Jr. Publication Award from American Institute of Chemical Engineers, the 2013 Northwestern-Argonne Early Career Investigator Award, and a CAREER Award from the National Science Foundation in 2016, as well as a number of best paper awards and “most cited” article awards. He is currently an Associate Editor for Computers & Chemical Engineering. Fengqi earned a B.Eng. from Tsinghua University and received his Ph.D. from Carnegie Mellon University, both in chemical engineering. His research focuses on the development of novel computational models, optimization algorithms, and systems analysis tools for process manufacturing, energy systems and sustainability. More information about his research group can be found from the website: <http://you.cbe.cornell.edu>.