On the Polyhedrality of the Chvatal-Gomory Closure

In this paper, we provide an equivalent condition for the Chvatal-Gomory (CG) closure of a closed convex set to be finitely-generated. Using this result, we are able to prove that, for any closed convex set that can be written as the Minkowski sum of a compact convex set and a closed convex cone, its CG … Read more

Multi-cover Inequalities for Totally-Ordered Multiple Knapsack Sets

We propose a method to generate cutting-planes from multiple covers of knapsack constraints. The covers may come from different knapsack inequalities if the weights in the inequalities form a totally-ordered set. Thus, we introduce and study the structure of a totally-ordered multiple knapsack set. The valid multi-cover inequalities we derive for its convex hull have … Read more

On Convex Lower-Level Black-Box Constraints in Bilevel Optimization with an Application to Gas Market Models with Chance Constraints

Bilevel optimization is an increasingly important tool to model hierarchical decision making. However, the ability of modeling such settings makes bilevel problems hard to solve in theory and practice. In this paper, we add on the general difficulty of this class of problems by further incorporating convex black-box constraints in the lower level. For this … Read more

Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs

Cutting planes are a key ingredient to successfully solve mixed-integer linear programs. For specific problems, their strength is often theoretically assessed by showing that they are facet-defining for the corresponding mixed-integer hull. In this paper we experimentally investigate the dimensions of faces induced by general-purpose cutting planes generated by a state-of-the-art solver. Therefore, we relate … Read more

On the Complexity of Inverse Mixed Integer Linear Optimization

Inverse optimization is the problem of determining the values of missing input parameters that are closest to given estimates and that will make a given solution optimal. This study is concerned with the relationship of a particular inverse mixed integer linear optimization problem (MILPs) to both the original problem and the separation problem associated with … Read more

Valid Inequalities for Mixed Integer Bilevel Linear Optimization Problems

Despite the success of branch-and-cut methods for solving mixed integer bilevel linear optimization problems (MIBLPs) in practice, there have remained some gaps in the theory surrounding these methods. In this paper, we take a first step towards laying out a theory of valid inequalities and cutting-plane methods for MIBLPs that parallels the existing theory for … Read more

SDP-based bounds for the Quadratic Cycle Cover Problem via cutting plane augmented Lagrangian methods and reinforcement learning

We study the Quadratic Cycle Cover Problem (QCCP), which aims to find a node-disjoint cycle cover in a directed graph with minimum interaction cost between successive arcs. We derive several semidefinite programming (SDP) relaxations and use facial reduction to make these strictly feasible. We investigate a nontrivial relationship between the transformation matrix used in the … Read more

Inverse Mixed Integer Optimization: Polyhedral Insights and Trust Region Methods

Inverse optimization – determining parameters of an optimization problem that render a given solution optimal – has received increasing attention in recent years. While significant inverse optimization literature exists for convex optimization problems, there have been few advances for discrete problems, despite the ubiquity of applications that fundamentally rely on discrete decision-making. In this paper, … Read more

On a generalization of the Chvatal-Gomory closure

Many practical integer programming problems involve variables with one or two-sided bounds. Dunkel and Schulz (2012) considered a strengthened version of Chvatal-Gomory (CG) inequalities that use 0-1 bounds on variables, and showed that the set of points in a rational polytope that satisfy all these strengthened inequalities is a polytope. Recently, we generalized this result … Read more

On the Complexity of Branching Proofs

We consider the task of proving integer infeasibility of a bounded convex set K in R^n using a general branching proof system. In a general branching proof, one constructs a branching tree by adding an integer disjunction at each node, such that the leaves of the tree correspond to empty sets (i.e., K together with … Read more