Integer Programming

On mixed integer reformulations of monotonic probabilistic programming problems with discrete distributions

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

    The paper studies large scale mixed integer reformulation approach to stochastic programming problems containing probability and quantile functions, under assumption of discreteness of the probability distribution involved. Jointly with general sample approximation technique and contemporary mixed integer programming solvers the approach gives a regular framework to solution of practical probabilistic programming problems. In the literature … Read more

    Truss topology design with integer variables made easy

  • Michal Kočvara
    • Categories (Mixed) Integer Nonlinear Programming, Mechanical Engineering, Semi-definite Programming Tags , ,

    We propose a new look at the problem of truss topology optimization with integer or binary variables. We show that the problem can be equivalently formulated as an integer \emph{linear} semidefinite optimization problem. This makes its numerical solution much easier, compared to existing approaches. We demonstrate that one can use an off-the-shelf solver with default … Read more

    Combinatorial Integral Approximation

  • Michael N. Jung
  • Christian Kirches
  • Sebastian Sager
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Distributed Control Tags , ,

    We are interested in structures and efficient methods for mixed-integer nonlinear programs (MINLP) that arise from a first discretize, then optimize approach to time-dependent mixed-integer optimal control problems (MIOCPs). In this study we focus on combinatorial constraints, in particular on restrictions on the number of switches on a fixed time grid. We propose a novel … Read more

    The Chvatal-Gomory Closure of a Strictly Convex Body

  • Daniel Dadush
  • Santanu S. Dey
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches

    In this paper, we prove that the Chvatal-Gomory closure of a set obtained as an intersection of a strictly convex body and a rational polyhedron is a polyhedron. Thus, we generalize a result of Schrijver which shows that the Chvatal-Gomory closure of a rational polyhedron is a polyhedron. ArticleDownload View PDF

    Small bipartite subgraph polytopes

  • Laura Galli
  • Adam N. Letchford
    • Categories 0-1 Programming, Polyhedra Tags ,

    We compute a complete linear description of the bipartite subgraph polytope, for up to seven nodes, and a conjectured complete description for eight nodes. We then show how these descriptions were used to compute the integrality ratio of various relaxations of the max-cut problem, again for up to eight nodes. CitationL. Galli & A.N. Letchford … Read more

    Approximating the minimum directed tree cover

  • Viet Hung Nguyen
    • Categories 0-1 Programming, Approximation Algorithms, Telecommunications Tags , , ,

    Given a directed graph $G$ with non negative cost on the arcs, a directed tree cover of $G$ is a directed tree such that either head or tail (or both of them) of every arc in $G$ is touched by $T$. The minimum directed tree cover problem (DTCP) is to find a directed tree cover … Read more

    A Polyhedral Study of Triplet Formulation for Single Row Facility Layout Problem

  • Kiavash Kianfar
  • Sujeevraja Sanjeevi
    • Categories Integer Programming Tags , , , ,

    The Single Row Facility Layout Problem (SRFLP) is the problem of arranging n departments with given lengths on a straight line so as to minimize the total weighted distance between all department pairs. We present a polyhedral study of the triplet formulation of the SRFLP introduced by Amaral [Discrete Applied Mathematics 157(1)(2009)183-190]. For any number … Read more

    Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra

  • Sanjeeb Dash
  • Santanu S. Dey
  • Oktay Gunluk
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , ,

    In this paper, we study the relationship between {\em 2D lattice-free cuts}, the family of cuts obtained by taking two-row relaxations of a mixed-integer program (MIP) and applying intersection cuts based on maximal lattice-free sets in $\R^2$, and various types of disjunctions. Recently, Li and Richard (2007) studied disjunctive cuts obtained from $t$-branch split disjunctions … Read more

    Sequencing and Scheduling in Coil Coating with Shuttles

  • Wiebke Höhn
  • Marco E. Lübbecke
  • Felix G. König
  • Rolf H. Möhring
    • Categories (Mixed) Integer Linear Programming, Graphs and Matroids, Production and Logistics Tags , , , , , ,

    We consider a complex planning problem in integrated steel production. A sequence of coils of sheet metal needs to be color coated in consecutive stages. Di erent coil geometries and changes of coatings may necessitate time-consuming setup work. In most coating stages one can choose between two parallel color tanks in order to reduce setup times. … Read more

    Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation

  • Stefano Gualandi
  • Federico Malucelli
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    We consider two approaches for solving the classical minimum vertex coloring problem�that is, the problem of coloring the vertices of a graph so that adjacent vertices have different colors and minimizing the number of used colors, namely, constraint programming and column generation. Constraint programming is able to solve very efficiently many of the benchmarks but … Read more