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 … Read more
In this paper, we consider polytopes P that are contained in the unit hypercube. We provide conditions on the set of 0,1 vectors not contained in P that guarantee that P has a small Chvatal rank. Our conditions are in terms of the subgraph induced by these infeasible 0,1 vertices in the skeleton graph of … Read more
Split cuts are prominent general-purpose cutting planes in integer programming. The split closure of a rational polyhedron is what is obtained after intersecting the half-spaces defined by all the split cuts for the polyhedron. In this paper, we prove that deciding whether the split closure of a rational polytope is empty is NP-hard, even when … Read more
We introduce two-stage distributionally robust disjunctive programs (TSDR-DPs) with disjunctive constraints in both stages and a general ambiguity set for the probability distributions. The TSDR-DPs subsume various classes of two-stage distributionally robust programs where the second stage problems are non-convex programs (such as mixed binary programs, semi-continuous program, nonconvex quadratic programs, separable non-linear programs, etc.). … Read more
We study the following problem: given a rational polytope with Chvatal rank 1, does it contain an integer point? Boyd and Pulleyblank observed that this problem is in the complexity class NP ∩ co-NP, an indication that it is probably not NP-complete. It is open whether there is a polynomial time algorithm to solve the … Read more
Split cuts are arguably the most effective class of cutting planes within a branch-and-cut framework for solving general Mixed-Integer Programs (MIP). Sparsity, on the other hand, is a common characteristic of MIP problems, and it is an important part of why the simplex method works so well inside branch-and-cut. In this work, we evaluate the … Read more
Given a point x inside a polytope P and a direction d, the projection of x along d asks to find the maximum step length t such that x+td is feasible; we say x+td is a pierce point because it belongs to the boundary of P. We address this projection sub-problem with arbitrary interior points … Read more
We consider an extended version of the classical Max-k-Cut problem in which we additionally require that the parts of the graph partition are connected. For this problem we study two alternative mixed-integer linear formulations and review existing as well as develop new branch-and-cut techniques like cuts, branching rules, propagation, primal heuristics, and symmetry breaking. The … Read more
We give a variant of Basu–Hildebrand–Molinaro’s approximation theorem for continuous minimal valid functions for Gomory–Johnson’s infinite group problem by piecewise linear two-slope extreme functions [Minimal cut-generating functions are nearly extreme, IPCO 2016]. Our theorem is for piecewise linear minimal valid functions that have only rational breakpoints (in 1/q Z for some q ∈ N) and … Read more
We present an algorithm for finding the complete Pareto frontier of biobjective integer programming problems. The method is based on the solution of a finite number of integer programs. The feasible sets of the integer programs are built from the original feasible set, by adding cuts that separate efficient solutions. Providing the existence of an … Read more