ONR tracking number 21-000000606 - Collaborative Research: Mixed Integer Bilevel Linear Optimization
Abstract
Project SummaryBilevel optimization is a framework for modeling sequential hierarchical decision processes involving two or more dec,ision-makers who make decisions in turn based on independent objective functions. The case of two decision-makers, referred to as th,e leader and the follower, models the classic Stackelberg game. The leader acts first and the follower responds by solving an optimi,zation problem parameterized on the leader s action. Importantly, the follower s response affects the leader s objective, whose perf,ormance is modeled and optimized. Hence, the leader must take the follower s reactions into account when maximizing/minimizing their, own benefits/costs.In general, bilevel optimization is useful for modeling both adversarial and collaborative decision-making proce,sses. The former is natural in military contexts, while the latter is often applicable in complex organizations and man-made systems, that cannot be fully controlled by a single decision-maker. As modern and future naval systems become more complex, the capability,of decentralized design and optimization of such systems becomes even more important. This is what makes the study of bilevel optimi,zation compelling. Bilevel optimization problems have been widely studied over several decades but until relatively recently, most w,ork has focused on the case in which the lower-level problem has a compact formulation as a convex optimization problem. In such a c,ase, the problem has a (compact) strong dual and the bilevel problem can be reformulated to a single level by replacing the lower-le,vel problem with its optimality conditions. If the lower-level problem involves integrality restrictions, then the resulting mixed i,nteger bilevel linear problems (MIBLPs) become substantially more difficult to solve.The,number of new algorithms, with those based on the branch-and-cut paradigm emerging as the most efficient in practice. While the bran,ch-and-cut paradigmhas enabled practical solution of small- to medium-scale instances of MIBLPs, existing solvers have been built by, generalizing methodology from the well-studied case of mixed integer linear optimization problems to this more general setting in a, relatively straightforward way. The relaxation used in the standard branch-and-cut approach relaxes the optimality condition at the, lower level completely, which results in a rather weak bound and this hampers our ability to make good algorithmic choices initiall,y. In addition,the valid inequalities that have so far been developed are similarly weak due to the difficulty in exploiting the opt,imality conditions that have been relaxed and this makes it challenging to dynamically strengthen the already weak relaxation. Altho,ugh these solvers did result in the first truly practical algorithms for MIBLPs, it has become clear that their scalability is limit,ed and solution of large-scale problems with any such solver is likely an unattainable goal.Tomake 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 naviga,te the trade-off between strength and tractability, as well as anew paradigm for generation of strong valid inequalities that are pa,as new branching schemes and search procedure purpose-designed to work for this class of problems. All of the proposed methodology w,ill be implemented within theopen-source solver framework MibS.Approved for public release
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 08, 2022
- Source ID
- N000142212678
Entities
People
- Oleg A. Prokopyev
Organizations
- Office of Naval Research
- United States Navy
- University of Pittsburgh