Persistency of linear programming relaxations for the stable set problem

DOI10.1007/S10107-020-01600-3zbMATH Open1489.90162arXiv1911.01478OpenAlexW3120503500MaRDI QIDQ2118136FDOQ2118136

Elisabeth Rodríguez-Heck, Stefan Weltge, Karl Stickler, Matthias Walter

Publication date: 22 March 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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 other LP formulations have been studied and one may wonder whether any of them has this property as well. We show that any other formulation that satisfies mild conditions cannot have the persistency property on all graphs, unless it is always equal to the stable set polytope.

Full work available at URL: https://arxiv.org/abs/1911.01478

Recommendations

• Persistency of linear programming relaxations for the stable set problem
• Stability of efficient solutions to set optimization problems
• On the stability of the feasible set in linear optimization
• Stability of linear vector optimization problems corresponding to an efficient set
• Stability in linear programming models: An index set approach
• Stability in disjunctive linear optimization I: continuity of the feasible set
• scientific article; zbMATH DE number 1738576
• On the Stability of the Feasible Set in Optimization Problems
• On essential stable sets of solutions in set optimization problems
• scientific article

zbMATH Keywords

standard linear programmingpersistency

Mathematics Subject Classification ID

Linear programming (90C05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• A class of facet producing graphs for vertex packing polyhedra
• On certain polytopes associated with graphs
• On the facial structure of set packing polyhedra
• Minimum node covers and 2-bicritical graphs
• Vertex packings: Structural properties and algorithms
• Clique family inequalities for the stable set polytope of quasi-line graphs.
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
• Random near-regular graphs and the node packing problem
• An exact threshold theorem for random graphs and the node-packing problem
• Vertices Belonging to All or to No Maximum Stable Sets of a Graph
• On the integer-valued variables in the linear vertex packing problem
• On Linear Characterizations of Combinatorial Optimization Problems

Cited In (2)

• Persistency of Linear Programming Relaxations for the Stable Set Problem
• Persistency in 0-1 polynomial programming

This page was built for publication: Persistency of linear programming relaxations for the stable set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118136)