Integer Programming

A MIP Approach for some Practical Packing Problems: Balancing Constraints and Tetris-like Items

  • Giorgio Fasano
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , , ,

    This paper considers packing problems with balancing conditions and items consisting of clusters of parallelepipeds (mutually orthogonal, i.e. tetris-like items). This issue is quite frequent in space engineering and a real-world application deals with the Automated Transfer Vehicle project (funded by the European Space Agency), at present under development. A Mixed Integer Programming (MIP) approach … 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

    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. CitationWorking Paper, Department of Management Science, Lancaster University, May 2007.ArticleDownload View PDF

    Some Relations Between Facets of Low- and High-Dimensional Group Problems

  • Santanu S. Dey
  • Jean-Philippe P. Richard
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags ,

    In this paper, we introduce an operation that creates families of facet-defining inequalities for high-dimensional infinite group problems using facet-defining inequalities of lower-dimensional group problems. We call this family sequential-merge inequalities because they are produced by applying two group cuts one after the other and because the resultant inequality depends on the order of the … Read more

    An Integer Programming Approach to the Path Selection Problems

  • Deokseong Kim
  • Kyungsik Lee
  • Kyungchul Park
  • Sungsoo Park
    • Categories Integer Programming, Network Optimization

    We consider two types of path selection problems defined on arc-capacitated networks. Given an arc-capacitated network and a set of selected ordered pairs of nodes (commodity) each of which has a demand quantity, the first problem is to select a subset of commodities and setup one path for each chosen commodity to maximize profit, while … Read more

    Computations with Disjunctive Cuts for Two-Stage Stochastic Mixed Integer Programs

  • Lewis Ntaimo
  • Matthew W. Tanner
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Stochastic Programming

    Two-stage stochastic mixed-integer programming (SMIP) problems with recourse are generally difficult to solve. This paper presents a first computational study of a disjunctive cutting plane method for stochastic mixed 0-1 programs that uses lift-and-project cuts based on the extensive form of the two-stage SMIP problem. An extension of the method based on where the data … Read more

    Solving Max-Cut to Optimality by Intersecting Semidefinite and Polyhedral Relaxations

  • Franz Rendl
  • Giovanni Rinaldi
  • Angelika Wiegele
    • Categories Integer Programming, Semi-definite Programming

    In this paper we present a method for finding exact solutions of Max-Cut, the problem of finding a cut of maximum weight in a weighted graph. We use a Branch-and-Bound setting, that applies a dynamic version of the bundle method as bounding procedure. This approach uses Lagrangian duality to obtain a “nearly optimal” solution of … 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