Persistency of linear programming relaxations for the stable set problem

DOI10.1007/S10107-020-01600-3MaRDI QIDQ2118136zbMATH OpenOpenAlexFDO

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

Publication date 22 March 2022

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

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

zbMATH Keywords

standard linear programmingpersistency

Mathematics Subject Classification ID

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

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.

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 DE number 4145658

Cites work

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

Cited in

(3)

• Persistency in 0-1 polynomial programming
• Persistency of linear programming relaxations for the stable set problem
• Neighborhood persistency of the linear optimization relaxation of integer linear optimization

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)