Back to PROJECTS
> CONSTRAINTS
<
NEGATION
INTERPRETERS
MEDIA ANALYSIS
SEARCH
ONLINE
GUIDES

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 overconstrained systems.
Overconstrained system is a system of constraints
which cannot be solved at once, thus overconstrained.
Probably the most promising approach for describing
overconstrained systems is using constraint
hierarchies.
Constraint
hierarchies were introduced for describing
overconstrained 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 overconstrained systems using
constraint hierarchy approach. We also study
interhierarchy 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 PlugIn Architecture for HCLP (1996)
The
program implements a plugin architecture for
Hierarchical Constraint Logic Programming (HCLP). To get
the HCLP solver, you need to include:
 a
kernel metainterpreter (PROLOG
source code)
 a
general hierarchy solver (PROLOG
source code)
 a
plugin module with flat constraint solver
 a
plugin module that implements a specific
comparator
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 plugin module
containing a constraint solver to get a specific labeling
procedure. Two examples of plugin 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
InterHierarchy
Comparison in HCLP (download)
Barták, R., in: Proceedings of PAP/PACT '98,
pp. 461474, 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
Plugin Architecture of Constraint Hierarchy Solvers
(download)
Barták, R., in: Proceedings of PACT '97, pp.
359371, 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]
[Metainterpreters]
[Media
Analysis]
[Search]
[Guides]
