Richer Constraint Solving
Richer constraint solving means exploiting state of the art constraint solving methods, and, where there is a clear need and opportunity, developing new solvers that advance the state of the art.
Exploiting the State of the Art
Solvers that the project would exploit include MIP packages such as ILOG Cplex and Dash Xpress-MP. Over the last 15 years, MIP software efficiency has improved exponentially - doubling every 24 months - so as to match the performance improvement of hardware. It makes sense to build on these improvements, rather than trying to keep up with this fast-moving technology.
There are a number of software packages available that build on an underlying linear solver to support the development of more sophisticated algorithms. For example the ABACUS (`A Branch and Cut System') package is likely to prove useful as a component of G12, though it will be hidden from the user. For problems involving networks, a variety of algorithms are available as an alternative to or an extension of integer/linear programming. A package that provides sophisticated support for graph and network problems is LEDA.
Finally there has been exciting progress in interval methods yielding tight and safe approximations to the solutions to non-linear numerical problems. The RealPaver package is one candidate solver for inclusion in G12.
Advancing the State of the Art
Whilst constraint propagation over finite domains has become a mature technology, finite set-valued variables present new opportunities for propagation. In particular Binary Decision Diagrams provide a basis for some powerful propagation techniques for sets and potentially finite domains, which will be developed further and integrated into G12.
A second area of new development is the introduction of global constraints involving continuous variables. One example of this is a class of global scheduling constraints with task start-time variables ranging over a continuous temporal domain.
There is also a need to introduce global constraints that enforce an associated cost constraint. An example is a cost-constrained path constraint. Thirdly an area of current research is the design and implementation of soft global constraints. In effect these are global constraints with a cost which is related to the degree of violation of the global constraint.
Thirdly the theorem proving community has developed many powerful reasoning techniques. Their embedding into G12 will dramatically extend the range of constraint propagation techniques available to the problem solver.
Another area will be developing algorithms for returning more robust solutions. One possibility here is to use existing methods to find a starting solution, and then use branch and bound methods to improve its `robustness'. In this way, we provide an anytime approach, in which the user occurs no additional cost to see the first solution. However, if times permits, they can have a more robust solution.