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. ArticleDownload View PDF
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
This paper presents some strong valid inequalities for the Maximum Common Induced Subgraph Problem (MCIS) and the proofs that the inequalities are facet-defining under certain conditions. The MCIS is an NP-hard problem and, therefore, no polynomial time algorithm is known to solve it. In this context, the study of its polytope can help in the … 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
In this paper, we examine a mixed integer linear programming (MIP) reformulation for mixed integer bilinear problems where each bilinear term involves the product of a nonnegative integer variable and a nonnegative continuous variable. This reformulation is obtained by first replacing a general integer variable with its binary expansion and then using McCormick envelopes to … Read more
We present a new approach for exactly solving chance-constrained mathematical programs having discrete distributions with nite support and random polyhedral constraints. Such problems have been notoriously difficult to solve due to nonconvexity of the feasible region, and most available methods are only able to nd provably good solutions in certain very special cases. Our approach … Read more
In many telecommunication network architectures a given set of client nodes must be served by different kinds of facility, which provide di fferent services and have diff erent capabilities. Such facilities must be located and dimensioned in the design phase. We tackle a particular location problem in which two sets of facilities, mid level and high level, … Read more
A cutting-plane procedure for integer programming (IP) problems usually involves invoking a black-box procedure (such as the Gomory-Chvatal (GC) procedure) to compute a cutting-plane. In this paper, we describe an alternative paradigm of using the same cutting-plane black-box. This involves two steps. In the first step, we design an inequality cx = d + 1\} … Read more
Stochastic dominance theory provides tools to compare random entities. When comparing random vectors (say X and Y ), the problem can be viewed as one of multi-criterion decision making under uncertainty. One approach is to compare weighted sums of the components of these random vectors using univariate dominance. In this paper we propose new concepts … Read more