In this paper, we study cut generating functions for conic sets. Our first main result shows that if the conic set is bounded, then cut generating functions for integer linear programs can easily be adapted to give the integer hull of the conic integer program. Then we introduce a new class of cut generating functions … Read more
We explore the lifting question in the context of cut-generating functions. Most of the prior literature on lifting for cut-generating functions focuses on which cut-generating functions have the unique lifting property. Here we develop a general theory for under- standing how to do lifting for cut-generating functions which do not have the unique lifting property. … Read more
We consider the problem of generating inequalities that are valid for one-row relaxations of a simplex tableau, with the integrality constraints preserved for one or more non-basic variables. These relaxations are interesting because they can be used to generate cutting planes for general mixed-integer problems. We first consider the case of a single non-basic integer … Read more
We present software for investigations with cut generating functions in the Gomory-Johnson model and extensions, implemented in the computer algebra system SageMath. Citation An extended abstract of 8 pages appeared under the title “Software for cut-generating functions in the Gomory–Johnson model and beyond” in Proc. International Congress on Mathematical Software 2016 Article Download View Equivariant … Read more
We construct a two-sided discontinuous piecewise linear minimal valid function for the 1-row Gomory–Johnson model which is not extreme, but which is not a convex combination of other piecewise linear minimal valid functions. This anomalous behavior results from combining features of Hildebrand’s two-sided discontinuous extreme functions and Basu–Hildebrand–Koeppe’s piecewise linear extreme function with irrational breakpoints. … Read more
The essential structure of the mixed–integer programming formulation for chance–constrained program (CCP) is the intersection of multiple mixing sets with a $0-1$ knapsack. To improve our computational capacity on CCP, an underlying substructure, the (single) mixing set with a $0-1$ knapsack, has received substantial attentions recently. In this study, we consider a CCP problem with … Read more
Using a metaprogramming technique and semialgebraic computations, we provide computer-based proofs for old and new cutting-plane theorems in Gomory–Johnson’s model of cut generating functions. Citation to be presented at ISCO 2016 Article Download View Toward computer-assisted discovery and automated proofs of cutting plane theorems
We consider the maximum k-cut problem that consists in partitioning the vertex set of a graph into k subsets such that the sum of the weights of edges joining vertices in different subsets is maximized. We focus on identifying effective classes of inequalities to tighten the semidefinite programming relaxation. We carry out an experimental study … Read more
A chance constrained optimization problem over a finite distribution involves a set of scenario constraints from which a small subset can be violated. We consider the setting where all scenario constraints are mixed-integer convex. Existing works typically consider a mixed integer nonlinear programming (MINLP) formulation of this problem by introducing binary variables to indicate which … Read more
We study the polyhedral structure of the static probabilistic lot-sizing (SPLS) problem and propose facets that subsume existing inequalities for this problem. In addition, the proposed inequalities give the convex hull description of a related stochastic lot-sizing problem. We propose a new compact formulation that exploits the simple recourse structure, which can be applied to … Read more