We prove that any minimal valid function for the k-dimensional infinite group relaxation that is piecewise linear with at most k+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k=1, and Cornu\’ejols and Molinaro for k=2. Article Download View A … Read more
This paper introduces a fundamental family of unbounded convex sets that arises in the context of non-convex mixed-integer quadratic programming. It is shown that any mixed-integer quadratic program with linear constraints can be reduced to the minimisation of a linear function over a set in the family. Some fundamental properties of the convex sets are … Read more
We are given a digraph G = (N, A), where each arc is colored with one among k given colors. We look for a spanning arborescence T of G rooted at a given node and having minimum changeover cost. We call this the Minimum Changeover Cost Arborescence problem. To the authors’ knowledge, it is a … Read more
Valid inequalities or cutting planes for (mixed-) integer programming problems are an essential theoretical tool for studying combinatorial properties of polyhedra. They are also of utmost importance for solving optimization problems in practice; in fact any modern solver relies on several families of cutting planes. The Chvátal-Gomory procedure, one such approach, has a peculiarity that … Read more
Strong branching is an effective branching technique that can significantly reduce the size of the branch-and-bound tree for solving Mixed Integer Nonlinear Programming (MINLP) problems. The focus of this paper is to demonstrate how to effectively use discarded information from strong branching to strengthen relaxations of MINLP problems. Valid inequalities such as branching-based linearizations, various … Read more
Large-sized extended formulations have the potential for providing high-quality bounds on some combinatorial optimization problems where the natural formulations perform poorly. This chapter discusses the use of some families of cuts that have been recently applied on extended formulations that are obtained by the discretization of the continuous variables occurring in the natural formulation of … Read more
There are $n$ individual assets and $k$ of them are to be sold over two stages. The first-stage prices are known and the second-stage prices have a known distribution. The sell or hold problem (SHP) is to determine which assets are to be sold at each stage to maximize the total expected revenue. We show … Read more
We consider a probabilistic set covering problem where there is uncertainty regarding whether a selected set can cover an item, and the objective is to determine a minimum-cost combination of sets so that each item is covered with a pre-specified probability. To date, literature on this problem has focused on the special case in which … Read more
We study a mixed integer linear program with $m$ integer variables and $k$ non-negative continuous variables in the form of the relaxation of the corner polyhedron that was introduced by Andersen, Louveaux, Weismantel and Wolsey [\emph{Inequalities from two rows of a simplex tableau}, Proc.\ IPCO 2007, LNCS, vol.~4513, Springer, pp.~1–15]. We describe the facets of … Read more
In 1996, Laurent and Poljak introduced an extremely general class of cutting planes for the max-cut problem, called gap inequalities. We prove several results about them, including the following: (i) there must exist non-dominated gap inequalities with gap larger than 1, unless NP = co-NP; (ii) there must exist non-dominated gap inequalities with exponentially large … Read more