On Solving the Assignment Problem with Conflicts

Derek H. Smith; Roberto Montemanni

REVIEW 3 major objections 5 minor 24 references

On Solving the Assignment Problem with Conflicts

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A general-purpose solver matches specialized algorithms on the assignment problem with conflicts.

desk verdict A small, honest benchmark paper: the new result is CP-SAT 9.12 on existing APC instances, but the abstract overstates the heuristic gains and the cross-machine CPU comparison weakens the exact-solver claim. read the letter →

arxiv 2506.04274 v1 pith:4IYWLNIZ submitted 2025-06-03 math.OC

Roberto Montemanni , Derek H. Smith This is my paper

classification math.OC MSC 90C1090C2705C70

keywords assignmentproblemwithconflictsperfectmatchingconflictconstraintsmixedintegerlinearprogrammingCP-SATconstraintexactalgorithmsheuristics

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper aims to show that a previously known mixed integer linear program for the Assignment Problem with Conflicts—the problem of finding a cheapest perfect matching in a bipartite graph under constraints that forbid certain pairs of assignments from being chosen together—can be solved just as effectively by a general-purpose open-source constraint solver as by the purpose-built algorithms in the literature. The authors take the previously known model, write it in a few lines, and hand it to the CP-SAT solver without any custom search logic. On the 130 usable benchmark instances from the reference work, the solver finds the same optimal values that the dedicated exact methods find, and when used as a heuristic it returns optimal solutions faster than the dedicated Russian-doll-search heuristic and with a smaller gap than local search. The practical message is that a practitioner facing this problem need not implement specialized machinery to obtain good exact or heuristic solutions.

What carries the argument

The central vehicle is the previously known integer program (1)–(5). For each possible assignment between a left node $i$ and a right node $j$, a binary variable $x_{ij}$ is either 1 (selected) or 0; constraints (2) and (3) force each node to be matched exactly once, and each conflicting pair $\{i,j\},\{k,l\}$ contributes the inequality $x_{ij}+x_{kl}\le 1$, which forbids selecting both. The other half of the machinery is the CP-SAT solver run as a black box: the paper applies no branching rule, no cutting planes, and no heuristic of its own, so the result is a statement about how much can be achieved with a general solver alone.

What would settle it

Re-run the LS, RDS, BIP, and B&B implementations on the same CPU as CP-SAT with identical 3600-second limits and compare time-to-best and time-to-proof on the 130 instances; if CP-SAT's advantage over RDS disappears or its proof times exceed BIP's by a large margin, the central claim would fail.

Watch

Extended reading notes

Core claim

On its own terms, the paper claims that CP-SAT, solving the model (1)–(5) with binary assignment variables $x_{ij}$, assignment equalities (2)–(3), and one inequality $x_{ij}+x_{kl}\le 1$ per conflict, reaches all optimal values on the 130 usable benchmark instances. In the exact comparison, average time to proof is 204.5 seconds, against 194.1 for BIP and 216.5 for B&B; the differences are small, and the paper notes BIP remains the most robust option overall and B&B the best on the largest instances. In the heuristic comparison, CP-SAT's average gap is zero (it finds every optimum), whereas RDS leaves an average gap of 0.02% and local search 3.08%, and CP-SAT's average time to best solution is 141.6 seconds versus 566.4 for RDS. The paper therefore establishes that a conceptually simple, off-the-shelf formulation can compete with dedicated algorithms on this benchmark.

Load-bearing premise

The paper's performance conclusions treat the earlier methods' published runtimes as directly comparable to the new runtimes even though they were produced on a machine estimated to be at least three times slower; if that estimate is wrong, the claimed parity and speed advantage shift.

Editorial extensions

If this is right

CP-SAT proves optimality on all 130 usable benchmark instances, matching the dedicated exact methods BIP and B&B.
As a heuristic, CP-SAT finds every optimum on these instances, with zero average gap, versus 0.02% for RDS and 3.08% for local search.
CP-SAT's average time to best solution is about a quarter of RDS's (141.6 seconds versus 566.4 seconds) on comparable hardware.
For small and medium instances, BIP still gives proven optima faster, while B&B wins on the largest instances; CP-SAT occupies the balanced middle.
No custom algorithm is required: the entire method is a standard model plus a general solver.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The runtimes of the earlier methods were measured on a machine the authors estimate is at least three times slower; if that factor differs, CP-SAT's speed advantage over RDS and its parity with BIP and B&B would change.
Because the method is generic, the same model should extend to thicker conflict structures, such as triple conflicts or conflicts with weights, without new algorithmic work.
The largest instance in the benchmark has 500 nodes and 200,000 conflicts; testing beyond this conflict density would reveal where a generic solver's performance degrades relative to the specialized methods.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: this is a small, honest benchmark paper. The genuinely new content is one run: CP-SAT 9.12 on the 130 usable APC instances from Öncan et al. 2019, using the same MILP that was already in that paper. No new model, algorithm, or theorem. What the paper does well: the formulation is correctly transcribed, the experimental table is detailed enough to see per-instance-group behavior, and the final discussion is measured — it actually says BIP is often the best option and CP-SAT sits in between. That is more balanced than the abstract.

Soft spots, in proportion. The big one is the baseline comparison. CP-SAT ran on an i7-12700F; LS/RDS/BIP/B&B times come from [3] on an older 2.2 GHz i7, with the speed ratio only a web-site estimate ('3 or more times slower'). The stress-test note is right: if you apply the 3x correction, CP-SAT's average Sec Opt (204.5s) becomes ~613s on the old machine, which is worse than BIP's 194.1 and B&B's 216.5, not comparable. The paper's own conclusion already downgrades CP-SAT to 'in between,' so the exact-solver claim mostly survives in spirit, but the abstract's 'comparable with state-of-the-art solvers' is too strong without same-hardware reruns or a better-calibrated CPU ratio.

The heuristic claim is the clearest overreach. The abstract says CP-SAT provides heuristic solutions 'quicker and better' than prior heuristics. Table I shows CP-SAT Sec Best 141.6s on average vs LS 6.6s — 21x slower. CP-SAT is better on gap (0% vs 3.08%) and faster than RDS on average, so the abstract should say 'better' and, against RDS only, 'quicker.' That is an easy fix.

Also minor: five of the 135 instances are dropped for 'inconsistencies' but never listed. That is opaque; a table or footnote of which instances and what the inconsistency was would close the question of selective exclusion. The self-citations [21]-[23] are just motivation and don't do any load-bearing work — not a problem.

Verdict: this deserves a serious referee. The experimental comparison is reproducible in principle (open-source solver, public benchmark), the model is correct, and the paper is honest enough in its main conclusions. A revision that fixes the heuristic wording, either reruns baselines or narrows the performance claims to what the hardware correction supports, and documents the excluded instances would make it a sound little contribution. For an APC practitioner deciding between CP-SAT and custom code, the table is useful even with the cross-machine caveat.

Referee Report

3 major / 5 minor

Summary. The paper studies the Assignment Problem with Conflicts (APC), an assignment problem variant with pairwise conflict constraints. The authors take the previously known MILP formulation (1)-(5), solve it with the open-source CP-SAT solver (OR-Tools 9.12), and compare it against four published methods (LS, RDS, BIP, B&B) on the benchmark set from [3]. Experiments are reported for 130 of the 135 available instances, with average gaps and runtimes in Table I. The paper concludes that CP-SAT achieves results comparable to the exact state-of-the-art methods, and that it provides heuristic solutions that are "quicker and better" than the previously proposed heuristics.

Significance. If the empirical claims are correct, the paper provides a useful practical data point: a generic, open-source CP-SAT solver can match or even outperform dedicated algorithms on a standard APC benchmark with minimal implementation effort. The experimental results are transparently tabulated, and the authors correctly acknowledge the hardware-speed caveat, which is more than many empirical papers do. However, the significance is conditional on resolving the cross-machine runtime comparability and on documenting the five excluded instances; without those, the central "comparable" claim is not yet established. The paper does not introduce new theory or algorithms, so its value is empirical and comparative.

major comments (3)

[Section IV-B, Table I] The runtime comparison across machines is not quantitatively reliable. The only adjustment for the hardware difference is an informal web-derived estimate that the older CPU is "3 or more times slower." Applying this factor to the average Sec Opt values gives CP-SAT approximately 613 seconds versus 194.1 seconds for BIP and 216.5 seconds for B&B, which would make CP-SAT about three times slower rather than comparable. The authors should either rerun the compared methods on the same hardware, or provide a justified and sensitivity-tested performance normalization, before claiming that the exact times are comparable.
[Abstract and Section V] The statement that CP-SAT provides heuristic solutions "quicker and better" than prior heuristics is contradicted by Table I for the LS heuristic: the average Sec Best is 6.6 seconds for LS versus 141.6 seconds for CP-SAT. The data support the claims that CP-SAT achieves a better average gap (0% versus 3.08%) and is faster on average than RDS (141.6 seconds versus 566.4 seconds), but they do not support the "quicker" claim with respect to LS. Please revise the claim or add experiments with CP-SAT under time limits comparable to LS so that the speed assertion is substantiated.
[Section IV-A] The five excluded instances are not documented. The benchmark originally contains 135 instances and the paper uses 130, citing "some inconsistencies in the available dataset," but gives no information about which instances were removed or what the inconsistencies were. Because the averages in Table I are computed over the remaining 130 instances, the reader cannot assess whether the exclusions affect the conclusions. Please list the excluded instances (e.g., by |VA| and |C|), describe the inconsistencies, and preferably show that the reported averages are robust to their removal or report results for the full set.

minor comments (5)

[Abstract] The phrase "comparable with, those of state-of-the-art solvers" contains a stray comma; it should read "comparable with those of state-of-the-art solvers."
[Section II] The definition of the conflict set C is written as "C = {{i, j}, {k, l} | {{i, j}, {k, l}} ∈ E}", which is not a standard set-builder notation for a set of unordered pairs of edges. Please define C precisely as a set of two-element subsets of E.
[Section IV-B] Table I does not report a Gap% column for CP-SAT, even though the text claims that CP-SAT finds optimal solutions for all instances. Adding a Gap% column for CP-SAT would allow the reader to verify this claim directly from the table.
[Section IV-B] The hardware-speed ratio is currently supported only by a URL reference. It would be more rigorous to cite a specific benchmark or provide the CPU models and a measured or well-known speed ratio, rather than relying on an informal web page.
[References] Reference [16] lists an author as "G. Schauer, J.and Woeginger"; this appears to be a formatting error and should be corrected to "J. Schauer and G. J. Woeginger" (or the appropriate author list).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper solves an external MILP with a general-purpose solver and compares against published external benchmarks.

full rationale

The paper's derivation chain is entirely self-contained from an external starting point: it takes the MILP (1)-(5) from the reference work [3], feeds it to the CP-SAT solver, and reports computational results against the same published benchmark instances and published runtimes. There is no parameter fitted to the target results and then relabeled as a prediction; the optimal values in Table I are computed directly by the solver from the given objective and constraints. The only self-citations ([21]-[23]) merely motivate the choice of CP-SAT as a solver and do not enter the experiments or the derivation in any load-bearing way. The comparison with different hardware is a potential correctness threat, not a circularity, because the CP-SAT results are new measurements, not rewritten outputs of the compared methods. The benchmark is external to the authors' own prior work, and no uniqueness theorem or ansatz is imported from the authors' earlier papers.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new theory, free parameters, or entities. Its contribution is purely experimental: applying a known open-source solver to a known MILP on published benchmarks. The assumptions are standard domain assumptions about the correctness of the model, the benchmark set, and the comparability of literature baselines.

assumptions (3)

domain assumption The MILP (1)-(5) exactly represents the Assignment Problem with Conflicts.
Section III presents the model from [3] without proof; correctness is assumed.
domain assumption The benchmark instances from [3] are correctly generated and representative.
Section IV-A adopts 130 of the 135 literature instances, assuming their validity and the meaningfulness of the random conflict generation.
domain assumption The baseline solver results reported in [3] are accurate and comparable despite different hardware.
Section IV-B compares CP-SAT against published LS, RDS, BIP, and B&B times without rerunning them; a 3x hardware speed adjustment is estimated, not measured.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Solving the Assignment Problem with Conflicts." pith.science (2026). https://pith.science/paper/4IYWLNIZ

@misc{pith2026250604274,
  author       = {Pith},
  title        = {Pith review of: On Solving the Assignment Problem with Conflicts},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4IYWLNIZ}},
  note         = {Machine review of arXiv:2506.04274}
}

read the original abstract

A variant of the well-known Assignment Problem is studied in this paper, where pairs of assignments are conflicting, and cannot be selected at the same time. This configures a set of hard constraints. The problem, which models real applications, looks for a complete assignment that minimizes the total cost, while no conflict is violated. In this paper, we consider a previously known mixed integer linear program representing the problem and we solve it with the open-source solver CP-SAT, part of the Google OR-Tools computational suite. An experimental campaign on the instances available from the literature, indicates that the approach we propose achieves results comparable with, those of state-of-the-art solvers, notwithstanding its intrinsic conceptual and implementation simplicity. The solver adopted is also able to provide heuristic solutions quicker and better than the heuristic methods previously discussed in the literature.

Figures

Figures reproduced from arXiv: 2506.04274 by the authors.

**Figure 1.** On the left an example of a APC instance is presented, where conflicts are indicated as colored edges. Costs are omitted. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[3]

Assignment problem with conflicts,

T. ¨Oncan, Z. S ¸uvak, M. H. Aky ¨uz, and I. K. Altınel, “Assignment problem with conflicts,” Computers & Operations Research , vol. 111, pp. 214–229, 2019

work page 2019
[21]

Solving the parallel drone schedul- ing traveling salesman problem via constraint programming,

R. Montemanni and M. Dell’Amico, “Solving the parallel drone schedul- ing traveling salesman problem via constraint programming,” Algo- rithms, vol. 16, no. 1, p. 40, 2023

work page 2023
[23]

Solving a home healthcare routing and scheduling problem with real-world features,

R. Montemanni, “Solving a home healthcare routing and scheduling problem with real-world features,” in Proceedings of the 9th Interna- tional Conference on Machine Learning and Soft Computing . Springer, to appear, 2025

work page 2025
[1]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network flows . Mas- sachusetts Institute of Technology press, 1993

work page 1993
[2]

The Hungarian method for the assignment problem,

H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistics Quarterly , vol. 1-2, no. 2, pp. 83–97, 1955

work page 1955
[4]

A branch-and-bound algorithm for the knapsack problem with conflict graph,

A. Bettinelli, V . Cacchiani, and E. Malaguti, “A branch-and-bound algorithm for the knapsack problem with conflict graph,” INFORMS Journal on Computing , vol. 29, no. 3, pp. 457–473, 2017

work page 2017
[5]

A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts,

S. Coniglio, F. Furini, and P. San Segundo, “A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts,” European Journal of Operational Research, vol. 289, no. 2, pp. 435–455, 2021

work page 2021
[6]

The minimum spanning tree prob- lem with conflict constraints and its variations,

R. Zhang, S. Kabadi, and A. Punnen, “The minimum spanning tree prob- lem with conflict constraints and its variations,” Discrete Optimization, vol. 2, no. 8, pp. 191–205, 2011

work page 2011

Show all 24 references

[7]

A branch and cut algorithm for minimum spanning trees under conflict constraints,

P. Samer and S. Urrutia, “A branch and cut algorithm for minimum spanning trees under conflict constraints,” Optimization Letters, vol. 1, no. 9, pp. 41–55, 2014

2014
[8]

A multi-ethnic genetic approach for the minimum conflict weighted spanning tree problem,

F. Carrabs, C. Cerrone, and R. Pentangelo, “A multi-ethnic genetic approach for the minimum conflict weighted spanning tree problem,” Networks, vol. 2, no. 74, pp. 134–147, 2019

2019
[9]

Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach,

F. Carrabs, R. Cerulli, R. Pentangelo, and A. Raiconi, “Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach,” Annals of Operations Research , no. 298, pp. 65–78, 2019. TABLE I: Computational results. Instances Opt LS [3] RDS [3] BIP [3] B&B [3] CP-SAT ...

2019
[10]

A lagrangian approach for the minimum spanning tree problem with conflicting edge pairs,

F. Carrabs and M. Gaudioso, “A lagrangian approach for the minimum spanning tree problem with conflicting edge pairs,” Networks, vol. 1, no. 78, pp. 32–45, 2021

2021
[11]

Shortest paths with exclusive-disjunction arc pairs conflicts,

R. Cerulli, G. Guerriero, E. Scalzo, and C. Sorgente, “Shortest paths with exclusive-disjunction arc pairs conflicts,” Computers & Operations Research, vol. 152, p. 106158, 2023

2023
[12]

Set covering problem with conflict constraints,

S. Saffari and Y . Fathi, “Set covering problem with conflict constraints,” Computers & Operations Research , vol. 143, p. 105763, 2022

2022
[13]

Solving the set covering problem with conflicts on sets: A new parallel GRASP,

F. Carrabs, R. Cerulli, R. Mansini, L. Moreschini, and D. Serra, “Solving the set covering problem with conflicts on sets: A new parallel GRASP,” Computers & Operations Research , vol. 166, p. 106620, 2024

2024
[14]

Exact solution algorithms for the maximum flow problem with additional conflict constraints,

Z. S ¸uvak, I. K. Altınel, and N. Aras, “Exact solution algorithms for the maximum flow problem with additional conflict constraints,” European Journal of Operational Research , vol. 287, no. 2, pp. 410–437, 2020

2020
[15]

Hy- bridizing carousel greedy and kernel search: A new approach for the maximum flow problem with conflict constraints,

F. Carrabs, R. Cerulli, R. Mansini, D. Serra, and C. Sorgente, “Hy- bridizing carousel greedy and kernel search: A new approach for the maximum flow problem with conflict constraints,” European Journal of Operational Research, 2025

2025
[16]

Paths, trees and matchings under disjunctive constraints,

A. Darmann, U. Pferschy, and G. Schauer, J.and Woeginger, “Paths, trees and matchings under disjunctive constraints,” Discrete Applied Mathematics, vol. 16, no. 159, pp. 1726–1735, 2011

2011
[17]

The minimum cost perfect matching problem with conflict pair constraints,

T. ¨Oncan, R. Zhang, and A. P. Punnen, “The minimum cost perfect matching problem with conflict pair constraints,” Computers & Opera- tions Research, vol. 40, no. 4, pp. 920–930, 2013

2013
[18]

Iterated exact and heuristic algorithms for the minimum cost bipartite perfect matching problem with conflict constraints,

T. ¨Oncan and I. K. Altınel, “Iterated exact and heuristic algorithms for the minimum cost bipartite perfect matching problem with conflict constraints,” in 2017 IEEE International Conference on Industrial En- gineering and Engineering Management (IEEM) , 2017, pp. 1032–1036

2017
[19]

A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints,

——, “A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints,” Electronic Notes in Discrete Mathematics, vol. 64, pp. 5–14, 2018, 8th International Network Optimization Conference - INOC 2017

2018
[20]

Google OR-Tools - CP-SAT,

L. Perron and F. Didier, “Google OR-Tools - CP-SAT,” Google, 2025, https://developers.google.com/optimization/cp/cp solver/

2025
[22]

Parallel drone scheduling vehicle routing problems with collective drones,

R. Montemanni, M. Dell’Amico, and A. Corsini, “Parallel drone scheduling vehicle routing problems with collective drones,” Computers & Operations Research , vol. 163, p. 106514, 2024

2024
[24]

IBM CPLEX Optimizer,

IBM, “IBM CPLEX Optimizer,” 2024, https://www.ibm.com/de-de/ analytics/cplex-optimizer [Accessed: 2024-03-14]

2024

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [3]

Assignment problem with conflicts,

T. ¨Oncan, Z. S ¸uvak, M. H. Aky ¨uz, and I. K. Altınel, “Assignment problem with conflicts,” Computers & Operations Research , vol. 111, pp. 214–229, 2019

work page 2019

[2] [21]

Solving the parallel drone schedul- ing traveling salesman problem via constraint programming,

R. Montemanni and M. Dell’Amico, “Solving the parallel drone schedul- ing traveling salesman problem via constraint programming,” Algo- rithms, vol. 16, no. 1, p. 40, 2023

work page 2023

[3] [23]

Solving a home healthcare routing and scheduling problem with real-world features,

R. Montemanni, “Solving a home healthcare routing and scheduling problem with real-world features,” in Proceedings of the 9th Interna- tional Conference on Machine Learning and Soft Computing . Springer, to appear, 2025

work page 2025

[4] [1]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network flows . Mas- sachusetts Institute of Technology press, 1993

work page 1993

[5] [2]

The Hungarian method for the assignment problem,

H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistics Quarterly , vol. 1-2, no. 2, pp. 83–97, 1955

work page 1955

[6] [4]

A branch-and-bound algorithm for the knapsack problem with conflict graph,

A. Bettinelli, V . Cacchiani, and E. Malaguti, “A branch-and-bound algorithm for the knapsack problem with conflict graph,” INFORMS Journal on Computing , vol. 29, no. 3, pp. 457–473, 2017

work page 2017

[7] [5]

A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts,

S. Coniglio, F. Furini, and P. San Segundo, “A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts,” European Journal of Operational Research, vol. 289, no. 2, pp. 435–455, 2021

work page 2021

[8] [6]

The minimum spanning tree prob- lem with conflict constraints and its variations,

R. Zhang, S. Kabadi, and A. Punnen, “The minimum spanning tree prob- lem with conflict constraints and its variations,” Discrete Optimization, vol. 2, no. 8, pp. 191–205, 2011

work page 2011