George L. Nemhauser

Enhancing Techniques in LP Based Approximation Algorithms (2007)

Abstract. We present and study a mixed integer programming model that arises as a substructure in many industrial applications. This model provides a relaxation of various capacitated production...

Kamal Jain, Richard A. Duke, Kalomire-eleni Mihail, George L. Nemhauser, Leonard J. Schulman

nts between every pair of vertices. We are asked to find a least cost subgraph such that every pair of vertices is connected with at least as many edge disjoint paths as their connectivity...

A lifted linear programming branch-and-bound algorithm for mixed integer conic quadratic programs (2007)

Juan Pablo Vielma, Shabbir Ahmed, George L. Nemhauser

This paper develops a linear programming based branch-and-bound algorithm for mixed in-teger conic quadratic programs. The algorithm is based on a higher dimensional or lifted polyhedral relaxation...

Cutting planes for multi-stage stochastic integer programs (2006)

Guan, Yongpei, Ahmed, Shabbir, Nemhauser, George L.

This paper addresses the problem of finding cutting planes for multi-stage stochastic integer programs. We give a general method for generating cutting planes for multi-stage stochastic integer...

Cutting planes for multi-stage stochastic integer programs (2006)

Guan, Yongpei, Ahmed, Shabbir, Nemhauser, George L.

This paper addresses the problem of finding cutting planes for multi-stage stochastic integer programs. We give a general method for generating cutting planes for multi-stage stochastic integer...

Application of Mixed-Integer Programming to Selected Military Problems (2006)

Approved by: Drayage Optimization in Truck/Rail Networks (2006)

This is a final report on a contract whose objective was to provide research support to the Concepts Analysis Agency (CAA) in the solution of large- scale mixed-integer programming models. We...

George L. Nemhauser, Joel Sokol, Alan L. Erera, Özlem Ergun

Approved by: CUTTING PLANES FOR LARGE MIXED INTEGER PROGRAMMING MODELS (2006)

G. Goycoolea, William J. Cook, George L. Nemhauser, Ellis L. Johnson, Robin Thomas, Zonghao Gu

Sports Scheduling (2005)

Functional description of MINTO, a Mixed INTeger Optimizer -- Version 3.1 (2005)

Presentation given in the Wilby Room of the Georgia Tech Library and Information Center.

George L. Nemhauser, Jeff T. Linderoth

Sequential pairing of mixed integer inequalities (2005)

Yongpei Guan, Shabbir Ahmed, George L. Nemhauser

We investigate a scheme, called pairing, for generating new valid inequalities for mixed integer programs by taking pair-wise combinations of existing valid inequalities. The pairing scheme...

A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem (2004)

Guan, Yongpei, Ahmed, Shabbir, Nemhauser, George L.

This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical $(\mathcal{l}, S)$ inequalities for...

A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem (2004)

Guan, Yongpei, Ahmed, Shabbir, Nemhauser, George L.

This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical $(\mathcal{l}, S)$ inequalities for...

Approved by: Inventory Routing Investigations (2004)

Laurie Dutton, Alan Erera, George L. Nemhauser

To my wife, for her love and patience. iii ACKNOWLEDGEMENTS I would like to express my deepest appreciation to Dr. Martin Savelsbergh for serving as my thesis advisor, and providing invaluable advice...

A Branch-and-Cut Algorithm for the Stochastic Uncapacitated Lot-Sizing Problem (2004)

Yongpei Guan, Shabbir Ahmed, George L. Nemhauser

This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (#, S) inequalities for the...

A Stochastic Model of Airline Operations (2002)

Jay M. Rosenberger, Andrew J. Schaefer, David Goldsman, Ellis L. Johnson, Anton J. Kleywegt, George L. Nemhauser

Decision makers in air transportation face many uncertainties. In spite of this, airline planning models do not explicitly consider uncertainty in operations. As a result, there is often a notable...

A multi-item production planning model with setup times: algorithms, reformulations, and polyhedral characterizations for a special case (2001)

Airline Crew Scheduling under Uncertainty (2001)

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

Andrew J. Schaefer, Ellis L. Johnson, Anton J. Kleywegt, George L. Nemhauser

Airline crew scheduling algorithms widely used in practice assume no disruptions. Since disruptions often occur, the actual cost of the resulting crew schedules is often significantly greater. We...

Progress in linear programming-based algorithms for integer programming: An exposition (2000)

Ellis L. Johnson, George L. Nemhauser, W. P. Savelsbergh

This paper is about modeling and solving mixed integer programming (MIP) problems. In the last decade, the use of mixed integer programming models has increased dramatically. Fifteen years ago,...

On the polyhedral structure of a multi-item production planning model with setup times (2000)

Solving multi–item capacitated lot–sizing problems with setup times by branch–and–cut (2000)

We present and study a mixed integer programming model that arises as a substructure in many industrial applications. This model provides a relaxation of various capacitated production planning...

On the polyhedral structure of a multi-item production planning model with setup times (2000)

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

The Mixed Vertex Packing Problem (2000)

We present and study a mixed integer programming model that arises as a substructure in many industrial applications. This model provides a relaxation of various capacitated production planning...

Solving Multi-Item Capacitated Lot-Sizing Problems with Setup Times by Branch-and-Cut (2000)

We study a generalization of the vertex packing problem having both binary and bounded continuous variables, called the mixed vertex packing problem (MVPP). The well-known vertex packing model arises...

SIMAIR: A stochastic model of airline operations (2000)

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

Jay M. Rosenberger, Andrew J. Schaefer, David Goldsman, Ellis L. Johnson, Anton J. Kleywegt, George L. Nemhauser

Airline transportation systems are inherently random. However, airline planning models do not explicitly consider stochasticity in operations. Because of this, there is often a notable discrepancy...

Sequence independent lifting in mixed integer programming (2000)

Valid Inequalities for Problems With Additive Variable Upper Bounds (1999)

We investigate lifting, i.e., the process of taking a valid inequality for a polyhedron and extending it to a valid inequality in a higher dimensional space. Lifting is usually applied sequentially,...

Applications of Mixed-Integer Programming to Problems of the U.S. Army. (1998)

. We study the facial structure of a polyhedron associated with the single node relaxation of network flow problems with additive variable upper bounds. This type of structure arises for example in...

Search Strategies in Large-Scale Discrete Optimization: A Joint AI/OR Approach (1998)

This research focuses on applying mixed-integer programming (MIP) to selected problems of the U.S. Army. The research has two distinct aspects: Phase I: Methodology. Developing and implementing new...

Etherington, David W., Joslin, David, Nemhauser, George L.

The aim of this award was to exploit and enhance the differing strengths of Artificial Intelligence (AI) and Operations Research (OR) in solving hard combinatorial optimization problems, discover...

Evaluators report, the Logistics Institute/Material Handling Research Center, Georgia Institute of Technology/University of Arkansas, 1997 (1998)

Lifted Cover Inequalities for 0-1 Integer Programs: Computation (1998)

Issued as final report

Con ict graphs in solving integer programming problems 1 (1998)

We investigate the algorithmic and implementation issues related to the e ective and e cient use of lifted cover inequalities and lifted GUB cover inequalities in a branch-and-cut algorithm for 0-1...

Alper Atamturk, George L. Nemhauser

We report on the use of con ict graphs in solving integer programs. A con ict graph represents logical relations between binary variables. We develop algorithms and data structures that allow the e...

Scheduling a major college basketball conference (1998)

George L. Nemhauser, Michael A. Trick

The nine universities in the Atlantic Coast Conference (ACC) have a basketball competition in which each school plays home and away games against each other over a nine-week period. The creation of a...

Lifted Cover Inequalities for 0-1 Integer Programs: Computation (1998)

Branch-and-price: Column generation for solving huge integer programs (1998)

We investigate several complexity issues related to branch-and-cut algorithms for 0-1 integer programming based on lifted cover inequalities (LCIs). We show that given a fractional point, determining...

Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Pamela H. Vance

We discuss formulations of integer programs with a huge number of variables and their solution by column generation methods, i.e., implicit pricing of nonbasic variables to generate new columns or to...

Sequence Independent Lifting in Mixed Integer Programming (1998)

Conflict Graphs in Integer Programming (1998)

We investigate lifting, i.e., the process of taking a valid inequality for a polyhedron and extending it to a valid inequality in a higher dimensional space. Lifting is usually applied sequentially,...

Alper Atamturk, George L. Nemhauser

We report on the use of conflict graphs in solving integer programs. A conflict graph represents logical relations between binary variables appearing in an integer program. We develop algorithms and...

On the Capacitated Lot--Sizing and Continuous 0--1 Knapsack Polyhedra (1998)

Andrew Miller George, George L. Nemhauser

We consider the single item capacitated lot--sizing problem, a well-known production planning model that often arises in practical applications, and derive new classes of valid inequalities for it....

Functional description of MINTO, a Mixed INTeger Optimizer Version 3.0 (1998)

George L. Nemhauser

MINTO is a software system that solves mixed-integer linear programs by a branch-andbound algorithm with linear programming relaxations. It also provides automatic constraint classification,...

A Flow Model with Additive Variable Upper Bounds: Valid Inequalities and Applications (1998)

The Mixed Vertex Packing Problem (1998)

1 Introduction We investigate the polyhedral structure of a single node network flow model with additive variable upper bounds. This model generalizes the one given by Padberg, Van Roy and Wolsey [3]...

Lifted Cover Inequalities for 0-1 Integer Programs: Computation (1998)

We study the polyhedral structure of a new model for various bottleneck resource allocation problems in which the resource consumption is determined by the activity with the maximum usage. The model,...

Mathematical Programming manuscript No. (will be inserted by the editor) (1998)

We investigate several complexity issues related to branch-and-cut algorithms for 0-1 integer programming based on lifted cover inequalities (LCIs). We showthat given a fractional point, determining...

Branch-and-price: Column generation for solving huge integer programs (1998)

Abstract. We study a generalization of the vertex packing problem having both binary and bounded continuous variables, called the mixed vertex packing problem (MVPP). The wellknown vertex packing...

Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Pamela H. Vance

We discuss formulations of integer programs with a huge number of variables and their solution by column generation methods, i.e., implicit pricing of nonbasic variables to generate new columns or to...

Evaluators report, the Logistics Institute/Material Handling Research Center, Georgia Institute of Technology/University of Arkansas, 1997 (1998)

Applications of Mixed-Integer Programming to Problems of the U.S. Army. (1997)

Issued as final report

Search strategies in large-scale discrete optimization : a joint AI/OR approach (1997)

This research focuses on applying mixed integer programming (MIP) to selected problems of the U.S. Army. Many strategic planning problems can be formulated as MIPs but frequently they contain a huge...

Lifted Cover Inequalities for 0-1 Integer Programs: Computation (1997)

Issued as final report

Heuristic Optimization: A hybrid AI/OR approach (1997)

We investigate the algorithmic and implementation issues related to the effective and efficient use of lifted cover inequalities and lifted GUB cover inequalities in a branch-and-cut algorithm for...

David P. Clements, James M. Crawford, David E. Joslin, George L. Nemhauser, Markus E. Puttlitz

We have developed a hybrid architecture, h-opt, that combines Integer Programming (IP) for global optimization, and heuristic search techniques. Our hybrid approach captures the most desirable...

A Heuristic Branch-and-Price Approach for the Airline Crew Pairing Problem (1997)

Pamela H. Vance, Alper Atamturk, Cynthia Barnhart, Eric Gelman, Ellis L. Johnson, Alamuru Krishna, ...

We describe a methodology for finding near-optimal solutions to airline crew pairing problems. We use a dynamic column generation scheme to identify crew work schedules combined with a customized...

Scheduling a Major College Basketball Conference (1997)

George L. Nemhauser, Michael A. Trick

The nine universities in the Atlantic Coast Conference (ACC) have a basketball competition in which each school plays home and away games against each other over a nine-week period. The creation of a...

OR PRACTICE SCHEDULING A MAJOR COLLEGE BASKETBALL CONFERENCE (1997)

George L. Nemhauser, Michael A. Trick

The nine universities in the Atlantic Coast Conference (ACC) have a basketball competition in which each school plays home and away games against each other over a nine-week period. The creation of a...

y i2 Technologies (1997)

George L. Nemhauser, Markus E. Puttlitz

We have developed a hybrid architecture, h-opt, that combines Integer Programming (IP) for global optimization, and heuristic search techniques. Our hybrid approach captures the most desirable...

Search strategies in large-scale discrete optimization : a joint AI/OR approach (1997)

Lifted Flow Cover Inequalities for Mixed 0-1 Integer Programs (1996)

Issued as final report

Production Scheduling in Almost Continuous Time (1995)

We investigate strong inequalities for mixed 0-1 integer programs derived from flow cover inequalities. Flow cover inequalities are usually not facet defining and need to be lifted to obtain stronger...

Kevin R. Gue, George L. Nemhauser, Mario Padron

We present a large scale production scheduling problem where each order is unique and the processing time for an operation can be close to the size of a time period. Because modeling the problem as a...

Airline Crew Scheduling: A New Formulation and Decomposition Algorithm (1995)

Pamela H. Vance, Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser

Airline crew scheduling is concerned with finding a minimum cost assignment of flight crews to a given flight schedule while satisfying restrictions dictated by collective bargaining agreements and...

MINTO, a mixed integer optimizer (1994)

George L. Nemhauser, Gabriele C. Sigismondi

MINTO is a software system that solves mixed-integer linear programs by a branch-and-bound algorithm with linear programming relaxations. It also provides automatic constraint classification,...

MINTO, a Mixed INTeger Optimizer (1994)

George L. Nemhauser, Gabriele C. Sigismondi

MINTO is a software system that solves mixed-integer linear programs by a branch-and-bound algorithm with linear programming relaxations. It also provides automatic constraint classification,...

Engineering: Cornell Quarterly, Vol.13, No.1 (July 1978): Operations Research Comes of Age (1978)

Nemhauser, George L., Muckstadt, John A., Schruben, Lee W., Lucas, William F.

IN THIS ISSUE: Operations Research /2 (George L. Nemhauser, director of the School of Operations Research and Industrial Engineering at Cornell, presents a perspective of a field still not well...

Engineering: Cornell Quarterly, Vol.13, No.1 (July 1978): Operations Research Comes of Age (1978)

Nemhauser, George L., Muckstadt, John A., Schruben, Lee W., Lucas, William F.

IN THIS ISSUE: Operations Research /2 (George L. Nemhauser, director of the School of Operations Research and Industrial Engineering at Cornell, presents a perspective of a field still not well...

Integer programming / Robert S. Grafinkel. George L. Nemhauser (1972)

Garfinkel, Robert S, Nemhauser, George L

A Wiley-Interscience Publication

Introduction to dynamic programing / Georege L. Nemhauser (1966)

Nemhauser, George L

Short-term booking of air cargo space

Chew, Ek-Peng, Huang, Huei-Chuen, Johnson, Ellis L., Nemhauser, George L., Sokol, Joel S., Leong, Chun-How

On the capacitated lot-sizing and continuous 0-1 knapsack polyhedra

Miller, Andrew J., Nemhauser, George L., Savelsbergh, Martin W. P.

Conflict graphs in solving integer programming problems

Atamturk, Alper, Nemhauser, George L., Savelsbergh, Martin W. P.

Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case

Lee, Heesang, Nemhauser, George L., Wang, Yinhua

A multi-item production planning model with setup times: algorithms, reformulations, and polyhedral characterizations for a special case

MILLER, Andrew J., NEMHAUSER, George L., SAVELSBERGH, Martin 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...

The design of optimum piping networks for incompressible fluids by linear programming techniques.