Valid inequalities for 0–1 knapsacks and mips with generalised upper bound constraints

Discrete Applied MathematicsPublished 1 December 1990

Laurence A. Wolsey

DOI10.1016/0166-218x(90)90148-6

Source URL

Citations101

SJR quartileQ2

SJR score0.66

SNIP1.11

TL;DR

It is shown that the inequalities are “strong” by showing that in one special case, they suffice to describe the convex hull of solutions, and for other models it is possible to obtain violated inequalities by using constraint aggregation followed by the above separation procedure.

Abstract

We derive valid inequalities for the knapsack problem with generalised upper bound (GUB) constraints, and show that the separation problem for a subclass of the inequalities is again a knapsack problem with GUB constraints. It is shown that the inequalities are "strong" by showing that in one special case, they suffice to describe the convex hull of solutions, and for other models it is possible to obtain violated inequalities by using constraint aggregation followed by the above separation procedure.

Keywords

Computer ScienceEngineeringBusiness, Management and Accounting

Operations ResearchSolving Large-Scale Zero-One Linear Programming Problems

676 Citations1983Harlan Crowder, Ellis L. Johnson +1 more

The results indicate that cutting-planes related to the facets of the underlying polytope are an indispensable tool for the exact solution of this class of problem.

Mathematical ProgrammingFacets of the knapsack polytope

393 Citations1975Egon Balas

A necessary and sufficient condition is given for an inequality with coefficients 0 or 1 to define a facet of the knapsack polytope, i.e., of the convex hull of 0–1 points satisfying a given linear inequality.

Mathematical ProgrammingFaces for a linear inequality in 0–1 variables

302 Citations1975Laurence A. Wolsey

Special subclasses of inequalities for which all faces can be generated are demonstrated, including the “matroidal” and “graphic” inequalities, where a count on the number of such inequalities is obtained, and inequalities where all Faces can be derived from lower dimensional faces.

Operations ResearchSolving Mixed Integer Programming Problems Using Automatic Reformulation

272 Citations1987Tony J. Van Roy, Laurence A. Wolsey

The solution to optimality of 18 medium-to large-size problems, including production planning problems with setup costs and capacity constraints, multilevel distribution planning problems, drainage and heating system design problems, and electricity generator scheduling problems is reported on.

Mathematical ProgrammingFacet of regular 0–1 polytopes

168 Citations1975P. L. Hammer, E. L. Johnson +1 more

A special class of prime implicants is described for regular functions and it is shown that for anyP in this class,F(P) consists of one facet of H, and this facet has 0–1 coefficients, and every nontrivial facet ofH with 0-1 coefficients is obtained from this class.

Discrete Applied MathematicsValid inequalities for mixed 0–1 programs

118 Citations1986Tony J. Van Roy, Laurence A. Wolsey

A class of valid inequalities is derived for a typical region appearing in mixed 0–1 programs, namely a single row with variable or simple lower and/or upper bounds on the continuous variables.

Mathematical ProgrammingThe generalized assignment problem: Valid inequalities and facets

53 Citations1990Elsie Sterbin Gottlieb, M. R. Rao

It is proved that a basic fractional solution to the linear programming relaxation can be eliminated by a facet defining inequality associated with an individual knapsack constraint.