Mixed-integer bilevel representability
From MaRDI portal
Publication:2220657
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).
Recommendations
Cites work
- scientific article; zbMATH DE number 35514 (Why is no real title available?)
- scientific article; zbMATH DE number 1234104 (Why is no real title available?)
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 1163110 (Why is no real title available?)
- scientific article; zbMATH DE number 1860211 (Why is no real title available?)
- A closed-form representation of mixed-integer program value functions
- A new general-purpose algorithm for mixed-integer bilevel linear programs
- A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs
- A study on the computational complexity of the bilevel knapsack problem
- A value-function-based exact approach for the bilevel mixed-integer programming problem
- Bilevel programming and the separation problem
- Discrete linear bilevel programming problem
- Disjunctive cuts for continuous linear bilevel programming
- Enhanced exact algorithms for discrete bilevel linear problems
- Extended formulations in mixed-integer convex programming
- Integer Programming
- Links between linear bilevel and mixed 0-1 programming problems
- Mixed integer linear programming formulation techniques
- Mixed-integer convex representability
- Mixed-integer linear representability, disjunctions, and variable elimination
- Modelling with integer variables
- New necessary optimality conditions for bilevel programs by combining the MPEC and value function approaches
- On the use of intersection cuts for bilevel optimization
- Parametric integer programming algorithm for bilevel mixed integer programs
- Solving discrete linear bilevel optimization problems using the optimal value reformulation
- Solving stochastic and bilevel mixed-integer programs via a generalized value function
- Some Basis Theorems for Integral Monoids
- Some properties of convex hulls of integer points contained in general convex sets
- The Linear Complementarity Problem
- The Mixed Integer Linear Bilevel Programming Problem
- The Theory of Moral Hazard and Unobservable Behaviour: Part I
- The Watermelon Algorithm for The Bilevel Integer Linear Programming Problem
- The polynomial hierarchy and a simple model for competitive analysis
- The value function of a mixed integer program. II
- The value function of a mixed integer program: I
- The value function of an integer program
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 Gilmore-Gomory construction of integer programming value functions
- A survey on mixed-integer programming techniques in bilevel optimization
- Modelling with integer variables
- Solving a class of two-stage stochastic nonlinear integer programs using value functions
- 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)
