Integer Programming

Computational Optimization of Gas Compressor Stations: MINLP Models vs. Continuous Reformulations

  • Daniel Rose
  • Martin Schmidt
  • Marc C. Steinbach
  • Bernhard M. Willert
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Nonlinear Optimization Tags , , , ,

    When considering cost-optimal operation of gas transport networks, compressor stations play the most important role. Proper modeling of these stations leads to complicated mixed-integer nonlinear and nonconvex optimization problems. In this article, we give an isothermal and stationary description of compressor stations, state MINLP and GDP models for operating a single station, and discuss several … Read more

    Separation of Generic Cutting Planes in Branch-and-Price Using a Basis

  • Marco E. Lübbecke
  • Jonas T. Witt
    • Categories Branch and Cut Algorithms, Integer Programming, Optimization Software and Modeling Systems

    Dantzig-Wolfe reformulation of a mixed integer program partially convexifies a subset of the constraints, i.e., it implicitly adds all valid inequalities for the associated integer hull. Projecting an optimal basic solution of the reformulation’s LP relaxation to the original space does is in general not yield a basic solution of the original LP relaxation. Cutting … Read more

    An Overview on Mathematical Programming Approaches for the Deterministic Unit Commitment Problem in Hydro Valleys

  • Claudia D'Ambrosio
  • Raouia Taktak
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences Tags , , ,

    With the fast-growing demand in the electricity market of the last decades, attention has been focused on alternative and flexible sources of energy such as hydro valleys. Managing the hydroelectricity produced by the plants in hydro valleys is called the hydro unit commitment problem. This problem consists in finding the optimal power production schedule of … Read more

    A polyhedral study of binary polynomial programs

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization

    We study the polyhedral convex hull of a mixed-integer set S defined by a collection of multilinear equations over the 0-1-cube. Such sets appear frequently in the factorable reformulation of mixed-integer nonlinear optimization problems. In particular, the set S represents the feasible region of a linearized unconstrained binary polynomial optimization problem. We define an equivalent … Read more

    A Fast Branch-and-Bound Algorithm for Non-convex Quadratic Integer Optimization Subject To Linear Constraints Using Ellipsoidal Relaxations

  • Christoph Buchheim
  • Marianna De Santis
  • Laura Palagi
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Quadratic Programming

    We propose two exact approaches for non-convex quadratic integer minimization subject to linear constraints where lower bounds are computed by considering ellipsoidal relaxations of the feasible set. In the first approach, we intersect the ellipsoids with the feasible linear subspace. In the second approach we penalize exactly the linear constraints. We investigate the connection between … Read more

    A Polyhedral Study of Two-Period Relaxations for Big-Bucket Lot-Sizing Problems: Zero Setup Case

  • Kerem Akartunali
  • Mahdi Doostmohammadi
    • Categories Integer Programming, Polyhedra, Production and Logistics

    In this paper, we investigate the two-period subproblems proposed by Akartunal{\i} et al. (2014) for big-bucket lot-sizing problems, which have shown a great potential for obtaining strong bounds for these problems. In particular, we study the polyhedral structure of the mixed integer sets related to two relaxations of these subproblems for the special case of … Read more

    Lower bounding procedure for the Asymmetric Quadratic Traveling Salesman Problem

  • Pietro Belotti
  • Stefano Gualandi
  • Federico Malucelli
  • Borzou Rostami
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Quadratic Programming Tags , , , ,

    In this paper we consider the Asymmetric Quadratic Traveling Salesman Problem. Given a directed graph and a function that maps every pair of consecutive arcs to a cost, the problem consists in finding a cycle that visits every vertex exactly once and such that the sum of the costs is minimum. We propose an extended … Read more

    Submodular Minimization in the Context of Modern LP and MILP Methods and Solvers

  • Jon Lee
  • Siqian Shen
  • Andrew Orso
    • Categories 0-1 Programming, Combinatorial Optimization, Linear Programming Tags , , , ,

    We consider the application of mixed-integer linear programming (MILP) solvers to the minimization of submodular functions. We evaluate common large-scale linear-programming (LP) techniques (e.g., column generation, row generation, dual stabilization) for solving a LP reformulation of the submodular minimization (SM) problem. We present heuristics based on the LP framework and a MILP solver. We evaluated … Read more

    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