New facets of the clique partitioning polytope

Adam N. Letchford; Michael Malmros Sørensen

doi:10.1016/j.orl.2025.107242

New facets of the clique partitioning polytope

Adam N. Letchford^*, Michael Malmros Sørensen

^*Corresponding author for this work

Department of Economics and Business Economics

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

Abstract

The clique partitioning problem is a combinatorial optimisation problem which has many applications. At present, the most promising exact algorithms are those that are based on an understanding of the associated polytope. We present two new families of valid inequalities for that polytope, and show that the inequalities define facets under certain conditions.

Original language	English
Article number	107242
Journal	Operations Research Letters
Volume	59
Number of pages	4
ISSN	0167-6377
DOIs	https://doi.org/10.1016/j.orl.2025.107242
Publication status	Published - Mar 2025

Keywords

Clique partitioning problem
Combinatorial optimisation
Polyhedral combinatorics

Access to Document

10.1016/j.orl.2025.107242Licence: CC BY

Cite this

@article{da12a1f943704795a8736acd641d03d9,

title = "New facets of the clique partitioning polytope",

abstract = "The clique partitioning problem is a combinatorial optimisation problem which has many applications. At present, the most promising exact algorithms are those that are based on an understanding of the associated polytope. We present two new families of valid inequalities for that polytope, and show that the inequalities define facets under certain conditions.",

keywords = "Clique partitioning problem, Combinatorial optimisation, Polyhedral combinatorics",

author = "Letchford, {Adam N.} and S{\o}rensen, {Michael Malmros}",

year = "2025",

month = mar,

doi = "10.1016/j.orl.2025.107242",

language = "English",

volume = "59",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - New facets of the clique partitioning polytope

AU - Letchford, Adam N.

AU - Sørensen, Michael Malmros

PY - 2025/3

Y1 - 2025/3

N2 - The clique partitioning problem is a combinatorial optimisation problem which has many applications. At present, the most promising exact algorithms are those that are based on an understanding of the associated polytope. We present two new families of valid inequalities for that polytope, and show that the inequalities define facets under certain conditions.

AB - The clique partitioning problem is a combinatorial optimisation problem which has many applications. At present, the most promising exact algorithms are those that are based on an understanding of the associated polytope. We present two new families of valid inequalities for that polytope, and show that the inequalities define facets under certain conditions.

KW - Clique partitioning problem

KW - Combinatorial optimisation

KW - Polyhedral combinatorics

UR - http://www.scopus.com/inward/record.url?scp=85215429607&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2025.107242

DO - 10.1016/j.orl.2025.107242

M3 - Journal article

SN - 0167-6377

VL - 59

JO - Operations Research Letters

JF - Operations Research Letters

M1 - 107242

ER -

New facets of the clique partitioning polytope

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this