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
