Bilevel optimization is a framework to model a hierarchical decision system where two decision makers interact in a sequential way when they pursue their own objectives. It is currently applied to study and support many real decision-making problems where centralized control is not applicable, including those arising from government policy design, economics, social science, defense and security. However, it is computationally challenging to make such decisions. In particular, bilevel optimization with discrete decisions in the lower level remains computationally unsolved. This research will produce a novel and efficient algorithm paradigm to compute bilevel discrete optimization problems, including unstructured formulations and popular interdiction models. Various analytical insights and algorithm enhancements will be investigated and developed. Results will be further incorporated into publicly available and professional optimization solvers to provide decision support to users in government agencies, military forces and other societal organizations with different analytical backgrounds. Teaching and learning materials will be designed to disseminate research results. Graduate and undergraduate students will benefit through lectures and research experiences. Therefore, broad and positive impacts will be produced in the U.S. government policy making, economy, education, and defense and security areas.
The solution scheme from this research will include non-traditional reformulations of bilevel mixed integer program (MIP) that yield relaxations theoretically stronger than existing ones. It will also involve a new decomposition framework that progressively explores solution space and strengthens bounds. Advanced relaxation techniques, branch-and-bound strategies and strong valid inequalities, along with integration of fast heuristics and popular optimization algorithms, will be studied, developed and evaluated. If successful, the intellectual merit of this research will include: (i) the first general, complete and empirically verified algorithmic procedure with a comprehensive analysis will become available to compute bilevel MIP problems; (ii) the solution capability will be substantially improved to solve instances from practice; (iii) integration methods with other efficient computing approaches will be developed and demonstrated to address different variants of bilevel MIP and large-scale applications; (iv) a new algorithm philosophy will enrich existing literature on optimization and algorithm design; (v) modeling and computing packages will be implemented and provided for public access and rapid prototyping.
