We review strong inequalities for fundamental knapsack relaxations of (mixed) integer programs. These relaxations are the 0-1 knapsack set, the mixed 0-1 knapsack set, the integer knapsack set, and the mixed integer knapsack set. Our aim is to give a unified presentation of the inequalities based on covers and packs and highlight the connections among … Read more
We consider the rail car management at industrial in-plant railroads. Demands for materials or empty cars are characterized by a track, a car type, and the desired quantity. If available, we assign cars from the stock, possibly substituting types, otherwise we rent additional cars. Transportation requests are fulfilled as a short sequence of pieces of … Read more
In this paper we consider a particular class of nonlinear optimization problems involving both continuous and discrete variables. The distinguishing feature of this class of nonlinear mixed optimization problems is that the structure and the number of variables of the problem depend on the values of some discrete variables. In particular we define a general … Read more
We propose an algorithm based on Barvinok’s counting algorithm for P -> max {c’x | Ax
Given $A\in Z^{m\times n}$ and $b\in Z^m$, we consider the integer program $\max \{c’x\vert Ax=b;x\in N^n\}$ and provide an equivalent and explicit linear program $\max \{\widehat{c}’q\vert M q=r;q\geq 0\}$, where $M,r,\widehat{c}$ are easily obtained from $A,b,c$ with no calculation. We also provide an explicit algebraic characterization of the integer hull of the convex polytope $P=\{x\in\R^n\vert … Read more
We consider the integer program $\max \{c’ x\,|\,Ax=b,x\in N^n\}$. A formal parallel between linear programming and continuous integration on one side, and discrete summation on the other side, shows that a natural duality for integer programs can be derived from the $Z$-transform and Brion and Vergne’s counting formula. Along the same lines, we also provide … Read more
Given a convex rational polytope $\Omega(b):=\{x\in\R^n_+\,|\,Ax=b\}$, we consider the function $b\mapsto f(b)$, which counts the nonnegative integral points of $\Omega(b)$. A closed form expression of its $\Z$-transform $z\mapsto \mathcal{F}(z)$ is easily obtained so that $f(b)$ can be computed as the inverse $\Z$-transform of $\mathcal{F}$. We then provide two variants of an inversion algorithm. As a … Read more
The lot-sizing polytope is a fundamental structure contained in many practical production planning problems. Here we study this polytope and identify facet-defining inequalities that cut off all fractional extreme points of its linear programming relaxation, as well as liftings from those facets. We give a polynomial-time combinatorial separation algorithm for the inequalities when capacities are … Read more
We study the mixed-integer knapsack polyhedron, that is, the convex hull of the mixed-integer set defined by an arbitrary linear inequality and the bounds on the variables. We describe facet-defining inequalities of this polyhedron that can be obtained through sequential lifting of inequalities containing a single integer variable. These inequalities strengthen and/or generalize known inequalities … Read more
Column generation has become a powerful tool in solving large scale integer programs. We argue that most of the often reported compatibility issues between pricing oracle and branching rules disappear when branching decisions are based on the reduction of the variables of the oracle’s domain. This can be generalized to branching on variables of a … Read more