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

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:

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

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:

Example file


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.

Word Puzzle Solver

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



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.

[Constraints] [
Negation] [Meta-interpreters] [Media Analysis]

[Search] [Guides]

Charles University
Malostranské nám. 25
Praha 1