On the redundancy of transitivity constraints in the clique partitioning problem
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911640523374592 |
|---|---|
| author | Sukegawa, Noriyoshi |
| author_facet | Sukegawa, Noriyoshi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_01481 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the redundancy of transitivity constraints in the clique partitioning problem Sukegawa, Noriyoshi Optimization and Control Discrete Mathematics 90C10, 90C27, 05C85 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. |
| title | On the redundancy of transitivity constraints in the clique partitioning problem |
| topic | Optimization and Control Discrete Mathematics 90C10, 90C27, 05C85 |
| url | https://arxiv.org/abs/2605.01481 |