G. L. Nemhauser

Publication List Details

Period

1985 - 2008

Number

24

Co-Authors

cwi.nl/CWIreports/PNA/PNA-E0421.pdf. (2008)

In K. Aardal, G. L. Nemhauser, R. Weismantel, Book On Discrete, S. Abiteboul, R. Agrawal, ...

[1] K. Aardal. Comments on the paper: Attacking the market split problem with lattice point

Printed in U.S.A. FACETS OF THE COMPLEMENTARITY KNAPSACK POLYTOPE (2008)

E. L. Johnson, G. L. Nemhauser

We present a polyhedral study of the complementarity knapsack problem. Traditionally, complementarity constraints are modeled by introducing auxiliary binary variables and additional constraints, and...

Properties and Bounds on P/T Nets (2007)

Javier Campos, D. L. Eager, G. L. Nemhauser, M. J. Todd

A complementary approach to exact or approximation techniques...

A Polyhedral Study of the Cardinality Constrained Knapsack Problem (2003)

G. L. Nemhauser

A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for...

Two Computationally Difficult Set Covering Problems that Arise in Computing the 1-Width of Incidence Matrices of Steiner Triple Systems. (1998)

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)

Nemhauser,G. L.

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...

A Generalized Assignment Problem with Special Ordered Sets: A Polyhedral Approach (Extended Abstract) (1998)

De Farias, E. L. Johnson, G. L. Nemhauser

I. R. de Farias, Jr. IBM Corporation, 3200 Windy Hill Rd., Atlanta, GA 30339 (WG09B) E. L. Johnson and G. L. Nemhauser School of Industrial and Systems Engineering Georgia Institute of Technology,...

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...

Facets of the complementarity knapsack polytope (1998)

E. L. Johnson, G. L. Nemhauser

We present a polyhedral study of the complementarity knapsack problem. Traditionally, complementarity constraints are modeled by introducing auxiliary binary variables and additional constraints, and...

A Combined Lagrangian, Linear Programming and Implication Heuristic for Large-Scale Set Partitioning Problems (1995)

A. Atamturk, G.L. Nemhauser

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 (1985)

Ikura, Y., Nemhauser, G. L.

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 (1985)

Ikura, Y., Nemhauser, G. L.

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...

A Multi-Item Prosuction Planning Model with Setup Times : Algorithms, Reformulations and Polyhedral Characterizations for a Special Case.

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...