Mixed-integer bilevel representability

DOI10.1007/S10107-019-01424-WMaRDI QIDQ2220657zbMATH OpenOpenAlexWikidataFDO

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)

Full work available at URL https://arxiv.org/abs/1808.03865

zbMATH Keywords

bilevel programmingrepresentabilityStackelberg games

Mathematics Subject Classification ID

Mixed integer programming (90C11) Mathematical programming (90C99) 2-person games (91A05)

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).

Review text

The authors study mixed integer bilevel linear (MIBL) programs. In particular, they show that the sets defined by continuous bilevel constraints, linear complementarity constraints and polyhedral reverse convex constraints are all equivalent and they are all equal to the family of finite unions of polyhedra as well as every finite union of polyhedra can be described in one of those three ways -- another result of the paper is that if the integer variables are present only in the upper level of a MIBL program, then its feasible region is equivalent to a finite union of sets defined by mixed integer linear (MIL) programs. The last main result of the paper is that the family of finite unions of sets defined by MIL programs is an algebra of sets. This allows to prove that using integer variables also in the lower level of MIBL does not bring any additional modelling power, up to topological closures.

Recommendations

• Representability in mixed integer programming. I: Characterization results
• Mixed-integer convex representability
• Mixed-integer convex representability
• Modelling with integer variables
• The Mixed Integer Linear Bilevel Programming Problem

Cites work

• 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
• 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?)
• 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 polynomial hierarchy and a simple model for competitive analysis
• The Theory of Moral Hazard and Unobservable Behaviour: Part I
• 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
• The Watermelon Algorithm for The Bilevel Integer Linear Programming Problem

Cited in

(10)

• Representability in mixed integer programming. I: Characterization results
• A Gilmore-Gomory construction of integer programming value functions
• Mixed-integer convex representability
• Modelling with integer variables
• Mixed-integer convex representability
• Mixed-integer linear representability, disjunctions, and Chvátal functions -- modeling implications
• A survey on mixed-integer programming techniques in bilevel optimization
• Shapes and recession cones in mixed-integer convex representability
• Solving a class of two-stage stochastic nonlinear integer programs using value functions
• Complexity of bilevel linear programming with a single upper-level variable

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)