Use of Declarative Programming for Solving Industrial Optimization Problems
by Ulrich Geske
The correctness, safety, efficiency and maintenance of software systems depend essentially on the kind of specifications used and on the possibilities of manipulating such specifications. The use of logic-declarative concepts has a positive effect on all phases of a system's lifecycle: a declarative specification reflects clearly the logic of the algorithms; facilitates the use of metainterpretation, program transformation and abstract interpretation; testing, execution (by different processing systems) and debugging of declarative programs benefit from the fact that the code is (almost) free from control elements and side effects.
In the modeling, processing and maintenance of industrial systems, in which the combinatorial nature of the basic problem essentially influences the task of finding an optimal or near-optimal solution, the use of declarative and knowledge-based methods has proved to be highly advantageous, especially for tasks like job shop scheduling, flow shop scheduling, material requirements planning, allocation and packing problems, timetabling, and the design of technical devices.
Traditionally, such problems are dealt with using classical Operations Research methods. A number of algorithms exist to address problems of this kind. These include linear programming, branch-and-bound, constraint satisfaction, hill climbing, simulated annealing, tabu search, genetic algorithms, connectionist systems, and expert systems. The problem when using such algorithms to find solutions to complex problems is, that they have an exponential complexity, which normally prevents the fast generation of exact solutions.
An alternative approach is to employ new methods of Constraint-Logic Programming (CLP) and Hierarchical Constraint-Logic Programming. The declarative nature of these new paradigms is reflected in the use of a logic-based approach for modeling a problem, which avoids side effects and fundamentally changes the manner of processing from an a posteriori to an a priori style of condition checking. Moreover, the high efficiency of these methods allows the simulation of different strategies and yields near-optimal solutions in a short time. Nevertheless, complex problems can only be solved heuristically.
In the Declarative Programming group at GMD Institute for Computer Architecture and Software Technology, research is under way to extend these (H)CLP methods, and to investigate intelligent methods from knowledge-based systems, case-based reasoning, and connectionist systems in order to select appropriate heuristics. In our experiments we quickly found solutions for benchmark problems which deviated no more than approx. 5% from the optimal solution. These results contrast sharply with to deviations of 30% to 50% found with commercial tools, which use traditional algorithms. A promising future line of research would appear to be the combination of constraint-based and local search methods.
New paradigms, such as Constraint Logic Programming (CLP) and Hierarchical Constraint Logic Programming (HCLP), bring significant advantages by reducing the complexity of the search tree. Moreover, the high efficiency of these methods allows the simulation of different strategies and yields near-optimal solutions.
The CLP techniques provide a necessary link between the declarative description of constraints, which arise in scheduling, planning, and configuration domains, and the demand for efficient usable programs. Roughly speaking, CLP is a combination of constraint satisfaction (CSP) and logic programming. The CLP paradigm combines efficient methods known from Operations Research (OR) with flexible methods from Artificial Intelligence and Logic Programming for search and rule processing.
An important extension of CLP is HCLP, which allows us to express soft constraints, whose satisfiability is uncertain and controlled by error functions. Soft constraints are very useful for solving over-constrained problems and for modeling planning/design goals. Constraint-satisfaction methods are characterized by efficient processing where there are a large number of constraints. Moreover, constraint-satisfaction methods allow problem-oriented problem description, dispensing with artificial parameters that have to be adjusted. Since it is also valid for other methods, the CSP method's order of execution is hard to understand, but it inspires greater confidence by confining attention to the actual defining quantities of the problem.
While inheriting a strong theoretical background from logic programming, (H)CLP offers a declarative programming style, that is expressive and flexible enough for problem specification and heuristics programming, allowing rapid program development for complex problems and enabling programs to be easily modified and extended. This programming style is often considered a major contribution to software engineering, since it enables programs to be written with clear and transparent semantics, which is what distinguishes logic-based systems from mainstream programming languages.
Extensions of the constraint-logic programming paradigm and applications have been studied by using the WISPRO (Knowledge-Based Production Planning) VERMEIL (Methods for Knowledge-Based Development of Reliable Control Systems), and ImPlan (Intelligent Multi-Resource Planning) projects. Extensions affect constraint hierarchies, processing of dynamic constraints, search by backtrackable domain reduction, and layered backtracking. Their use results in execution times of a few seconds and near-optimal or optimal plans.
Description languages and visual, interactive tools have been developed for scheduling, configuration, planning, and timetabling tasks. Our replanning method is based on the application and developed extensions of the HCLP model. The incremental processing of constraints makes it possible to avoid (re)planning from scratch in the case of changed conditions. By this method, starting from an already available solution, the number of changes can be minimized.
The EXCALIBUR (Adaptive Constraint-Based Agents in Artificial Environments) project sets out to describe distributed parts of a domain that have to work together, or to decompose large problems into smaller ones. These parts can be considered autonomous agents. Autonomous agents in planning, scheduling or computer games have to select the right action and adapt to the current situation in order to attain their goals. They require intelligent behavior and also the ability to communicate and perform coordinated actions. Equipping agents with constraint-based capabilities enables them to find efficient solutions to complex search problems. Research is under way to equip such agents with the capabilities of real-time response, dynamic and learning behavior.
Constraint technology is also being used in a project with the aim of integrating logic-based constraint-solving techniques and deductive databases so as to express and efficiently process temporal-spatial relations. Further Information is available at: http://www.cs.tu-berlin.de/concorde/plan
Please contact:
Ulrich Geske - GMD
Tel: +49 30 6392 1782
E-mail: geske@first.gmd.de
