Integer 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

    Visualizing Branch-and-Bound Algorithms

  • Brady Hunsaker
  • Osman Y. Ozaltin
  • Ted K. Ralphs
    • Categories Integer Programming

    We present a suite of tools for visualizing the status and progress of branch-and-bound algorithms for mixed integer programming. By integrating these tools with the open-source codes CBC, SYMPHONY, and GLPK, we demonstrate the potential usefulness of visual representations in helping a user predict future progress of the algorithm or analyzing the algorithm’s performance. We … Read more

    Computational experience with general cutting planes for the Set Covering problem

  • Pasquale Avella
  • Maurizio Boccia
  • Igor Vasilyev
    • Categories 0-1 Programming Tags ,

    In this paper we present a cutting plane algorithm for the Set Covering problem. Cutting planes are generated by a “general” (i.e. not based on the “template paradigm”) separation algorithm based on the following idea: i) identify a suitably small subproblem defined by a subset of the constraints of the formulation; ii) run an exact … Read more

    Lifting Inequalities: A framework for generating strong cuts in nonlinear programs

  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories Global Optimization, Integer Programming, Nonlinear Optimization Tags , , , , ,

    In this paper, we propose lifting techniques for generating strong cuts for nonlinear programs that are globally-valid. The theory is geometric and provides intuition into lifting-based cut generation procedures. As a special case, we find short proofs of earlier results on lifting techniques for mixed-integer programs. Using convex extensions, we obtain conditions that allow sequence-independent … 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. CitationOperations Research Letters 36 (2008) 439–443ArticleDownload View PDF

    Single-layer Cuts for Multi-layer Network Design Problems

  • Georg Baier
  • Arie M.C.A. Koster
  • Sebastian Orlowski
  • Thomas Engel
  • Christian Raack
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Telecommunications Tags , , ,

    We study a planning problem arising in SDH/WDM multi-layer telecommunication network design. The goal is to find a minimum cost installation of link and node hardware of both network layers such that traffic demands can be realized via grooming and a survivable routing. We present a mixed-integer programming formulation that takes many practical side constraints … 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