Integer Programming

Combining Progressive Hedging with a Frank-Wolfe Method to Compute Lagrangian Dual Bounds in Stochastic Mixed-Integer Programming

  • Natashia Boland
  • Brian Dandurand
  • Andrew C. Eberhard
  • Jeff Linderoth
  • James R. Luedtke
  • Fabricio Oliveira
  • Jeffrey Christiansen
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , ,

    We present a new primal-dual algorithm for computing the value of the Lagrangian dual of a stochastic mixed-integer program (SMIP) formed by relaxing its nonanticipativity constraints. The algorithm relies on the well-known progressive hedging method, but unlike previous progressive hedging approaches for SMIP, our algorithm can be shown to converge to the optimal Lagrangian dual … Read more

    Matroid Optimisation Problems with Nested Non-linear Monomials in the Objective Function

  • Anja Fischer
  • Frank Fischer
  • S. Thomas McCormick
    • Categories 0-1 Programming, Graphs and Matroids, Polyhedra Tags , , , , ,

    Recently, Buchheim and Klein suggested to study polynomial-time solvable optimisation problems with linear objective functions combined with exactly one additional quadratic monomial. They concentrated on special quadratic spanning tree or forest problems. We extend their results to general matroid optimisation problems with a set of nested monomials in the objective function. The monomials are linearised … Read more

    Monoidal Cut Strengthening and Generalized Mixed-Integer Rounding for Disjunctions and Complementarity Constraints

  • Tobias Fischer
  • Marc E. Pfetsch
    • Categories Integer Programming Tags , , ,

    In the early 1980s, Balas and Jeroslow presented monoidal disjunctive cuts exploiting the integrality of variables. This article investigates the relation of monoidal cut strengthening to other classes of cutting planes for general two-term disjunctions. We introduce a generalization of mixed-integer rounding cuts and show equivalence to monoidal disjunctive cuts. Moreover, we demonstrate the effectiveness … Read more

    Minimization and Maximization Versions of the Quadratic Traveling Salesman Problem

  • Oswin Aichholzer
  • Anja Fischer
  • Frank Fischer
  • J. Fabian Meier
  • Ulrich Pferschy
  • Alexander Pilz
  • Rostislav Stanek
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    The traveling salesman problem (TSP) asks for a shortest tour through all vertices of a graph with respect to the weights of the edges. The symmetric quadratic traveling salesman problem (SQTSP) associates a weight with every three vertices traversed in succession. If these weights correspond to the turning angles of the tour, we speak of … Read more

    Computational study of valid inequalities for the maximum hBccut problem

  • Miguel F. Anjos
  • Sébastien Le Digabel
  • Vilmar Jefté Rodrigues de Sousa
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Semi-definite Programming Tags , , ,

    We consider the maximum k-cut problem that consists in partitioning the vertex set of a graph into k subsets such that the sum of the weights of edges joining vertices in different subsets is maximized. We focus on identifying effective classes of inequalities to tighten the semidefinite programming relaxation. We carry out an experimental study … Read more

    On quantile cuts and their closure for chance constrained optimization problems

  • Shabbir Ahmed
  • Weijun Xie
    • Categories Cutting Plane Approaches, Stochastic Programming Tags , ,

    A chance constrained optimization problem over a finite distribution involves a set of scenario constraints from which a small subset can be violated. We consider the setting where all scenario constraints are mixed-integer convex. Existing works typically consider a mixed integer nonlinear programming (MINLP) formulation of this problem by introducing binary variables to indicate which … Read more

    Optimization Driven Scenario Grouping

  • Shabbir Ahmed
  • Santanu S. Dey
  • Deepak Rajan
  • Kevin Ryan
    • Categories 0-1 Programming, Stochastic Programming Tags ,

    Scenario decomposition algorithms for stochastic programs compute bounds by dualizing all nonanticipativity constraints and solving individual scenario problems independently. We develop an approach that improves upon these bounds by re-enforcing a carefully chosen subset of nonanticipativity constraints, effectively placing scenarios into ‘groups’. Specifically, we formulate an optimization problem for grouping scenarios that aims to improve … Read more

    The SCIP Optimization Suite 3.2

  • Tobias Fischer
  • Tristan Gally
  • Gerald Gamrath
  • Ambros Gleixner
  • Gregor Hendel
  • Thorsten Koch
  • Stephen J. Maher
  • Matthias Miltenberger
  • Marc E. Pfetsch
  • Felipe Serrano
  • Dieter Weninger
  • Jakob Witzig
  • Benjamin Müller
  • Christian Puchert
  • Daniel Rehfeldt
  • Sebastian Schenker
  • Robert Schwarz
  • Yuji Shinano
  • Stefan Vigerske
  • Michael Winkler
  • Jonas T. Witt
    • Categories Integer Programming, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems

    The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic … Read more

    Three Enhancements for Optimization-Based Bound Tightening

  • Timo Berthold
  • Ambros Gleixner
  • Benjamin Müller
  • Stefan Weltge
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Nonlinear Optimization Tags , , , , ,

    Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper … Read more

    A coordinate ascent method for solving semidefinite relaxations of non-convex quadratic integer programs

  • Christoph Buchheim
  • Maribel Montenegro
  • Angelika Wiegele
    • Categories Integer Programming, Semi-definite Programming Tags , ,

    We present a coordinate ascent method for a class of semidefinite programming problems that arise in non-convex quadratic integer optimization. These semidefinite programs are characterized by a small total number of active constraints and by low-rank constraint matrices. We exploit this special structure by solving the dual problem, using a barrier method in combination with … Read more