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 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
We present software for investigations with cut generating functions in the Gomory-Johnson model and extensions, implemented in the computer algebra system SageMath. CitationAn 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 2016ArticleDownload View PDF
In this paper we analyze general two-term disjunctions on a regular cone $\K$ and derive a general form for a family of convex inequalities which are valid for the resulting nonconvex sets. Under mild technical assumptions, these inequalities collectively describe the closed convex hulls of these disjunctions, and if additional conditions are satisfied, a single … Read more
In this paper, we present an analysis of the strength of sparse cutting-planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is non-negative. Given a MILP instance of one of these three … Read more
In this paper, we study a two-level lot-sizing problem with supplier selection (LSS). This NP-hard problem arises in different production planning and supply chain management applications. We first present a dynamic programming algorithm for LSS that is polynomial when the number of plants is fixed. We use this algorithm to describe the convex hull of … Read more
Optimization problems over permutation matrices appear widely in facility layout, chip design, scheduling, pattern recognition, computer vision, graph matching, etc. Since this problem is NP-hard due to the combinatorial nature of permutation matrices, we relax the variable to be the more tractable doubly stochastic matrices and add an $L_p$-norm ($0 < p < 1$) regularization ... Read more
As the modern transmission control and relay technologies evolve, transmission line switching has become an important option in power system operators’ toolkits to reduce operational cost and improve system reliability. Most recent research has relied on the DC approximation of the power flow model in the optimal transmission switching problem. However, it is known that … Read more
In this paper, we analyze the strength of split cuts in a lift-and-project framework. We first observe that the Lovasz-Schrijver and Sherali-Adams lift-and-project operator hierarchies can be viewed as applying specific 0-1 split cuts to an appropriate extended formulation and demonstrate how to strengthen these hierarchies using additional split cuts. More precisely, we define a … Read more
We study two-stage stochastic mixed integer programs (TSS-MIPs) with integer variables in the second stage. We show that under suitable conditions, the second stage MIPs can be convexified by adding parametric cuts a priori. As special cases, we extend the results of Miller and Wolsey (Math Program 98(1):73-88, 2003) to TSS-MIPs. Furthermore, we consider second … Read more