Solving Clique Partitioning Problems: A Comparison of Models and Commercial Solvers

Yu Du, Gary Kochenberger, Fred Glover, Haibo Wang, Mark Lewis, Weihong Xie and Takeshi Tsuyuguchi
Additional contact information
Yu Du: University of Colorado at Denver, USA
Gary Kochenberger: University of Colorado at Denver, USA
Fred Glover: ��University of Colorado at Boulder, USA
Haibo Wang: ��Texas A&M International University, USA
Mark Lewis: �Missouri State University, USA
Weihong Xie: �Guangdong University of Technology, P. R. China
Takeshi Tsuyuguchi: ��Texas A&M International University, USA

International Journal of Information Technology & Decision Making (IJITDM), 2022, vol. 21, issue 01, 59-81

Abstract: Finding good solutions to clique partitioning problems remains a computational challenge. With rare exceptions, finding optimal solutions for all but small instances is not practically possible. However, choosing the most appropriate modeling structure can have a huge impact on what is practical to obtain from exact solvers within a reasonable amount of run time. Commercial solvers have improved tremendously in recent years and the combination of the right solver and the right model can significantly increase our ability to compute acceptable solutions to modest-sized problems with solvers like CPLEX, GUROBI and XPRESS. In this paper, we explore and compare the use of three commercial solvers on modest sized test problems for clique partitioning. For each problem instance, a conventional linear model from the literature and a relatively new quadratic model are compared. Extensive computational experience indicates that the quadratic model outperforms the classic linear model as problem size grows.

Keywords: Clique partitioning; combinatorial optimization; quadratic integer programming (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219622021500504
Access to full text is restricted to subscribers

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:wsi:ijitdm:v:21:y:2022:i:01:n:s0219622021500504

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219622021500504

Access Statistics for this article

International Journal of Information Technology & Decision Making (IJITDM) is currently edited by Yong Shi

More articles in International Journal of Information Technology & Decision Making (IJITDM) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().