0-1 Programming

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

    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

    Risk Averse Shortest Path Interdiction

  • Siqian Shen
  • Yongjia Song
    • Categories 0-1 Programming, Network Optimization, Stochastic Programming

    We consider a Stackelberg game in a network, where a leader minimizes the cost of interdicting arcs and a follower seeks the shortest distance between given origin and destination nodes under uncertain arc traveling cost. In particular, we consider a risk-averse leader, who aims to keep high probability that the follower’s traveling distance is longer … Read more

    Min-max-min Robust Combinatorial Optimization Subject to Discrete Uncertainty

  • Christoph Buchheim
  • Jannis Kurtz
    • Categories 0-1 Programming, Combinatorial Optimization, Robust Optimization Tags , ,

    We consider combinatorial optimization problems with uncertain objective functions. In the min-max-min robust optimization approach, a fixed number k of feasible solutions is computed such that the respective best of them is optimal in the worst case. The idea is to calculate a set of candidate solutions in a potentially expensive preprocessing and then select … Read more

    Parallel Scenario Decomposition of Risk Averse 0-1 Stochastic Programs

  • Shabbir Ahmed
  • Yan Deng
  • Siqian Shen
    • Categories 0-1 Programming, Parallel Algorithms, Stochastic Programming

    In this paper, we extend a recently proposed scenario decomposition algorithm (Ahmed (2013)) for risk-neutral 0-1 stochastic programs to the risk-averse setting. Specifically, we consider risk-averse 0-1 stochastic programs with objective functions based on coherent risk measures. Using a dual representation of a coherent risk measure, we first derive an equivalent minimax reformulation of the … Read more

    The Strength of Dantzig-Wolfe Reformulations for the Stable Set and Related Problems

  • Marco E. Lübbecke
  • Jonas T. Witt
    • Categories 0-1 Programming, Polyhedra

    Dantzig-Wolfe reformulation of an integer program convexifies a subset of the constraints, which yields an extended formulation with a potentially stronger linear programming (LP) relaxation. We would like to better understand the strength of such reformulations in general. As a first step we investigate the classical edge formulation for the stable set problem. We characterize … Read more

    hBcnorm regularization algorithms for optimization over permutation matrices

  • Bo Jiang
  • Ya-Feng Liu
  • Zaiwen Wen
    • Categories 0-1 Programming, Constrained Nonlinear Optimization Tags , , , , , ,

    Optimization problems over permutation matrices appear widely in facility layout, chip design, scheduling, pattern recognition, computer vision, graph matching, etc. Since this problem is NP-hard due to the combinatorial nature of permutation matrices, we relax the variable to be the more tractable doubly stochastic matrices and add an $L_p$-norm ($0 < p < 1$) regularization ... Read more

    Totally Unimodular Congestion Games

  • Alberto Del Pia
  • Michael C. Ferris
  • Carla Michini
    • Categories 0-1 Programming, Game Theory, Polyhedra Tags , ,

    We investigate a new class of congestion games, called Totally Unimodular Congestion Games, in which the strategies of each player are expressed as binary vectors lying in a polyhedron defined using a totally unimodular constraint matrix and an integer right-hand side. We study both the symmetric and the asymmetric variants of the game. In the … Read more

    Rank aggregation in cyclic sequences

  • Javier Alcaraz
  • Eva García-Nove
  • Mercedes Landete
  • Juan F. Monge
  • Justo Puerto
    • Categories 0-1 Programming, Combinatorial Optimization Tags ,

    In this paper we propose the problem of finding the cyclic sequence which best represents a set of cyclic sequences. Given a set of elements and a precedence cost matrix we look for the cyclic sequence of the elements which is at minimum distance from all the ranks when the permutation metric distance is the … Read more

    A new family of facet defining inequalities for the maximum edge-weighted clique problem

  • Franklin Djeumou Fomeni
    • Categories 0-1 Programming, Combinatorial Optimization, Cutting Plane Approaches Tags , , , , ,

    This paper considers a family of cutting planes, recently developed for mixed 0-1 polynomial programs and shows that they define facets for the maximum edge-weighted clique problem. There exists a polynomial time exact separation algorithm for these in- equalities. The result of this paper may contribute to the development of more efficient algorithms for the … Read more