Environment
The key to solving complex industrial application problems is rapid applications development, with close end-user involvement. This is necessary to:
- reduce application cost,
- minimise the risk of wasting effort on an approach that never ultimately works,
- ensure that the specified problem accurately reflects the real industrial requirement, and
- deliver a working solution before the business needs have changed.
One of the most important factors in application development is the quality of the development environment. To support rapid application development, a rich solution development environment is essential.
The first stage in developing an application is constructing a correct Zinc model. This is much easier for the application programmer if solutions are presented in a way that they can readily understand, for example for scheduling as Gantt charts or for routing as routes on a map. Often, as in these examples, a graphical representation is required. Consequently the system must provide natural and easily added application specific graphical representations for models expressed in Zinc. These representations should be interactive, for example allowing the user to set the value of a variable to a specific value, even while the machine is searching for solutions to the problem. Furthermore the system should be able to explain why a particular suggested solution is in fact invalid, highlighting the constraints in the model that it does not satisfy. The combinations of flexible graphics, dual control (by the user and by the machine), and real-time mapping between the Zinc model and the Mercury program is an exciting research challenge.
The second and more time consuming phase is performance debugging in which we study the behaviour of the algorithms at runtime and understand exactly what is going on. Interaction with a running algorithm is necessary to detect its weaknesses, and to understand and build on its strengths. To support close end-user involvement, the problem solving behaviour must be made meaningful and transparent to the end-user. This requires that the algorithm behaviour be mapped back onto the problem model, so that the user can understand the behaviour in terms of the original application, rather than seeing it in terms of the underlying implementation. It also requires the ability to display algorithm behaviour in a meaningful way. For each kind of algorithm this means different forms of visualisation. For example, constraint propagation can be visualised by representing graphically the domains of the relevant variables before and after each propagation step. However at a higher level of abstraction, it is only necessary to represent the variable domains at the beginning of each propagation sequence, and not showing any domain reductions until all propagation steps are completed and a fixed point has been attained. A quite different example is the requirement to represent the solution to the relaxed linear subproblem after each run of the (external) linear solver. In this case the relaxed solution may change completely after each invocation of the linear solver. The shadow price of a constraint may also need to be represented graphically.
An important component of performance debugging is running a particular algorithm on a variety of test data in order to test for brittleness. It would be useful to have automatic generation of a profiling data summary obtained by merging profiling information from each of the data sets.
A major part of solution development is experimentation with different hybrid algorithms. In this case it would be good to have facilities to compare two different algorithms. For example given one algorithm that works, albeit slowly, the problem solver may develop an enhancement that produces solutions much more quickly but appears to miss some. What is needed is a facility to run both algorithms concurrently and have the system detect at what point the two algorithms diverge. The challenge is to devise a specification and implementation of the concept of "divergence" that only reports significant divergences, and not unimportant ones.