Integer Programming

LP formulations for mixed-integer polynomial optimization problems

  • Daniel Bienstock
  • Gonzalo Muñoz
    • Categories (Mixed) Integer Nonlinear Programming, Nonsmooth Optimization Tags

    We present polynomial-time algorithms for constrained optimization problems overwhere the intersection graph of the constraint set has bounded tree-width. In the case of binary variables we obtain exact, polynomial-size linear programming formulations for the problem. In the mixed-integer case with bounded variables we obtain polynomial-size linear programming representations that attain guaranteed optimality and feasibility bounds. … Read more

    Quadratic Cone Cutting Surfaces for Quadratic Programs with On-Off Constraints

  • Hyemin Jeon
  • Jeff Linderoth
  • Andrew J. Miller
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming

    We study the convex hull of a set arising as a relaxation of difficult convex mixed integer quadratic programs (MIQP). We characterize the extreme points of our set and the extreme points of its continuous relaxation. We derive four quadratic cutting surfaces that improve the strength of the continuous relaxation. Each of the cutting surfaces … Read more

    Extended Formulations in Mixed Integer Conic Quadratic Programming

  • Iain Dunning
  • Joey Huchette
  • Juan Pablo Vielma
  • Miles Lubin
    • Categories (Mixed) Integer Nonlinear Programming

    In this paper we consider the use of extended formulations in LP-based algorithms for mixed integer conic quadratic programming (MICQP). Extended formulations have been used by Vielma, Ahmed and Nemhauser (2008) and Hijazi, Bonami and Ouorou (2013) to construct algorithms for MICQP that can provide a significant computational advantage. The first approach is based on … Read more

    Obtaining Lower Bounds from the Progressive Hedging Algorithm for Stochastic Mixed-Integer Programs

  • Dinakar Gade
  • Jean-Paul Watson
  • Gabriel Hackebeil
  • Sarah M. Ryan
  • Roger J.B. Wets
  • David L. Woodruff
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming

    We present a method for computing lower bounds in the Progressive Hedging Algorithm (PHA) for two-stage and multi-stage stochastic mixed-integer programs. Computing lower bounds in the PHA allows one to assess the quality of the solutions generated by the algorithm contemporaneously. The lower bounds can be computed in any iteration of the algorithm by using … Read more

    The Continuous Time Service Network Design Problem

  • Natashia Boland
  • Mike Hewitt
  • Luke Marshall
  • Martin Savelsbergh
    • Categories (Mixed) Integer Linear Programming, Transportation Tags , ,

    Consolidation carriers transport shipments that are small relative to trailer capacity. To be cost-effective, the carrier must consolidate shipments, which requires coordinating their paths in both space and time, i.e., the carrier must solve a Service Network Design problem. Most service network design models rely on discretization of time, i.e., instead of determining the exact … Read more

    Maximizing a class of submodular utility functions with constraints

  • Shabbir Ahmed
  • Jiajin Yu
    • Categories 0-1 Programming, Cutting Plane Approaches, Stochastic Programming Tags , , , ,

    Motivated by stochastic 0-1 integer programming problems with an expected utility objective, we study the mixed-integer nonlinear set: $P = \cset{(w,x)\in \reals \times \set{0,1}^N}{w \leq f(a’x + d), b’x \leq B}$ where $N$ is a positive integer, $f:\reals \mapsto \reals$ is a concave function, $a, b \in \reals^N$ are nonnegative vectors, $d$ is a real … Read more

    A Cycle-Based Formulation and Valid Inequalities for DC Power Transmission Problems with Switching

  • Santanu S. Dey
  • Hyemin Jeon
  • Burak Kocuk
  • Jeff Linderoth
  • James R. Luedtke
  • Xu Andy Sun
    • Categories Applications - Science and Engineering, Integer Programming Tags , ,

    It is well-known that optimizing network topology by switching on and off transmission lines improves the efficiency of power delivery in electrical networks. In fact, the USA Energy Policy Act of 2005 (Section 1223) states that the U.S. should “encourage, as appropriate, the deployment of advanced transmission technologies” including “optimized transmission line configurations”. As such, … Read more

    Some lower bounds on sparse outer approximations of polytopes

  • Santanu S. Dey
  • Andres Iroume
  • Marco Molinaro
    • Categories Integer Programming Tags ,

    Motivated by the need to better understand the properties of sparse cutting-planes used in mixed integer programming solvers, the paper [1] studied the idealized problem of how well a polytope is approximated by the use of sparse valid inequalities. As an extension to this work, we study the following “less idealized” questions in this pa- … Read more

    On the polyhedrality of cross and quadrilateral closures

  • Sanjeeb Dash
  • Oktay Gunluk
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Linear Programming Tags , ,

    Split cuts form a well-known class of valid inequalities for mixed-integer programming problems. Cook, Kannan and Schrijver (1990) showed that the split closure of a rational polyhedron $P$ is again a polyhedron. In this paper, we extend this result from a single rational polyhedron to the union of a finite number of rational polyhedra. We … Read more

    Certificates of Optimality and Sensitivity Analysis using Generalized Subadditive Generator Functions: A test study on Knapsack Problems

  • Kevin Cheung
  • Babak Moazzez
    • Categories (Mixed) Integer Linear Programming Tags , , , , , ,

    We introduce a family of subadditive functions called Generator Functions for mixed integer linear programs. These functions were previously defined for pure integer programs with non-negative entries by Klabjan [13]. They are feasible in the subadditive dual and we show that they are enough to achieve strong duality. Several properties of the functions are shown. … Read more