Symmetry plays an important role in optimization. The usual approach to cope with symmetry in discrete optimization is to try to eliminate it by introducing artificial symmetry-breaking conditions into the problem, and/or by using an ad-hoc search strategy. In this paper we argue that symmetry is instead a beneficial feature that we should preserve and … Read more
This paper introduces the PuLP library, an open source package that allows mathematical programs to be described in the Python computer programming language. PuLP is a high-level modelling library that leverages the power of the Python language and allows the user to create programs using expressions that are natural to the Python language, avoiding special … Read more
Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. In this paper we consider telecommunication network design under traffic uncertainty, adapting the robust optimization approach of Bertsimas and Sim (2004). We present three different mathematical formulations for this problem, provide valid inequalities, … Read more
In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (2008). By analyzing $n$-dimensional lattice-free sets, we prove that for every integer $n$ there exists a positive integer $t$ such that every facet-defining inequality of the … Read more
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