This paper presents a new warmstarting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after … Read more
We give an algorithm for testing the extremality of minimal valid functions for Gomory and Johnson’s infinite group problem, that are piecewise linear (possibly discontinuous) with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically, for deciding extremality in this important class of minimal valid functions. ArticleDownload … Read more
In this paper, we study the hop-constrained survivable network design problem with reliable edges. Given a graph with non-negative edge weights and node pairs Q, the hop-constrained survivable network design problem consists of constructing a minimum weight set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L … Read more
In recent years, branch-and-cut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MILPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MILPs are a critical element of branch-and-cut. This paper examines the nature of the so-called separation problem, which is … Read more
We introduce a natural strengthening of Gomory-Chvátal cutting planes for the important class of 0/1-integer programming problems and study the properties of the elementary closure that arises from the new class of cuts. Most notably, we prove that the new closure is polyhedral, we characterize the family of all facet-defining inequalities, and we compare it … Read more
We consider a model of medium-term commodity contracts management. Randomness takes place only in the prices on which the commodities are exchanged, whilst state variable is multi-dimensional, and decision variable is integer. In our previous article, we proposed an algorithm based on the quantization of random process and a dual dynamic programming type approach to … Read more
This paper introduces novel formulations for optimally responding to epidemics and cyber attacks in networks. In our models, at a given time period, network nodes (e.g., users or computing resources) are associated with probabilities of being infected, and each network edge is associated with some probability of propagating the infection. A decision maker would like … Read more
We introduce the n-step conic MIR inequalities for the so-called polyhedral second-order conic (PSOC) mixed integer sets. PSOC sets arise in the polyhedral reformulation of the second-order conic mixed integer programs. Moreover, they are an equivalent representation for any mixed integer set defined by two linear constraints. The simple conic MIR inequalities of Atamtürk and … Read more
Recently, cutting planes derived from maximal lattice-free convex sets have been studied intensively by the integer programming community. An important question in this research area has been to decide whether the closures associated with certain families of lattice-free sets are polyhedra. For a long time, the only result known was the celebrated theorem of Cook, … Read more
The corner relaxation of a mixed-integer linear program is a central concept in cutting plane theory. In a recent paper Fischetti and Monaci provide an empirical assessment of the strength of the corner and other related relaxations on benchmark problems. In this paper we give a precise characterization of the bounds given by these relaxations … Read more