The Complexity Of Cover Inequality Separation (1998)
D. Klabjan, G. L. Nemhauser, C. Tovey
. Crowder et al. [1] conjectured that the separation problem for cover inequalities for binary integer programs is polynomially solvable. We show that the general problem is NP-hard but a special...
The Complexity Of Cover Inequality Separation (1998)
D. Klabjan, G. L. Nemhauser, C. Tovey
. Crowder et al. [1] conjectured that the separation problem for cover inequalities for binary integer programs is polynomially solvable. We show that the general problem is NP-hard but a special...
Fulkerson,D. R., Nemhauser,G. L.
Two minimum cardinality set covering problems of similar structure are presented as difficult test problems for evaluating the computational efficiency of integer programming and set covering...
When the Greedy Solution Solves a Class of Knapsack Problems. (1998)
Magazine,M. J., Nemhauser,G. L.
A heuristic for the knapsack problem that recursively determines a solution by making a variable with smallest marginal cost as large as possible is studied. Recursive necessary and sufficient...
Vertex Packings: Structural Properties and Algorithms. (1998)
A sufficient local optimality condition is given for the weighted vertex packing problem. It is shown that integer-valued variables in an optimal solution to the linearization of this problem retain...
The Uncapacitated Facility Location Problem. (1998)
Cornuejols,G., Nemhauser,G. L., Wolsey,L. A.
An economic problem of great practical importance is to choose the location of facilities, such as industrial plants or warehouses, in order to minimize the cost (or maximize the profit) of...
Given a finite ground set, a set of subsets and costs on the subsets, the set partitioning problem is to find a minimum cost partition of the ground set. Many combinatorial optimization problems can...
Given a finite ground set, a set of subsets and costs on the subsets, the set partitioning problem is to find a minimum cost partition of the ground set. Many combinatorial optimization problems can...
Computational Experience with a Polynomial-Time Dual Simplex Algorithm for the Transportation Problem
Computational Experience with a Polynomial-Time Dual Simplex Algorithm for the Transportation Problem
Solving Multi-Item Capacitated Lot-Sizing Problems with Setup Times by Branch-and-Cut.
Miller, A.J., Nemhauser, G.L., Savelsbergh, M.W.P.
Instances of the multi-item capacitated lot-sizing problem with setup times (MCL) often appear in practice, either in standard form or with additional constraints, but they have generally been...
Miller, A.J., Nemhauser, G.L., Savelsbergh, M.W.P.
We study a special case of a structured mixed integer programming model that arises in a number of applications. For the most general case of the model, called PI, we have earlier analyzed the...
On the Polyhedral Structure of a Multi-Item Production Planning Model with Setup Times.
Miller, A.J., Nemhauser, G.L., Savelsbergh, M.W.P.
We present and study a mixed integer programing model that arises as a sub-structure in any industrial applications. This model provides a relaxation of various capacitated production planning...