Constraint Hierarchies

Constraint programming, which makes a general framework of this project, is an emergent software technology for declarative description and effective solving of large, particularly combinatorial, problems especially in areas of planning and scheduling.

One of the hard problems studied within the area of constraint programming is handling over-constrained systems. Over-constrained system is a system of constraints which cannot be solved at once, thus over-constrained. Probably the most promising approach for describing over-constrained systems is using constraint hierarchies.

Constraint hierarchies were introduced for describing over-constrained systems by specifying constraints with hierarchical strengths or preferences. It allows one to specify declaratively not only the constraints that are required to hold, but also weaker, so called soft constraints at an arbitrary (finite) number of strengths.

The aim of the project is to design new general methods and algorithms for solving over-constrained systems using constraint hierarchy approach. We also study inter-hierarchy comparison within the project. The project covers:

• theory (formal definitions, soundness and completeness results)
• methodology
• implementation

To test our research ideas we have implemented the proposed algorithms in Prolog. Note that these programs are software prototypes.A Generalized Algorithm for Solving Constraint Hierarchies (1997)

The program implements a generalized algorithm for solving constraint hierarchies. This algorithm consists of two phases: planning phase that constructs constraint networks and executing phase that traverses the network and computes valuation of variables.

The following two modules implement a planning phase:

• basic graph operations (PROLOG source code)
• general constraint planner (PROLOG source code)

The following two modules implement an executing phase based on Indigo algorithm:

• interval arithmetic (PROLOG source code)
• Indigo executor (PROLOG source code)

Download also the Read Me file and some examples of usage.

A Plug-In Architecture for HCLP (1996)

The program implements a plug-in architecture for Hierarchical Constraint Logic Programming (HCLP). To get the HCLP solver, you need to include:

• a kernel meta-interpreter (PROLOG source code)
• a general hierarchy solver (PROLOG source code)
• a plug-in module with flat constraint solver
  • constraints over the Herbrand Universe (PROLOG source code)
• a plug-in module that implements a specific comparator
  • locally-predicate-better comparator (PROLOG source code)
  • regionally-predicate-better comparator (PROLOG source code)
  • weighted-sum-predicate-better comparator (PROLOG source code)
  • worst-case-better comparator (PROLOG source code)
  • unsatisfied-count-better comparator (PROLOG source code)

CSP (Constraint Satisfaction Problems) (1996)

The program implements a skeleton for labeling, the main part of CSP solvers. You need to include a plug-in module containing a constraint solver to get a specific labeling procedure. Two examples of plug-in modules are enclosed.

• PROLOG source code of labeling kernel
• plug-in module for constraints over integers (backtracking)
• plug-in module for constraints over integers (forward checking)

Word Puzzle Solver

This is a program, based on CSP, for solving word puzzles. Example of usage is enclosed.

• PROLOG source code of Word Puzzle Solver
• word puzzle example

Constraint Hierarchy Networks (download)
Barták, R., in: Proceedings of 3rd ERCIM/Compulog Workshop on Constraints, Amsterdam, September 1998

Inter-Hierarchy Comparison in HCLP (download)
Barták, R., in: Proceedings of PAP/PACT '98, pp. 461-474, London, March 1998

A Generalized Framework for Constraint Planning (download)
Barták, R., Tech. Report No 97/9, Department of Theoretical Computer Science, Charles University, Prague, June1997

Expert Systems Based on Constraints (download abstract)
Barták, R., Doctoral Dissertation, Charles University, Prague, April 1997 (in Czech, English summary available)

A Generalized Algorithm for Solving Constraint Hierarchies (download)
Barták, R., accepted as poster to JFPLC '97, also available as Tech. Report No 97/1, Department of Theoretical Computer Science, Charles University, Prague, January 1997

A Plug-in Architecture of Constraint Hierarchy Solvers (download)
Barták, R., in: Proceedings of PACT '97, pp. 359-371, London, April 1997
also available as Tech. Report No 96/8, Department of Theoretical Computer Science, Charles University, Prague, December 1996

The project is supported in part by:

• Faculty of Mathematics and Physics, Charles University
• Grant Agency of Czech Republic under the contract No 201/96/0197.

The other supporters are very welcomed, especially from the industry area. If you want to support this project (and exploit the research results directly), please contact me.

Charles University
Malostranské nám. 25
Praha 1
CZECH REPUBLIC