mercredi 22 juin 2011

Google or-tools new developments

Laurent Just sent an update on the or-tools mailing list:

- linear assignment (including dimacs challenge support): A. V. Goldberg and R. Kennedy, "An Efficient Cost Scaling Algorithm for the Assignment Problem." Mathematical Programming, Vol. 71, pages 153-178, December 1995.
- Min cost flow: R.K. Ahuja, A.V. Goldberg, J.B. Orlin, and R.E. Tarjan, "Finding minimum-cost flows by double scaling," Mathematical Programming, (1992) 53:243-266. http://www.springerlink.com/index/gu7404218u6kt166.pdf
- Max flow (many references, see graph/max_flow.h for details).
- SCIP support (see scip.zib.de). We will make a separate announcement on how to compile scip to be used in or-tools.
- Deviation constraint in the Constraint Programming solver : Pierre Schaus et. al., "Bound Consistent Deviation Constraint", CP07.
- Initial support for no good management in the CP search tree.
- 30-50% speedup on large sums in constraint programming.

Aucun commentaire:

Enregistrer un commentaire