Modelling real-world problems using constraints
Parc Technologies develops solutions for industrial-scale combinatorial optimisation problems using the ECLiPSe development environment. ECLiPSe is a constraint programming platform, which is able to solve problems of a scale and complexity beyond the reach of more conventional approaches.
Combinatorial problems exist in many different fields, including planning, scheduling, resource allocation, routing, and complex numerical problem solving. The common task in these different application domains is to choose among many possible alternatives in order to find solutions that best meet many constraints.
Consider an airline schedule plan with 2500 flights, where each flight can be placed within a 4 hour time window in 5 minute increments. There exists scope here for 482500 scheduling configurations. To imagine how large this number is, consider that the number of atoms in the known universe is thought not to exceed 1079. Some of the constraints that an acceptable schedule must respect include airport capacity, maintenance requirements, regulatory restrictions, health and safety regulations, and marketing objectives. The task is to discover which of 482500 possible schedules satisfy all requirements, and of these which is the best. In mathematical terms, this type of problem is “NP-Hard”. In practical terms, this means that no single problem-solving technique can find solutions efficiently.
Flexible problem solving
But business problems aren’t static. In airline scheduling, changing fleet profiles, together with new maintenance practices and new services, may alter the structure of the problem completely. In the Internet Service arena, new hardware, faster customer access lines, more bandwidth-hungry applications and new billing options may have the same effect. This complexity of constraints tends to increase as business grows. A problem-solving system that cannot adapt rapidly and flexibly to new requirements and the increasing complexity of existing ones will quickly become obsolete.
Automated systems must interact with users in an intuitive way to provide useful decision support to businesses. The user interface must allow the human operator to introduce new rules and techniques to guide the search process. This co-operation enables better solutions to be found in shorter time. ECLiPSe has been developed to describe combinatorial problems in a natural and intuitive way. Off-the-shelf problem solving techniques can then be combined to find optimal solutions efficiently. This approach enjoys several benefits:
- Fast development time, re-using and combining problem solving techniques
- A declarative style of problem description, reducing maintenance effort
- The ability to add new functionality without the need to remodel from scratch
- The ability to add domain-specific information to help guide search towards solutions
Only by combing state-of-the-art problem solving techniques with human insight can problems of such staggering complexity be tamed. Constraint programming using ECLiPSe enables Parc Technologies’ customers to benefit from this winning combination.