Integer Programming

On reducing a quantile optimization problem with discrete distribution to a mixed integer programming problem

  • Andrey Kibzun
  • Vladimir I. Norkin
  • Andrey Naumov
    • Categories (Mixed) Integer Nonlinear Programming, Finance and Economics, Stochastic Programming Tags , , , , ,

    We suggest a method for equivalent transformation of a quantile optimization problem with discrete distribution of random parameters to mixed integer programming problems. The number of additional integer (in fact boolean) variables in the equivalent problems equals to the number of possible scenarios for random data. The obtained mixed integer problems are solved by standard … Read more

    On the Transportation Problem with Market Choice

  • Pelin Damci-Kurt
  • Santanu S. Dey
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Linear Programming, Transportation Tags , , ,

    We study a variant of the classical transportation problem in which suppliers with limited capacities have a choice of which demands (markets) to satisfy. We refer to this problem as the transportation problem with market choice (TPMC). While the classical transportation problem is known to be strongly polynomial-time solvable, we show that its market choice … Read more

    Incremental and Encoding Formulations for Mixed Integer Programming

  • Juan Pablo Vielma
  • Sercan Yildiz
    • Categories (Mixed) Integer Linear Programming

    The standard way to represent a choice between n alternatives in Mixed Integer Programming is through n binary variables that add up to one. Unfortunately, this approach commonly leads to unbalanced branch-and-bound trees and diminished solver performance. In this paper, we present an encoding formulation framework that encompasses and expands existing approaches to mitigate this … Read more

    On the relative strength of families of intersection cuts arising from pairs of tableau constraints in mixed integer programs

  • Yogesh Awate
  • Gérard Cornuéjols
  • Bertrand Guenin
  • Levent Tunçel
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We compare the relative strength of valid inequalities for the integer hull of the feasible region of mixed integer linear programs with two equality constraints, two unrestricted integer variables and any number of nonnegative continuous variables. In particular, we prove that the closure of Type~2 triangle (resp. Type~3 triangle; quadrilateral) inequalities, are all within a … Read more

    Intersection Cuts for Mixed Integer Conic Quadratic Sets

  • Kent Andersen
  • Anders Jensen
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    Balas introduced intersection cuts for mixed integer linear sets. Intersection cuts are given by closed form formulas and form an important class of cuts for solving mixed integer linear programs. In this paper we introduce an extension of intersection cuts to mixed integer conic quadratic sets. We identify the formula for the conic quadratic intersection … Read more

    Exact algorithms for the Traveling Salesman Problem with Draft Limits

  • Maria Battarra
  • Artur Alves Pessoa
  • Anand Subramanian
  • Eduardo Uchoa
    • Categories Branch and Cut Algorithms, Integer Programming Tags , , , ,

    This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance … Read more

    A NOTE ON THE EXTENSION COMPLEXITY OF THE KNAPSACK POLYTOPE

  • Sebastian Pokutta
  • Mathieu Van Vyve
    • Categories 0-1 Programming, Integer Programming, Polyhedra Tags , ,

    We show that there are 0-1 and unbounded knapsack polytopes with super-polynomial extension complexity. More specifically, for each n in N we exhibit 0-1 and unbounded knapsack polyhedra in dimension n with extension complexity \Omega(2^\sqrt{n}). Article Download View A NOTE ON THE EXTENSION COMPLEXITY OF THE KNAPSACK POLYTOPE

    On the Rank of Cutting-Plane Proof Systems

  • Sebastian Pokutta
  • Andreas S. Schulz
    • Categories 0-1 Programming, Cutting Plane Approaches, Polyhedra Tags , , , , , ,

    We introduce a natural abstraction of propositional proof systems that are based on cut- ting planes. This leads to a new class of proof systems that includes many well-known meth- ods, such as Gomory-Chvátal cuts, lift-and-project cuts, Sherali-Adams cuts, or split cuts. The rank of a proof system corresponds to the number of rounds that … Read more

    A New Class of Valid Inequalities for Nonlinear Network Design Problems

  • Armin Fügenschuh
  • Jesco Humpola
    • Categories (Mixed) Integer Nonlinear Programming

    We consider a nonlinear nonconvex network design problem that arises in the extension of natural gas transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides flow … Read more

    A big bucket time indexed formulation for nonpreemptive single machine scheduling problems

  • Natashia Boland
  • Hamish Waterer
  • Riley Clement
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , , ,

    A big bucket time indexed mixed integer linear programming formulation for nonpreemptive single machine scheduling problems is presented in which the length of each period can be as large as the processing time of the shortest job. The model generalises the classical time indexed model to one in which at most two jobs can be … Read more