New developments

[Laurent Perron]

Hello, 

It is time for a status update on our code!

Since the last announcements, we have added:

  - 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.

--Laurent (on behalf of the complete Operations Research team at Google).

[Laurent Perron]

Here is what we have been doing in Q3.

Graph algorithms: 

  - a lot of work went into making the algorithms (min cost flow, max flow) incremental after small modifications.

Linear solver: 

  - Added utility of constraints, primal and dual tolerances.

  - Basis status of variables.

  - Added solving model from protobuf, outputting solutions as protobuf. Useful for having MP solvers in another process or machine for instance.

Constraint solver:

  - Added complete model visitor 

  - Applications to pretty print the model or display special stats

  - Main application is to implement model read/write to file. I will send another message to detail all this.

  - Added model_util binary to query/test/modify exported models.

  - Change the internal way of storing constraints and expressions in caches to avoid duplicating equivalent classes.

  - Lots of cleanup for the reference manual. Size has been divided by nearly 4 by hiding all implementation classes: check http://or-tools.googlecode.com/svn/doc/full_reference_manual/or-tools/index.html.

And of course the usual batch of bug fixes.

[John]

Nice!

[Phil Degenhardt]

Laurent, we are using the min cost flow solver and incrementally adding arcs to the graph. Is there anything we need to do to take advantage of the incremental algorithms referred to above?

We are adding an arc to a graph that was previously solved with M arcs but are finding the solve time is pretty much the same as if just solved a new M+1 arcs problem.

Thanks,
Phil