Simple and fast surrogate constraint heuristics for the maximum independent set problem

DOI10.1007/s10732-007-9054-yzbMath1173.90557OpenAlexW1971556879MaRDI QIDQ1009195

Bahram Alidaee, Haibo Wang, Gary A. Kochenberger

Publication date: 31 March 2009

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10732-007-9054-y

zbMATH Keywords

HeuristicsMaximum independent setSurrogate constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (3)

Iterated local search with Trellis-neighborhood for the partial Latin square extension problem ⋮ On zero duality gap in surrogate constraint optimization: the case of rational-valued functions of constraints ⋮ Zero duality gap in surrogate constraint optimization: a concise review of models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact search for the solution of the surrogate dual of the 0-1 bidimensional knapsack problem
• Tutorial on surrogate constraint approaches for optimization in graphs
• A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere
• Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions
• Using critical sets to solve the maximum independent set problem
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• Surrogate Constraint Duality in Mathematical Programming
• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• Surrogate Mathematical Programming

This page was built for publication: Simple and fast surrogate constraint heuristics for the maximum independent set problem