(Mixed) Integer Linear Programming

Computational Experience with a Software Framework for Parallel Integer Programming

  • Lazslo Ladanyi
  • Ted K. Ralphs
  • Matthew Saltzman
  • Yan Xu
    • Categories (Mixed) Integer Linear Programming, Optimization Software Design Principles, Parallel Algorithms

    In this paper, we discuss the challenges that arise in parallelizing algorithms for solving mixed integer linear programs and introduce a software framework that aims to address these challenges. The framework was designed specifically with support for implementation of relaxation-based branch-and-bound algorithms in mind. Achieving efficiency for such algorithms is particularly challenging and involves a … Read more

    Single Item Lot-Sizing with Nondecreasing Capacities

  • Yves Pochet
  • Laurence A. Wolsey
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Production and Logistics Tags , , ,

    We consider the single item lot-sizing problem with capacities that are non-decreasing over time. When the cost function is i) non-speculative or Wagner-Whitin (for instance, constant unit production costs and non-negative unit holding costs), and ii) the production set-up costs are non-increasing over time, it is known that the minimum cost lot-sizing problem is polynomially … 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

    A polyhedral study of the Network Pricing Problem with Connected Toll Arcs

  • Géraldine Heilporn
  • Martine Labbé
  • Patrice Marcotte
  • Gilles Savard
    • Categories (Mixed) Integer Linear Programming, Yield Management Tags , ,

    Consider the problem that consists in maximizing the revenue generated by tolls set on a subset of arcs of a transportation network, and where origin-destination flows are assigned to shortest paths with respect to the sum of tolls and initial costs. In this work, we address the instance where toll arcs must be connected, as … 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

    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

    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