Solving the Minimum Sum Coloring Problem: Alternative Models, Exact Solvers, and Metaheuristics

Yu Du (), Fred Glover (), Gary Kochenberger (), Rick Hennig (), Haibo Wang () and Amit Hulandageri ()
Additional contact information
Yu Du: Business School, University of Colorado Denver, Denver, Colorado 80102
Fred Glover: Entanglement, Inc., Boulder, Colorado 80305
Gary Kochenberger: Entanglement, Inc., Boulder, Colorado 80305
Rick Hennig: Entanglement, Inc., Boulder, Colorado 80305
Haibo Wang: Sanchez School of Business, Texas A&M International University, Laredo, Texas 78040
Amit Hulandageri: Entanglement, Inc., Boulder, Colorado 80305

INFORMS Journal on Computing, 2025, vol. 37, issue 2, 199-211

Abstract: The minimum sum coloring problem (MSCP), a well-known NP-hard (nondeterministic polynomial time) problem with important practical applications, has been the subject of several papers in recent years. Because of the computational challenge posed by these problems, most solution methods employed are metaheuristics designed to find high-quality solutions with no guarantee of optimality. Exact methods (like Gurobi) and metaheuristic solvers have greatly improved in recent years, enabling high-quality and often optimal solutions to be found to a growing set of MSCPs. Alternative model forms can have a significant impact on the success of exact and heuristic methods in such settings, often providing enhanced performance compared with traditional model forms. In this paper, we introduce several alternative models for MSCP, including the quadratic unconstrained binary problem plus (QUBO-Plus) model for solving problems with constraints that are not folded into the objective function of the basic quadratic unconstrained binary problem (QUBO) model. We provide a computational study using a standard set of test problems from the literature that compares the general purpose exact solver from Gurobi with the leading QUBO metaheuristic solver NGQ and a special solver called Q-Card that belongs to the QUBO-Plus class. Our results highlight the effectiveness of the QUBO and QUBO-Plus models when solved with these metaheuristic solvers on this test bed, showing that the QUBO-Plus solver Q-Card provides the best performance for finding high-quality solutions to these important problems.

Keywords: minimum sum coloring problem; metaheuristics; combinatorial optimization; quadratic unconstrained binary optimization; constraint programming (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0334 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:2:p:199-211

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().