Optimization Online


Persistency of Linear Programming Formulations for the Stable Set Problem

Elisabeth Rodrı́guez-Heck(rodriguez-heck***at***or.rwth-aachen.de)
Karl Stickler(karl.stickler***at***rwth-aachen.de)
Matthias Walter(m.walter***at***utwente.nl)
Stefan Weltge(weltge***at***tum.de)

Abstract: 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 is defined by only non-negativity and edge constraints, a variety of stronger LP formulations have been studied and one may wonder whether any of them is persistent as well. We show that any stronger LP formulation that satisfies mild conditions cannot be persistent on all graphs, unless it is always equal to the stable-set polytope.

Keywords: linear programming, persistency, stable set

Category 1: Integer Programming (0-1 Programming )

Category 2: Combinatorial Optimization (Polyhedra )


Download: [PDF]

Entry Submitted: 11/05/2019
Entry Accepted: 11/05/2019
Entry Last Modified: 11/05/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society