Mixed-integer bilevel representability
From MaRDI portal
Publication:2220657
DOI10.1007/S10107-019-01424-WzbMATH Open1480.90176arXiv1808.03865OpenAlexW2970684385WikidataQ127280227 ScholiaQ127280227MaRDI QIDQ2220657FDOQ2220657
Authors: Amitabh Basu, Christopher Thomas Ryan, Sriram Sankaranarayanan 
Publication date: 25 January 2021
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: We study the representability of sets that admit extended formulations using mixed-integer bilevel programs. We show that feasible regions modeled by continuous bilevel constraints (with no integer variables), complementarity constraints, and polyhedral reverse convex constraints are all finite unions of polyhedra. Conversely, any finite union of polyhedra can be represented using any one of these three paradigms. We then prove that the feasible region of bilevel problems with integer constraints exclusively in the upper level is a finite union of sets representable by mixed-integer programs and vice versa. Further, we prove that, up to topological closures, we do not get additional modeling power by allowing integer variables in the lower level as well. To establish the last statement, we prove that the family of sets that are finite unions of mixed-integer representable sets forms an algebra of sets (up to topological closures).
Full work available at URL: https://arxiv.org/abs/1808.03865
Recommendations
Cites Work
- The polynomial hierarchy and a simple model for competitive analysis
- Title not available (Why is that?)
- Links between linear bilevel and mixed 0-1 programming problems
- New necessary optimality conditions for bilevel programs by combining the MPEC and value function approaches
- The Linear Complementarity Problem
- The Theory of Moral Hazard and Unobservable Behaviour: Part I
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Modelling with integer variables
- The Mixed Integer Linear Bilevel Programming Problem
- Discrete linear bilevel programming problem
- Disjunctive cuts for continuous linear bilevel programming
- Parametric integer programming algorithm for bilevel mixed integer programs
- Title not available (Why is that?)
- Solving stochastic and bilevel mixed-integer programs via a generalized value function
- Some properties of convex hulls of integer points contained in general convex sets
- Bilevel programming and the separation problem
- The value function of an integer program
- The value function of a mixed integer program. II
- Enhanced exact algorithms for discrete bilevel linear problems
- The value function of a mixed integer program: I
- Integer Programming
- Some Basis Theorems for Integral Monoids
- Mixed integer linear programming formulation techniques
- A new general-purpose algorithm for mixed-integer bilevel linear programs
- A value-function-based exact approach for the bilevel mixed-integer programming problem
- A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs
- Extended formulations in mixed-integer convex programming
- A closed-form representation of mixed-integer program value functions
- Mixed-integer convex representability
- A study on the computational complexity of the bilevel knapsack problem
- Solving discrete linear bilevel optimization problems using the optimal value reformulation
- The Watermelon Algorithm for The Bilevel Integer Linear Programming Problem
- On the use of intersection cuts for bilevel optimization
- Mixed-integer linear representability, disjunctions, and variable elimination
Cited In (9)
- Representability in mixed integer programming. I: Characterization results
- Mixed-integer linear representability, disjunctions, and Chvátal functions -- modeling implications
- Mixed-integer convex representability
- Mixed-integer convex representability
- A survey on mixed-integer programming techniques in bilevel optimization
- A Gilmore-Gomory construction of integer programming value functions
- Solving a class of two-stage stochastic nonlinear integer programs using value functions
- Modelling with integer variables
- Shapes and recession cones in mixed-integer convex representability
This page was built for publication: Mixed-integer bilevel representability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220657)
