A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation
- PDF / 723,711 Bytes
- 40 Pages / 439.37 x 666.142 pts Page_size
- 22 Downloads / 203 Views
A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation Sahar Tahernejad1 · Ted K. Ralphs1 · Scott T. DeNegre2 Received: 25 April 2017 / Accepted: 14 November 2019 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract In this paper, we describe a comprehensive algorithmic framework for solving mixed integer bilevel linear optimization problems (MIBLPs) using a generalized branchand-cut approach. The framework presented merges features from existing algorithms (for both traditional mixed integer linear optimization and MIBLPs) with new techniques to produce a flexible and robust framework capable of solving a wide range of bilevel optimization problems. The framework has been fully implemented in the open-source solver MibS. The paper describes the algorithmic options offered by MibS and presents computational results evaluating the effectiveness of the various options for the solution of a number of classes of bilevel optimization problems from the literature. Keywords Bilevel optimization · Mixed integer optimization · Branch-and-cut algorithm · Open-source solver
1 Introduction This paper describes an algorithmic framework for the solution of mixed integer bilevel linear optimization problems (MIBLPs) and MibS, its open-source software implementation. MIBLPs comprise a difficult class of optimization problems that arise in
Electronic supplementary material The online version of this article (https://doi.org/10.1007/s12532020-00183-6) contains supplementary material, which is available to authorized users.
B
Ted K. Ralphs [email protected] Sahar Tahernejad [email protected] Scott T. DeNegre [email protected]
1
Department of Industrial and System Engineering, Lehigh University, Bethlehem, PA, USA
2
Hospital for Special Surgery, New York, NY, USA
123
S. Tahernejad et al.
applications in which multiple, possibly competing decision-makers (DMs), make a sequence of decisions over time. For an ever-increasing array of such applications, the traditional framework of mathematical optimization, which assumes a single DM with a single objective function making a decision at a single point in time, is inadequate. The motivation for the development of MibS, which was begun a decade ago, is both to serve as an open test bed for new algorithmic ideas and to provide a platform for solution of the wide variety of practical problems of this type currently coming under scientific study. The modeling framework underlying MibS is that of multilevel optimization. Multilevel optimization problems model applications in which decisions are made in a sequence, with decisions made earlier in the sequence affecting the options available later in the sequence. Under the assumption that all DMs are rational and have complete information about their own and each other’s models and input data (there is no stochasticity), we can describe such problems formally using the language of mathematical optimization. To do so, we consider a set
Data Loading...
