New answers tagged solver
8
This is where decomposition algorithms (specifically Dantzig-Wolfe can be quite useful).
My thesis work and subsequent OSS in COIN provides APIs to do this kind of thing:
https://projects.coin-or.org/Dip
The basic idea is that the oracle is the graph implementation while the side constraints are modeled as the master constraints in the decomposition ...
6
In general ILP solvers are not as efficient in solving the Maximum Matching problem. A comparison of efficient matching algorithm implementations, as well as an ILP formulation for the Maximum Cardinality Matching Problem and the Minimum Weight perfect matching problem can be found in Figures 5 and 6 of this paper:
Dimitrios Michail, Joris Kinable, Barak ...
Top 50 recent answers are included
