October 19, 2012
Kathryn Francis
The field of Constraint Programming (CP) is concerned with solving combinatorial optimisation problems, and the associated tools have been successfully applied to large-scale problems in industry. Unfortunately, these tools are very difficult and inconvenient for general software developers to use, so many smaller problems which should be easily solved by CP technology are still tackled by hand or using ad-hoc algorithms. Existing CP tools require the use of a separate paradigm to define the optimisation problem. This is true even for CP libraries embedded in general purpose programming languages. We suggest an alternative interface to CP which instead uses the semantics of the host language to define the problem. The programmer writes a procedure which constructs a solution using an oracle to make decisions, and another procedure which evaluates a solution. Both of these can make use of existing code and data types. The optimisation problem is to find the decisions which should be made by the oracle in order to maximise or minimise the evaluation result. Using this procedure-based problem definition, optimisation can be seamlessly integrated into a wider application. During program execution optimisation is triggered be specifying the relevant procedures. An appropriate conventional constraint model is created automatically and sent to an external solver. Then the results are used to update the program state as though the procedure to build a solution has been executed with optimal decisions made by the oracle. In this talk I will describe our prototype implementation of such an interface for Java.