stable set

The Impact of Symmetry Handling for the Stable Set Problem via Schreier-Sims Cuts

  • Christopher Hojny
  • Marc E. Pfetsch
  • José Verschae
    • Categories Integer Programming Tags , , ,

    Symmetry handling inequalities (SHIs) are an appealing and popular tool for handling symmetries in integer programming. Despite their practical application, little is known about their interaction with optimization problems. This article focuses on Schreier-Sims (SST) cuts, a recently introduced family of SHIs, and investigate their impact on the computational and polyhedral complexity of optimization problems. … Read more

    Schreier-Sims Cuts meet Stable Set: Preserving Problem Structure when Handling Symmetries

  • Christopher Hojny
  • Marc E. Pfetsch
  • José Verschae
    • Categories 0-1 Programming Tags , ,

    Symmetry handling inequalities (SHIs) are a popular tool to handle symmetries in integer programming. Despite their successful application in practice, only little is known about the interaction of SHIs with optimization problems. In this article, we focus on SST cuts, an attractive class of SHIs, and investigate their computational and polyhedral consequences for optimization problems. … Read more

    Dynamic Node Packing

  • Christopher Muir
  • Alejandro Toriello
    • Categories Combinatorial Optimization, Dynamic Programming, Polyhedra Tags , , , ,

    We propose a dynamic version of the classical node packing problem, also called the stable set or independent set problem. The problem is defined by a node set, a node weight vector, and an edge probability vector. For every pair of nodes, an edge is present or not according to an independent Bernoulli random variable … Read more

    Persistency of Linear Programming Formulations for the Stable Set Problem

  • Elisabeth Rodriguez-Heck
  • Matthias Walter
  • Karl Stickler
  • Stefan Weltge
    • Categories 0-1 Programming, Polyhedra Tags , ,

    The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP … Read more

    A smaller extended formulation for the odd cycle inequalities of the stable set polytope

  • Sven de Vries
  • Bernd Perscheid
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Graphs and Matroids Tags , , , ,

    For sparse graphs, the odd cycle polytope can be used to compute useful bounds for the maximum stable set problem quickly. Yannakakis introduced an extended formulation for the odd cycle inequalities of the stable set polytope in 1991, which provides a direct way to optimize over the odd cycle polytope in polynomial time, although there … Read more

    Solving Vertex Coloring Problems as Maximum Weight Stable Set Problems

  • Denis Cornaz
  • Fabio Furini
  • Enrico Malaguti
    • Categories Graphs and Matroids, Integer Programming Tags , , ,

    In Vertex Coloring Problems, one is required to assign a color to each vertex of an undirected graph in such a way that adjacent vertices receive different colors, and the objective is to minimize the cost of the used colors. In this work we solve four different coloring problems formulated as Maximum Weight Stable Set … Read more

    A branch and cut algorithm for minimum spanning trees under conflict constraints

  • Phillippe Samer
  • Sebastián Urrutia
    • Categories 0-1 Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , , ,

    We study approaches for the exact solution of the \NP–hard minimum spanning tree problem under conflict constraints. Given a graph $G(V,E)$ and a set $C \subset E \times E$ of conflicting edge pairs, the problem consists of finding a conflict-free minimum spanning tree, i.e. feasible solutions are allowed to include at most one of the … Read more

    How tight is the corner relaxation? Insights gained from the stable set problem

  • Gérard Cornuéjols
  • Carla Michini
  • Giacomo Nannicini
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra Tags , ,

    The corner relaxation of a mixed-integer linear program is a central concept in cutting plane theory. In a recent paper Fischetti and Monaci provide an empirical assessment of the strength of the corner and other related relaxations on benchmark problems. In this paper we give a precise characterization of the bounds given by these relaxations … Read more

    Interdiction Branching

  • Andrea Lodi
  • Ted K. Ralphs
  • Fabrizio Rossi
  • Stefano Smriglio
    • Categories 0-1 Programming, Branch and Cut Algorithms Tags , , , , , ,

    This paper introduces interdiction branching, a new branching method for binary integer programs that is designed to overcome the difficulties encountered in solving problems for which branching on variables is inherently weak. Unlike traditional methods, selection of the disjunction in interdiction branching takes into account the best feasible solution found so far. In particular, the … Read more