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

combinatorial optimizationfacets0-1 quadratic programminggeneralized 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)

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

• scientific article; zbMATH DE number 2079894 (Why is no real title available?)
• scientific article; zbMATH DE number 939919 (Why is no real title available?)
• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• A branch-and-price approach for the maximum weight independent set problem
• 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
• 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

(6)

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

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)