George L. Nemhauser

A Lifted Linear Programming Branch-and-Bound Algorithm for Mixed Integer Conic Quadratic Programs

  • Shabbir Ahmed
  • George L. Nemhauser
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Nonlinear Programming

    This paper develops a linear programming based branch-and-bound algorithm for mixed integer conic quadratic programs. The algorithm is based on a higher dimensional or lifted polyhedral relaxation of conic quadratic constraints introduced by Ben-Tal and Nemirovski. The algorithm is different from other linear programming based branch-and-bound algorithms for mixed integer nonlinear programs in that, it … Read more

    Cutting planes for multi-stage stochastic integer programs

  • Shabbir Ahmed
  • Yongpei Guan
  • George L. Nemhauser
    • Categories Cutting Plane Approaches, Stochastic Programming Tags , , ,

    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 programs based on combining inequalities that are valid for the individual scenarios. We apply the method to generate cuts for a stochastic version of a dynamic knapsack problem … Read more

    Sequential pairing of mixed integer inequalities

  • Shabbir Ahmed
  • Yongpei Guan
  • George L. Nemhauser
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We present a scheme for generating new valid inequalities for mixed integer programs by taking pair-wise combinations of existing valid inequalities. Our scheme is related to mixed integer rounding and mixing. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some important cases, we identify combination sequences that … Read more

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

  • Shabbir Ahmed
  • Yongpei Guan
  • George L. Nemhauser
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Stochastic Programming

    This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (l,S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (l,S) inequalities to a general class of valid inequalities, called the (Q,S_Q) inequalities, and we … Read more

    A Polyhedral Study of the Cardinality Cosntrained Knapsack Problem

  • Ismael de Farias
  • George L. Nemhauser
    • Categories Branch and Cut Algorithms, Combinatorial Optimization, Integer Programming Tags , , ,

    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 example, in areas as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous … Read more

    The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study

  • Shabbir Ahmed
  • Anton J. Kleywegt
  • George L. Nemhauser
  • Alexander Shapiro
  • Bram Verweij
    • Categories Cutting Plane Approaches, Stochastic Programming, Transportation Tags , , ,

    The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. … Read more

    A Family of Inequalities for the Generalized Assignment Polytope

  • George L. Nemhauser
  • Ismael de Farias
    • Categories 0-1 Programming, Branch and Cut Algorithms Tags , ,

    We present a family of inequalities that are valid for the generalized assignment polytope. Although the inequalities are not facet-defining in general, they define facets of a polytope of a relaxation. We report computational results on the use of the inequalities in a branch-and-cut scheme that demonstrate their effectiveness. Citation Department of Industrial Engineering, State … Read more

    Facets of the Complementarity Knapsack Polytope

  • Ellis L. Johnson
  • George L. Nemhauser
  • Ismael de Farias
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms Tags , ,

    We present a polyhedral study of the complementarity knapsack problem, in which no auxiliary binary variables are introduced, but rather the inequalities are derived in the space of the continuous variables. Citation School of Industrial and Systems Engineering, GA Tech, under review Article Download View Facets of the Complementarity Knapsack Polytope