The generalized independent set problem: polyhedral analysis and solution approaches

DOI10.1016/J.EJOR.2016.11.050MaRDI QIDQ1753398zbMATH OpenOpenAlexFDO

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

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

0-1 quadratic programmingcombinatorial optimizationfacetsgeneralized independent setGRASP tabu search

Mathematics Subject Classification ID

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

Recommendations

• Algorithms for the generalized independent set problem based on a quadratic optimization approach
• An effective modeling and solution approach for the generalized independent set problem
• An unconstrained binary quadratic programming for the maximum independent set problem
• A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere
• Simple and fast surrogate constraint heuristics for the maximum independent set problem

Cites work

• A branch-and-price approach for the maximum weight independent set problem
• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• A unified modeling and solution framework for combinatorial optimization problems
• An effective modeling and solution approach for the generalized independent set problem
• An exact algorithm for the maximum stable set problem
• Computing maximum stable sets for distance-hereditary graphs
• Exact Algorithms for Maximum Independent Set
• scientific article; zbMATH DE number 2079894 (Why is no real title available?)
• scientific article; zbMATH DE number 939919 (Why is no real title available?)
• Maximum stable set formulations and heuristics based on continuous optimization
• On balanced graphs
• On the facial structure of set packing polyhedra
• Probabilistic GRASP-tabu search algorithms for the UBQP problem
• Properties of vertex packing and independence system polyhedra

Cited in

(8)

• Polyhedral properties of the induced cluster subgraphs
• Learning pseudo-backdoors for mixed integer programs
• Algorithms for the generalized independent set problem based on a quadratic optimization approach
• An effective modeling and solution approach for the generalized independent set problem
• A sufficient condition to extend polynomial results for the maximum independent set problem
• Exact and heuristic solution approaches for the generalized independent set problem
• Algorithms for the global domination problem
• Machine learning augmented branch and bound for mixed integer linear programming

Describes a project that uses

Uses Software

• Max-AO
• DIMACS

This page was built for publication: The generalized independent set problem: polyhedral analysis and solution approaches

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