integer programming

New Formulations for Optimization Under Stochastic Dominance Constraints

  • James R. Luedtke
    • Categories Stochastic Programming Tags , , , ,

    Stochastic dominance constraints allow a decision-maker to manage risk in an optimization setting by requiring their decision to yield a random outcome which stochastically dominates a reference random outcome. We present new integer and linear programming formulations for optimization under first and second-order stochastic dominance constraints, respectively. These formulations are more compact than existing formulations, … Read more

    A new, solvable, primal relaxation for nonlinear integer programming problems with linear constraints

  • Monique Guignard
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization Tags , , , ,

    This paper describes a new primal relaxation for nonlinear integer programming problems with linear constraints. This relaxation, contrary to the standard Lagrangean relaxation, can be solved efficiently. It requires the solution of a nonlinear penalized problem whose linear constraint set is known only implicitly, but whose solution is made possible by the use of a … Read more

    On Test Sets for Nonlinear Integer Maximization

  • Shmuel Onn
  • Robert Weismantel
  • Jon Lee
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , , ,

    A finite test set for an integer maximization problem enables us to verify whether a feasible point attains the global maximum. We establish in this paper several general results that apply to integer maximization problems with nonlinear objective functions. Citation Operations Research Letters 36 (2008) 439–443 Article Download View On Test Sets for Nonlinear Integer … Read more

    Algorithms to Separate {0,1/2}-Chvatal-Gomory Cuts

  • Arie M.C.A. Koster
  • Adrian Zymolka
  • Manuel Kutschka
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , ,

    Chvatal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or 1/2, such cuts are known as {0, 1/2}-cuts. It has been proven by Caprara and Fischetti (1996) that separation of {0, 1/2}-cuts is NP-hard. In this paper, we study … Read more

    Column basis reduction and decomposable knapsack problems

  • Bala Krishnamoorthy
  • Gabor Pataki
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    We propose a very simple preconditioning method for integer programming feasibility problems: replacing the problem b’   ≤   Ax   ≤   b,   x ∈ Zn with b’   ≤   (AU)y   ≤   b,   y ∈ Zn, where U is a unimodular matrix computed via basis reduction, to make the … Read more

    Separation Algorithms for 0-1 Knapsack Polytopes

  • Konstantinos Kaparis
  • Adam N. Letchford
    • Categories 0-1 Programming, Cutting Plane Approaches, Polyhedra Tags , ,

    Valid inequalities for 0-1 knapsack polytopes often prove useful when tackling hard 0-1 Linear Programming problems. To use such inequalities effectively, one needs separation algorithms for them, i.e., routines for detecting when they are violated. We show that the separation problems for the so-called extended cover and weight inequalities can be solved exactly in O(nb) … Read more

    Improving a Formulation of the Quadratic Knapsack Problem

  • Daniel Grainger
  • Adam N. Letchford
    • Categories 0-1 Programming Tags ,

    The Quadratic Knapsack Problem can be formulated, using an idea of Glover, as a mixed 0-1 linear program with only 2n variables. We present a simple method for strengthening that formulation, which gives good results when the profit matrix is dense and non-negative. Citation Working Paper, Department of Management Science, Lancaster University, May 2007. Article … Read more

    On the strength of cut-based inequalities for capacitated network design polyhedra

  • Arie M.C.A. Koster
  • Christian Raack
  • Roland Wessäly
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Polyhedra Tags , , ,

    In this paper we study capacitated network design problems, differentiating directed, bidirected and undirected link capacity models. We complement existing polyhedral results for the three variants by new classes of facet-defining valid inequalities and unified lifting results. For this, we study the restriction of the problems to a cut of the network. First, we show … Read more

    A Computational Analysis of Lower Bounds for Big Bucket Production Planning Problems

  • Kerem Akartunali
  • Andrew J. Miller
    • Categories Production and Logistics Tags , , ,

    In this paper, we analyze a variety of approaches to obtain lower bounds for multi-level production planning problems with big bucket capacities, i.e., problems in which multiple items compete for the same resources. We give an extensive survey of both known and new methods, and also establish relationships between some of these methods that, to … Read more

    An integer programming approach for linear programs with probabilistic constraints

  • Shabbir Ahmed
  • James R. Luedtke
  • George L. Nemhauser
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    Linear programs with joint probabilistic constraints (PCLP) are difficult to solve because the feasible region is not convex. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We give a mixed-integer programming formulation for this special case and study the relaxation … Read more