Student Project Proposal:

A Simple CSP Solver for Continuous Constraints


Supervisors

Santiago Macho Gonzalez
Office: INR 210
Tel: 693 6595
Email: santi.macho@epfl.ch
Tuan-Viet NGUYEN
Office: INR 210
Tel: 693 6595
Email: viet.nguyen@epfl.ch

Description

Many problems, ranging from resource allocation and scheduling to fault diagnosis and design, involve numerical constraint satisfaction as an essential component. A constraint satisfaction problem (CSP) can have one, several or no solutions. Most commonly used constraint solvers attempt to compute a single solution, optimal according to some criterion. Most solvers are based on linear and non-linear programming, others use numerical analysis, hill-climbing or stochastic techniques.

We have developed a java library which supports classical constraint satisfaction problems, Java Constraint Library. JCL is designed to support in applications based on Constraint-based reasoning.Mainly there are three parts of constraint-based problem solving supported by this library: building the CSP, solving the CSP and preprocessing the CSP.

The aim of this project is to implement a simple CSP Solver for continuous constraints/variables as an extension of the JCL. The Solver only implements very basic CSP algorithms.
(We have implemented a C++ version of the Solver, and it can be demonstrated online here)

This project is suitable for a student undertaking in a semester The student should have good Java programming skills and basic graph theory knowledge.

This project can be extended to a diploma project later on if desired.

Skills

Java programming language

Environment

Unix workstation

Last modified: Sun May 19 15:01:38 MEST 2002 Webmaster