ONR tracking number 21-000000606 - Collaborative Research: Mixed Integer Bilevel Linear Optimization
Abstract
Bilevel optimization is a framework for modeling sequential hierarchical decision processes involving two or more decision-makers wh,o make decisions in turn based on independent objective functions. The case of two decision-makers, referred to as the leader and th,e follower, models the classic Stackleberg game. The leader acts first and the follower responds by solving an optimization problem,led and optimized. Hence, the leader must take the follower s reactions into account when maximizing/minimizing their own benefits/c,osts.In general, bilevel optimization is useful for modeling both adversarial and collaborative decision-making processes,. The former is natural in military contexts, while the latter is often applicable in complex organizations and man-made systems tha,t cannot be fully controlled by a single decision-maker. As modern and future naval systems become more complex, the capability of d,ecentralized design and optimization of such systems becomes even more important. This is what makes the study of bilevel optimizati,on compelling.Bilevel optimization problems have been widely studied over several decades but until relatively recently, most work h,as focused on the case in which the lower-level problem has a compact formulation as a convex optimization problem. In such a case,,the problem has a (compact) strong dual and the bilevel problem can be reformulated to a single level by replacing the lower-level p,roblem with its optimality conditions. If the lower-level problem involves integrality restrictions, then the resulting mixed intege,r bilevel linear problems (MIBLPs) become substantially more difficult to solve.The last decade has seen the introduction of a numbe,r of new algorithms, with those based on the branch-and-cut paradigm emerging as the most efficient in practice. While the branch-an,d-cut paradigm has enabled practical solution of small- to medium-scale instances of MIBLPs, existing solvers have been built by gen,eralizing methodology from the well-studied case of mixed integer linear optimization problems to this more general setting in a rel,atively straightforward way. The relaxation used in the standard branch-and-cut approach relaxes the optimality condition at the low,er level completely, which results in a rather weak bound and this hampers our ability to make good algorithmic choices initially. I,n addition, the valid inequalities that have so far been developed are similarly weak due to the difficulty in exploiting the optima,lity conditions that have been relaxed and this makes it challenging to dynamically strengthen the already weak relaxation. Although, these solvers did result in the first truly practical algorithms for MIBLPs, it has become clear that their scalability is limited,and solution of large-scale problems with any such solver is likely an unattainable goal. To make further progress on solution meth,ods for this important class of problems, we propose to lay the foundations for development of a new generation of algorithms and so,lvers based on stronger relaxations that exploit relaxed versions of the lower-level optimality conditions in order to better navig,ate the trade-off between strength and tractability, as well as a new paradigm for generation of strong valid inequalities that are,{parametric} and exploit those same optimality conditions. We also propose a number of enhancements to the supporting methodology, s,uch as new branching schemes and search procedure purpose-designed to work for this class of problems. All of the,gy will be implemented within the open source solver framework MibS.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 08, 2022
- Source ID
- N000142212676
Entities
People
- Theodore Ralphs
Organizations
- Lehigh University
- Office of Naval Research
- United States Navy