pith. sign in

arxiv: 2605.01481 · v1 · submitted 2026-05-02 · 🧮 math.OC · cs.DM

On the redundancy of transitivity constraints in the clique partitioning problem

Noriyoshi Sukegawa This is my paper

Pith reviewed 2026-05-09 14:34 UTC · model grok-4.3

classification 🧮 math.OC cs.DM
keywords clique partitioningtransitivity constraintsredundancy0-1 integer linear programmingcorrelation clusteringfacet-definingpolytope
0
0 comments X

The pith

Certain transitivity constraints can be removed from the 0-1 ILP formulation of the clique partitioning problem without changing the optimal solution set.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper identifies a class of redundant transitivity constraints in the standard 0-1 integer linear programming formulation of the clique partitioning problem. These constraints can be removed without altering the optimal solutions, even though each one defines a facet of the associated polytope. The resulting smaller formulation proves particularly effective for correlation clustering instances that use edge weights from the set {-1, 1}. Computational tests demonstrate that this reduced model outperforms existing formulations on those instances.

Core claim

In the 0-1 integer linear programming formulation of the clique partitioning problem, a specific class of transitivity constraints is redundant. Removing them leaves the set of optimal solutions unchanged, although each constraint defines a facet of the polytope. This allows for a more compact formulation that works well for correlation clustering problems with binary edge weights.

What carries the argument

The class of redundant transitivity constraints identified for removal in the clique partitioning ILP formulation.

If this is right

  • The size of the ILP model decreases, which can speed up solution times.
  • The optimal solutions for clique partitioning remain the same after removal.
  • This is especially beneficial for correlation clustering instances with weights in {-1,1}.
  • Existing formulations can be improved by dropping these redundant constraints.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This redundancy suggests that similar simplifications might exist in other graph partitioning formulations.
  • Implementations of solvers for clustering problems could automatically detect and remove such constraints.
  • Further research might identify even larger redundant classes or apply this to weighted variants beyond {-1,1}.
  • The fact that facet-defining inequalities can be redundant points to interesting polyhedral properties worth exploring in related problems.

Load-bearing premise

The identified class of transitivity constraints is redundant for all instances of the clique partitioning problem, preserving the optimal solution set even after removal.

What would settle it

A concrete clique partitioning instance, such as one from correlation clustering, where the reduced formulation without the class of constraints produces an optimal solution different from the full formulation.

read the original abstract

In this study, we identify a class of redundant transitivity constraints in a 0-1 integer linear programming formulation of the clique partitioning problem. The transitivity constraints in this class can be removed from the formulation without changing the optimal solution set, although each transitivity constraint defines a facet of the associated polytope. This leads to a smaller formulation that is particularly effective for instances arising from correlation clustering, where edge weights are drawn from $\{-1,1\}$. Our computational experiments show that the resulting formulation outperforms existing formulations on such instances.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper identifies a class of transitivity constraints in the standard 0-1 ILP formulation of the clique partitioning problem that are redundant at integer feasible points (removable without changing the optimal solution set) while remaining facet-defining for the convex hull of those points. The resulting reduced formulation is claimed to be particularly effective for correlation clustering instances with edge weights in {-1,1}, with computational experiments showing outperformance relative to existing formulations.

Significance. If the redundancy result holds, the work offers a useful simplification of an important formulation in combinatorial optimization, highlighting that certain facet inequalities can be implied by the remaining constraints on {0,1}^n without being implied on the LP relaxation. This distinction has both theoretical value for polyhedral combinatorics and practical value for correlation clustering applications, where the smaller model size yields measurable computational gains in the reported experiments.

major comments (2)
  1. [§3, Theorem 1] §3, Theorem 1: the proof that the identified class of transitivity constraints is redundant for the 0-1 feasible set must be checked for completeness; it is unclear whether the argument covers all possible triangle configurations or only those satisfying additional structural assumptions on the underlying graph.
  2. [§5, Table 2] §5, Table 2: the reported speedups on {-1,1} instances are given only as aggregate ratios; without per-instance data on LP relaxation strength, number of branch-and-bound nodes, or comparison against the full transitivity formulation on the same solver settings, it is difficult to isolate the contribution of the redundancy reduction from other modeling choices.
minor comments (2)
  1. [Abstract] The abstract and introduction should explicitly name the 'existing formulations' used as baselines in the experiments.
  2. [§2 and §4] Notation for the transitivity inequalities (e.g., the indexing of triangles) should be introduced once and used consistently; occasional reuse of symbols for different index sets appears in §2 and §4.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive comments. We address each major comment below and have revised the manuscript to improve clarity and provide additional experimental details.

read point-by-point responses

  1. Referee: [§3, Theorem 1] §3, Theorem 1: the proof that the identified class of transitivity constraints is redundant for the 0-1 feasible set must be checked for completeness; it is unclear whether the argument covers all possible triangle configurations or only those satisfying additional structural assumptions on the underlying graph.

    Authors: The proof of Theorem 1 applies to an arbitrary triangle in the complete graph K_n that underlies the clique partitioning formulation; no additional structural assumptions on the graph are required. The argument proceeds by assuming an integer point violates the selected transitivity constraint and deriving a contradiction with the remaining constraints and the 0-1 bounds. To eliminate any ambiguity, we have added a short paragraph immediately after the proof that explicitly states the coverage for every triangle and includes a brief enumeration of the three possible ways an integer point can violate a transitivity inequality. revision: yes

  2. Referee: [§5, Table 2] §5, Table 2: the reported speedups on {-1,1} instances are given only as aggregate ratios; without per-instance data on LP relaxation strength, number of branch-and-bound nodes, or comparison against the full transitivity formulation on the same solver settings, it is difficult to isolate the contribution of the redundancy reduction from other modeling choices.

    Authors: We agree that aggregate ratios alone make it harder to isolate the effect of the redundancy reduction. In the revised version we have expanded the experimental section with a supplementary table that reports, for each {-1,1} instance, the LP relaxation value, the number of branch-and-bound nodes, and a side-by-side comparison against the full transitivity formulation run under identical solver settings and time limits. These additions allow direct assessment of the contribution of the reduced model. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper proves that a specific class of transitivity constraints is redundant for the integer feasible set of the 0-1 ILP formulation of clique partitioning (they are implied by the remaining constraints at all 0-1 points) while remaining facet-defining for the convex hull. This is a standard result in polyhedral combinatorics for incomplete extended formulations, where valid inequalities can be implied on the integer points without being implied on the LP relaxation. No self-definitional steps, fitted parameters renamed as predictions, load-bearing self-citations, or ansatzes smuggled via prior work appear; the derivation is a direct mathematical argument about implication and facet-defining properties that does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence of a standard 0-1 ILP formulation for clique partitioning that includes transitivity constraints and on the mathematical characterization of a subclass as redundant. No free parameters, new entities, or ad-hoc axioms beyond standard polyhedral combinatorics are introduced in the abstract.

axioms (1)
  • domain assumption The clique partitioning problem admits a standard 0-1 ILP formulation whose feasible region is defined in part by transitivity constraints.
    This is the base model assumed when identifying the redundant subclass.

pith-pipeline@v0.9.0 · 5375 in / 1261 out tokens · 28529 ms · 2026-05-09T14:34:11.125001+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Modularity-maximizing graph communities via mathematical programming

    Agarwal, G., Kempe, D., 2008. Modularity-maximizing graph communities via mathematical programming. The European Physical Journal B 66, 409–418

    work page 2008

  2. [2]

    Correlation clustering

    Bansal, N., Blum, A., Chawla, S., 2004. Correlation clustering. Machine learning 56, 89–113

    work page 2004

  3. [3]

    Optimal correlation clustering via maxsat, in: 2013 IEEE 13th international conference on data mining workshops, IEEE

    Berg, J., J¨ arvisalo, M., 2013. Optimal correlation clustering via maxsat, in: 2013 IEEE 13th international conference on data mining workshops, IEEE. pp. 750–757. 8

    work page 2013

  4. [4]

    Evaluation of ilp-based approaches for partitioning into colorful components, in: International symposium on experimental algorithms, Springer

    Bruckner, S., H¨ uffner, F., Komusiewicz, C., Niedermeier, R., 2013. Evaluation of ilp-based approaches for partitioning into colorful components, in: International symposium on experimental algorithms, Springer. pp. 176–187

    work page 2013

  5. [5]

    Toward optimal community detection: From trees to general weighted networks

    Dinh, T.N., Thai, M.T., 2015. Toward optimal community detection: From trees to general weighted networks. Internet Mathematics 11, 181–200

    work page 2015

  6. [6]

    A cutting plane algorithm for a clustering problem

    Gr¨ otschel, M., Wakabayashi, Y., 1989. A cutting plane algorithm for a clustering problem. Mathematical Programming 45, 59–96

    work page 1989

  7. [7]

    Facets of the clique partitioning polytope

    Gr¨ otschel, M., Wakabayashi, Y., 1990. Facets of the clique partitioning polytope. Mathematical Programming 47, 367–387

    work page 1990

  8. [8]

    New bounds and constraint propagation techniques for the clique partitioning problem

    Jaehn, F., Pesch, E., 2013. New bounds and constraint propagation techniques for the clique partitioning problem. Discrete Applied Mathematics 161, 2025–2037

    work page 2013

  9. [9]

    Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement

    Ji, X., Mitchell, J.E., 2007. Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement. Discrete Optimization 4, 87–102

    work page 2007

  10. [10]

    Concise integer linear programming formulation for clique partitioning problems

    Koshimura, M., Watanabe, E., Sakurai, Y., Yokoo, M., 2022. Concise integer linear programming formulation for clique partitioning problems. Constraints 27, 99–115

    work page 2022

  11. [11]

    A separation algorithm for the clique partitioning problem, in: International Symposium on Combinatorial Optimization (ISCO)

    Letchford, A.N., Sørensen, M.M., 2024. A separation algorithm for the clique partitioning problem, in: International Symposium on Combinatorial Optimization (ISCO)

    work page 2024

  12. [12]

    New facets of the clique partitioning polytope

    Letchford, A.N., Sørensen, M.M., 2025. New facets of the clique partitioning polytope. Operations Research Letters 59, 107242

    work page 2025

  13. [13]

    Computing an upper bound of modularity

    Miyauchi, A., Miyamoto, Y., 2013. Computing an upper bound of modularity. The European Physical Journal B 86, 302

    work page 2013

  14. [14]

    Exact clustering via integer programming and maximum satisfiability, in: Proceedings of the AAAI conference on artificial intelligence

    Miyauchi, A., Sonobe, T., Sukegawa, N., 2018. Exact clustering via integer programming and maximum satisfiability, in: Proceedings of the AAAI conference on artificial intelligence

    work page 2018

  15. [15]

    Redundant constraints in the standard formulation for the clique partitioning problem

    Miyauchi, A., Sukegawa, N., 2015. Redundant constraints in the standard formulation for the clique partitioning problem. Optimization Letters 9, 199–207

    work page 2015

  16. [16]

    Finding and evaluating community structure in networks

    Newman, M.E.J., Girvan, M., 2004. Finding and evaluating community structure in networks. Physical Review E 69, 026113

    work page 2004

  17. [17]

    Nowozin, S., Jegelka, S., 2009. Solution stability in linear programming relaxations: Graph partitioning and unsupervised learning, in: Proceedings of the 26th Annual International Conference on Machine Learning, pp. 769–776

    work page 2009

  18. [18]

    The clique partitioning problem: facets and patching facets

    Oosten, M., Rutten, J.H., Spieksma, F.C., 2001. The clique partitioning problem: facets and patching facets. Networks: An International Journal 38, 209–226

    work page 2001

  19. [19]

    The branch and cut method for the clique partitioning problem

    Simanchev, R.Y., Urazova, I.V., Kochetov, Y.A., 2019. The branch and cut method for the clique partitioning problem. Journal of Applied and Industrial Mathematics 13, 539–556

    work page 2019

  20. [20]

    Lagrangian relaxation and pegging test for the clique partitioning problem

    Sukegawa, N., Yamamoto, Y., Zhang, L., 2013. Lagrangian relaxation and pegging test for the clique partitioning problem. Advances in Data Analysis and Classification 7, 363–391

    work page 2013

  21. [21]

    Correlation clustering for crosslingual link detection., in: IJCAI, pp

    Van Gael, J., Zhu, X., 2007. Correlation clustering for crosslingual link detection., in: IJCAI, pp. 1744–1749

    work page 2007

  22. [22]

    Approximating symmetric relations by equivalence relations

    Zahn, C.T., 1964. Approximating symmetric relations by equivalence relations. SIAM Journal on Applied Mathematics 12, 840–847. 9

    work page 1964