We consider bounded integer knapsacks where the weights and variable upper bounds together form a superincreasing sequence. The elements of this superincreasing knapsack are exactly those vectors that are lexicographically smaller than the greedy solution to optimizing over this knapsack. We describe the convex hull of this n-dimensional set with O(n) facets. We also establish … Read more
Split cuts are among the most important and well-understood cuts for general mixed-integer programs. In this paper we consider some recent generalizations of split cuts and compare their relative strength. More precisely, we compare the elementary closures of {split}, {cross}, {crooked cross} and general {multi-branch split cuts} as well as cuts obtained from multi-row and … Read more
We give an algorithm for testing the extremality of a large class of minimal valid functions for the two-dimensional infinite group problem. ArticleDownload View PDF
In this paper, we study self-avoiding walks of a given length on a graph. We consider a formulation of this problem as a binary linear program. We analyze the polyhedral structure of the underlying polytope and describe valid inequalities. Proofs for their facial properties for certain special cases are given. In a variation of this … Read more
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