Integer Programming

A strong conic quadratic reformulation for machine-job assignment with controllable processing times

  • M. Selim Akturk
  • Alper Atamturk
  • Sinan Gurel
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming

    We describe a polynomial-size conic quadratic reformulation for a machine-job assignment problem with separable convex cost. Because the conic strengthening is based on only the objective of the problem, it can also be applied to other problems with similar cost functions. Computational results demonstrate the effectiveness of the conic reformulation. Citation Appeared in Operations Research … Read more

    Conic Mixed-Integer Rounding Cuts

  • Alper Atamturk
  • Vishnu Narayanan
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming

    A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These … Read more

    The Flow Set with Partial Order

  • Alper Atamturk
  • Muhong Zhang
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches

    The flow set with partial order is a mixed-integer set described by a budget on total flow and a partial order on the arcs that may carry positive flow. This set is a common substructure of resource allocation and scheduling problems with precedence constraints and robust network flow problems under demand/capacity uncertainty. We give a … Read more

    MIP-based heuristic for non-standard 3D-packing problems

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

    This paper is the continuation of a previous work (Fasano 2004), dedicated to a MIP formulation for non-standard three-dimensional packing issues, with additional conditions. The Single Bin Packing problem (Basic Problem) is considered and its MIP formulation shortly surveyed, together with some possible extensions, including balancing, tetris-like items and non-standard domains. A MIP-based heuristic is … Read more

    Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and the Nullstellensatz

  • Jesús A. De Loera
  • Jon Lee
  • Susan Margulies
  • Shmuel Onn
    • Categories Combinatorial Optimization, Integer Programming, Nonlinear Optimization Tags ,

    Systems of polynomial equations over the complex or real numbers can be used to model combinatorial problems. In this way, a combinatorial problem is feasible (e.g. a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution. In the first part of this paper, we construct new … Read more

    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

    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

    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

    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

    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