The generalized independent set problem: polyhedral analysis and solution approaches

DOI10.1016/j.ejor.2016.11.050zbMath1402.90141OpenAlexW2558758145MaRDI QIDQ1753398

Marco Colombi, Renata Mansini, Savelsbergh, Martin W. P.

Publication date: 29 May 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2016.11.050

zbMATH Keywords

combinatorial optimization0-1 quadratic programmingfacetsgeneralized independent setGRASP tabu search

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Learning pseudo-backdoors for mixed integer programs, Polyhedral properties of the induced cluster subgraphs, Algorithms for the generalized independent set problem based on a quadratic optimization approach

Uses Software

• Max-AO
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Probabilistic GRASP-tabu search algorithms for the UBQP problem
• An exact algorithm for the maximum stable set problem
• Maximum stable set formulations and heuristics based on continuous optimization
• A unified modeling and solution framework for combinatorial optimization problems
• An effective modeling and solution approach for the generalized independent set problem
• Computing maximum stable sets for distance-hereditary graphs
• On balanced graphs
• Exact Algorithms for Maximum Independent Set
• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• Properties of vertex packing and independence system polyhedra
• On the facial structure of set packing polyhedra
• A branch-and-price approach for the maximum weight independent set problem