Constraint
Logic Programming

Applications

Mr. I. Sakellariou

**
Intelligent Systems & Knowledge Processing Group (ISKP) **

http://iskp.csd.auth.gr

Department of Informatics, Aristotle University of Thessaloniki, Greece.

ISKP
Group - CLP Applications 2005

2

Outline

- CLP Applications in Industry
- ISKP Group efforts
- University Exam Scheduling
- Distributed CSP: CSPCONS
- Workforce Management
- Distributed Singleton Consistency
- Protein Structure Prediction

ISKP
Group - CLP Applications 2005

3

CLP
Applications

- The CLP paradigm has enjoyed a large number of applications.
- Commercially available platforms:
- SICStus: Swedish Institute of Computer Science
- ECLiPSe:
Originally ECRC, IC-Parc, now
**CISCO** - CHIP: ECRC, now COSYTEC
- There is an increasing number of applications, shown by the fact that annual conferences are devoted to it (PADP, ICLP, etc).

ISKP
Group - CLP Applications 2005

4

Some
Examples of Real World CLP Applications (1/3)

- Options Trading (stock market)
- OTAS system
- Constraint Based Spreadsheets
- Short Term Planning System at Renault
- Cutting stock

ISKP
Group - CLP Applications 2005

5

Some
Examples of Real World CLP Applications (2/3)

- Scheduling
- Scheduling activities in Energy Distribution network in Spain (PlaNets).
- Planning and Scheduling Aircraft Manufacture at Dassault Aviation
- Finds schedules of production lines to meet requirements.

ISKP
Group - CLP Applications 2005

6

Some
Examples of Real World CLP Applications (3/3)

- Allocation
- aircraft stand allocation (Roissy airport at Paris)
- ships allocation in harbour (Hong Kong International Terminals)
- Crew rotation
- Nurse planning package (GYMNASTE) assigns shifts according to work regulations, laws and individual wishes.
- Crew assignment to flights (SAS, British Airways, Swissair, TGV Trains FRANCE)

CLP Applications in ISKP group

ISKP
Group - CLP Applications 2005

8

Research
in ISKP group

*(Distributed
Filtering Algorithm)*

Distributed
Singleton Consistency

*(DCSP Application)*

DIWOMS (Distributed
Workforce Management System)

*(Distributed
CPL Platform)*

CSPCONS

*(CSP Application)*

University Exam Scheduling

ISKP
Group - CLP Applications 2005

9

University Exam Scheduling Application

ISKP
Group - CLP Applications 2005

10

Exam
Scheduling

- Common problem to University Departments.
- Involves finding an allocation of exams to available exam halls, allocation of invigilators, etc.
- A
number of
**constraints**have to be satisfied.

ISKP
Group - CLP Applications 2005

11

Exam
Scheduling Problem:

Resources & Data

- General Time related resources
- Starting date & Ending Date of exam period
- Holidays
- Exam halls
- Name, capacity, etc
- Availability
- Invigilators and exam setters
- Modules,
- Availability
- Course related
- Semester, number of students participating, etc

ISKP
Group - CLP Applications 2005

12

Exam
Scheduling Problem:

**Constraints **

- Exam setters and invigilators
- Invigilator cannot be in two halls simultaneously!
- Availability
- Maximum number of exams/day
- Exam halls
- Capacity
**constraints** - Hall availability
- Module related
- Avoid scheduling two exams of the same semester on the same time slot.
- Avoid scheduling same semester exams in the same day.

ISKP
Group - CLP Applications 2005

13

Modeling

- Common approach
- Divide Available time periods in slots. (1-hour/2-hour, etc)
- Assign
an integer to each
*time slot*-*exam Hall*pair.

*Hall 1 1*^{st
Exam Day 9:00-10:00 }^{ }^{ 1}

^{Hall 2 1st
Exam Day 9:00-10:00 }^{ }^{ 2}

^{Easier to state difference constraints.}^{Easier to state Hall/Exam setter availabilities}^{Easier to state capacity constraints.}

ISKP
Group - CLP Applications 2005

14

ECLiPSe-JAVA
Implementation

- Constraint Solving
- ECLiPSe
IC Library (Integer
**Constraints**) - Interface JAVA

ISKP
Group - CLP Applications 2005

15

Entering Information about Classrooms (Exam Halls)

ISKP
Group - CLP Applications 2005

16

Schedule

ISKP
Group - CLP Applications 2005

17

Distributed Constraint Logic Programming

ISKP
Group - CLP Applications 2005

18

Distributed
CLP (Our Current Research)

- The need for distributed constraint logic programming systems derives from the fact that:
- more efficient implementations
- natural representation of problems that are distributed in nature:
- production
planning in a factory in which independent departments must meet their
local
**constraints**and at the same time co-operate to achieve global**constraints** - university course scheduling in the case that university departments share resources (classes, labs, etc)
- implementation of multi-agent systems based on CLP.

ISKP
Group - CLP Applications 2005

19

Building
DCSP Applications

- Currently there are only a few Logic Programming platforms that address the problem of building DCSP applications (eg. CIAO, OZ).
- Such a platform should include:
- Sufficient Communication Primitives
- Support for Constraint Programming
- The
Communication Sequential
**Prolog**(CSPCONS) addresses both issues. - Suitable platform for the development and testing of distributed constraint applications.
- Developed under the Bilateral Cooperation Greece-Hungary 2000-2002 (AUTH-ML).

ISKP
Group - CLP Applications 2005

20

A Platform for DCLP Applications: CSPCONS

ISKP
Group - CLP Applications 2005

21

CSPCONS
(1/3)

- Our
approach involves extending the Communicating Sequential
**Prolog**II System to support Constraint Logic programming (CSPCONS). - CS-
**Prolog**II, is - a
UNIX implementation of the standard
**Prolog**that was developed by ML (Hungary). - originally developed for transputers (parallel processors)
- was ported to UNIX during an EU funded INCO-Copernicus project (ExperNet).

ISKP
Group - CLP Applications 2005

22

CSPCONS
(2/3)

- This approach was followed because CSP II offers among other things:
- Parallelism
through the use of
**independent sequential**that communicate via a message passing mechanism over channels.**Prolog**processes - Real time features
- TCP/IP communication capabilities between other instances of CSP-II programs and external applications
- Implementation is robust and has been tested on a real world application.

ISKP
Group - CLP Applications 2005

23

CSPCONS
Processes

- Self
driven: execute a single
**Prolog**call. - Event driven: respond to events.
- Inter-Process Communication
- Message Passing, though channels.
- Event Passing, by explicit (programmer) or implicit (system) event generation.
- TCP/IP Communication
- Extension of inter-process message passing scheme, but asynchronous

ISKP
Group - CLP Applications 2005

24

CSPCONS
Application

*Process A*

*channel*

*Process B*

*Process C*

*Process D*

*channel*

*channel*

ISKP
Group - CLP Applications 2005

25

TCP/IP
Mechanism Notions

- CSP-Port, entry point for all incoming messages
- Connection, where all outgoing messages are directed.
- Both are linked with local channels.

*connection*

*port*

*Process A*

*Process B*

**CSP Application**

**CSP Application**

*outgoing_channel*

*incoming_channel*

ISKP
Group - CLP Applications 2005

26

**Constraints
**in CSPCONS

- The
original language has been extended to provide support for
**constraints**. **Constraints**are being incorporated as external libraries, implemented in C, thus allowing the implementation of any constraint domain.- Constraint libraries for linear and finite domains have been developed.

ISKP
Group - CLP Applications 2005

27

CSPCONS
**Constraints** Schema

- CSP-Process
(core) handles all
**Prolog**specific tasks, maintains the solver instances and dispatches all*constraint related calls*to the solver. Each core can be connected to up to 4 solvers. - The
Solver performs all constraint satisfaction tasks, ie. maintains the
set of
**constraints**, the variable domains and applies when appropriate the consistency algorithms. The Solver returns the results to the core.

*(Up to 4
Solver Libraries)*

CSP

Process

(core)

Constraint

Library

(solver)

Constraint

Library

(solver)

ISKP
Group - CLP Applications 2005

28

Current
Status and Future Work

- Current version of CSPCONS, includes:
- Finite
Domain Solver (AC-2000 propagation,
*all_different*global constraint, etc). - Experimental Linear Equations Solver
- Platforms
- Solaris
- Linux
- Windows
- Future Work
- Improve Solver
- Include
more global
**constraints** - Test on more Applications

ISKP
Group - CLP Applications 2005

29

Distributed Workforce Management (DIWOMS)

ISKP
Group - CLP Applications 2005

30

Distributed
Workforce Management System (DIWOMS) (1/2)

- Problem definition
- allocation of jobs to workers, in such a way that the total number of assigned tasks is maximised, with the minimum transition time between tasks.
*Multiple time constraint travelling salesman problem*- Problem Data
, geographically distributed,*250 jobs*, with different attributes (skill, start/end time),*118 technicians*where the technicians belong to,*11 bases*for each job,*skill***constraints**and a*travel time*determining the quality of the solution.*cost function*

ISKP
Group - CLP Applications 2005

31

The
BT Problem

Spatial visualization of Jobs, Bases and Personnel

ISKP
Group - CLP Applications 2005

32

A
Three Phase Solving Approach

- A clustering phase
- Partitioning the problem to a number of subproblems of less complexity.
- Each subproblem is assigned to an agent.
- A solving phase
- Agents independently solve each subproblem.
- A patching phase
- Agents cooperate to find the final job assignments.

ISKP
Group - CLP Applications 2005

33

Implementation

- Each base is modeled as an agent.
- All agents execute the same algorithm.
- Each agent is implemented as a CSPCONS process.
- Communication during the clustering and optimization phase is achieved via channels.
- Solution phase uses the CLP primitives of CSPCONS:

**find_job_details(JobID,Start,Duration):-
job(JobID,Type,Duration,_), job_limits(Type,MinStart,MaxStart), clp_constraint([Start
in **

**
[MinStart..MaxStart]]). **

ISKP
Group - CLP Applications 2005

34

Results

- Implemented in a Sun E 450
- 4 Processors, 2GB RAM, Solaris 2.8
- Solution is near the optimal reported in the literature.

21.948

24.912

**Total Cost**

67(63+4+0)

63

**Active Techs**

190(165+23+2)

165

**Scheduled
Jobs**

**Final Solution**

**First Solution**

ISKP
Group - CLP Applications 2005

35

Final Solution (technician tours) and Clusters (generated during the first phase) visualized over the problem area

Distributed Singleton Consistency (DSAC)

ISKP
Group - CLP Applications 2005

37

Singleton
Arc Consistency

- Singleton Arc Consistency (SAC)

*(Debruyne-Bessière
1997)*

- Basic Idea
- For
every value
*d*_{i of a variable xi that is consistent, the sub-problem P obtained by restricting the domain Di to di is consistent.} _{Any value that fails to satisfy the above is removed from the domain, i.e. if the sub-problem is determined to be inconsistent then the value is removed. }_{Characteristics of the Algorithm}_{Enforces stronger consistency than most AC algorithms, i.e. removes a larger set of values. }_{Costly application.}_{Solution: Distributed execution of the SAC algorithm. }

ISKP
Group - CLP Applications 2005

38

Distributed
Singleton Arc Consistency

- Reduce execution time by distributing work to be done to a number of agents.
- A society of agents apply the SAC algorithm on the problem variables.
- Each agent applies SAC on a subset of the original set of variables (responsibility set)
- Removed values are communicated via message passing.
- Different Broadcasting Policies can be applied.
- A Scheduler is responsible for detecting termination.

ISKP
Group - CLP Applications 2005

39

*Χ*_{1,Χ2,Χ3,X4,Χ5,Χ6}_{,X7,X8,X9}

_{Χ1,Χ2,Χ3}_{,X4,Χ5,Χ6,X7,X8,X9}

_{Χ1,Χ2,Χ3}_{,X4,Χ5,Χ6}_{,X7,X8,X9}

_{DSAC
Agents}

_{Scheduler}

_{Responsibility
Set }

_{Value Removal
Messages}

_{Termination
Control Messages }

ISKP
Group - CLP Applications 2005

40

Impementing
DSAC

- First Version
- Java
Constraint Library for implementing
**constraints**. - Pathwalker lib for communication between agents.
- Experiments
- 3 Sun Ultra-5
- 1 Sun Enterprise 450 (4 Processors)

ISKP
Group - CLP Applications 2005

41

SpeedUp

ISKP
Group - CLP Applications 2005

42

Implementation
in CSPCONS

- The DSAC algorithm is simple and requires no major modifications to the underlying implementation platform.
- Network of SUN Workstations
- All measurements concern wall time.
- Problems
- Golomb Rulers
- A set of m different integers such that the m(m-1) differences between the integers are distinct.
- The length of the ruler is minimum.
- Quasigroup Completion
- Completing a partially filled Latin Square.

ISKP
Group - CLP Applications 2005

43

Experimental Results: Golomb Rulers

ISKP
Group - CLP Applications 2005

44

Experimental Results: Latin Squares

ISKP
Group - CLP Applications 2005

45

Conclusions
and Future Work

- Distributed Singleton Consistency improves significantly the performance of the algorithm.
- Simple but efficient.
- Easy to implement.
- Future Work
- More
"
**intelligent**" assignment of responsibility sets. - Heuristics during the application of SAC in each agent.

Protein
Structure Prediction in CLP

A Recent Approach

ISKP
Group - CLP Applications 2005

47

Recent
Approach to Protein Folding

- The approach follows a lattice model (fcc).
- Proposed in:
*A. Dovier, M. Burato, and F. Fogolari.Using Secondary Structure Information for Protein Folding in CLP(FD). In Proc. of Workshop on Functional and Constraint Logic Programming, ENTCS vol. 76, 2002.**A. Dal Palù, A. Dovier, and F. Fogolari. Constraint Logic Programming approach to protein structure prediction. BMC Bioinformatics 2004, 5:186, 30 November 2004.**A. Dal Palu', A. Dovier, and E. Pontelli. Heuristics, Optimizations, and Parallelism for Protein Structure Prediction in CLP(FD). To appear in PPDP'05.*

ISKP
Group - CLP Applications 2005

48

Proteins

- A protein is a list of linked units called aminoacids.
- There are 20 different kinds of aminoacids
*Alanine (A) Cysteine (C) Aspartic Acid (D) Glutamic Acid (E) Phenylalanine (F) Glycine (G) Histidine (H) Isoleucine (I) Lysine (K) Leucine (L) Methionine (M) Asparagine (N) Proline (P) Glutamine (Q) Arginine (R) Serine (S) Threonine (T) Valine (V) Tryptophan (W) Tyrosine (Y)*- Typical length of a protein is 100-500 units.
- Protein Structure Prediction
- Predicting the 3D structure of proteins, given their primary and secondary structure

ISKP
Group - CLP Applications 2005

49

Protein
Structure

- Protein Structure Prediction
- Predicting the 3D structure of proteins, given their primary and secondary structure
- Primary structure
- sequence of aminoacids (residues)
- Secondary Structure
- a-helix, β-sheets
- ssbonds (disulfide bridges from cystein residues)
- Tertiary Structure
- Admissible spatial positions of each aminoacid in 3D
- State
of minimum free energy (
*Anfinsen thermodynamic hypothesis)*

ISKP
Group - CLP Applications 2005

50

Optimization
Problem

- Optimization Problem
- Since the tertiary structure is the state with the minimum free energy:
- Define the energy function, that in general depends on distances between residues and their type.
- Minimize the energy function
- Assumptions
- Aminoacids are considered as a whole (sphere).
*Consecutive*amino acids have a fixed distance.- Energy
function is the sum of energy contributions of
*non-consecutive*aminoacids. - Energy contribution given by a potentials matrix for each combination of aminoacids.

ISKP
Group - CLP Applications 2005

51

Potentials
Matrix (part)

...

...

...

...

...

...

...

...

**...**

...

-2.222

-2.447

-2.501

-2.647

-2.491

-2.208

-2.343

**LEU**

...

-2.303

-2.568

-2.647

-2.691

-2.530

-2.286

-2.410

**LE**

...

-2.286

-2.391

-2.491

-2.530

-2.467

-2.304

-2.424

**PHE**

...

-2.090

-2.079

-2.208

-2.286

-2.304

-1.901

-2.240

**MET**

...

-2.080

-2.258

-2.343

-2.410

-2.424

-2.240

-3.477

**CYS**

**...**

**TRP**

**VAL**

**LEU**

**ILE**

**PHE**

**MET**

**CYS**

ISKP
Group - CLP Applications 2005

52

Problem
Description-**Constraints **

- Given a sequence of aminoacids that constitute the protein.
- s
_{1, s2, s3, ... sn} _{For aminoacid si define a point <x,y,z> that represents its position in 3D space.}_{x,y,z real numbers }_{x,y,z integer numbers (lattice models)}_{Two constraints }_{consecutive aminoacids in chain have a fixed distance (next )}_{two aminoacids cannot have the same position }

ISKP
Group - CLP Applications 2005

53

Problem
Description-Energy Function

- Non-consecutive
aminoacids contribute to the energy when are in contact, i.e. have a
distance less than a given threshold (are in
*contact*). - Energy function

ISKP
Group - CLP Applications 2005

54

Modeling
Space-Lattice Model

- Face-Centered
Cubic Lattice Model (fcc model) *

** (G. Raghunathan and R. L. Jernigan. 1997)* - Cubes of size 2.
- Distance between residues 2
- Residues are on
- Central point of face
- Vertices

ISKP
Group - CLP Applications 2005

55

Closer Look to the FCC model

Side Size 2

Distance 2
(Lattice Unit)

Positions

ISKP
Group - CLP Applications 2005

56

**Constraints **

- X,Y,Z variables for each aminoacid.
- Position Restrictions
- x+y+z is even.
- Given
two consecutive aminoacids s
_{i, si+1 (next)}

_{|xi-xi+1| }_{ }_{
{0,1}, |yi-yi+1| }_{ }_{ {0,1},
|zi-zi+1| }_{ } _{ {0,1}}

_{|xi-xi+1|
+ |yi-yi+1| + |zi-zi+1| = 2}

_{Two non-consecutive amino acids must have a distance of more than a lattice unit}

_{(xi-xj)}^{2
+ (y}_{i-yj)}^{2 + (z}_{i-zj)}^{2 >
2}

ISKP
Group - CLP Applications 2005

57

**Constraints **

- Admissible angles between 3 consecutive aminoacids
- FCC model: 60, 90, 120, 180
- Allowed: 90, 120 (volumetric + energetic cons)
- Constraint concerning angles
- scalar
product between vectors V
_{i-1,i and Vi,i+1} _{Scalar product should be {0,1}}_{Constraints concerning secondary structure}_{two animoacids with an ss-bond must be close.}_{strands}_{helix}

ISKP
Group - CLP Applications 2005

58

Example
of Modeling A Constraint in CLP(FD) (1/2)

- The Next Constraint

**next(X1,Y1,Z1,X2,Y2,Z2):-**

**domain([DX,DY,DZ],0,1),**

**DX
#= |X1-X2|,**

**DY
#= |Y1-Y2|,**

**DZ
#= |Z1-Z2|,**

**DX+DY+DZ
#= 2.**

ISKP
Group - CLP Applications 2005

59

Example
of Modeling A Constraint in CLP(FD)

- The non-next constraint

**non_next(X1,Y1,Z1,X2,Y2,Z2):- **

**
Dx #= (X1-X2) * (X1-X2),**

**
Dy #= (Y1-Y2) * (Y1-Y2),**

**
Dz #= (Z1-Z2) * (Z1-Z2),**

**
sum([Dx,Dy,Dz], #>, 2). **

ISKP
Group - CLP Applications 2005

60

SS
Bond **Constraints **

- SS Bond

**ssbond([X1,Y1,Z1],[X2,Y2,Z2]):-**

**
Dx #= abs(X1-X2),**

**
Dy #= abs(Y1-Y2),**

**
Dz #= abs(Z1-Z2),**

**
Dx #=< 4,**

**
Dy #=< 4,**

**
Dz #=< 4.**

ISKP
Group - CLP Applications 2005

61

Energy
Function

- Reified constraint

**... **

**
El in {0,Pot},**

**
DX #= abs(X1 - X2),**

**
DY #= abs(Y1 - Y2),**

**
DZ #= abs(Z1 - Z2),**

**
2 #= DX + DY + DZ #<=> El #= Pot.**

ISKP
Group - CLP Applications 2005

62

Search

- Variable Selection
- Assign value to variables adjacent to ground vars.
- Bounded Block Fails Heuristic
- Block = sublist of vars that are unbound
- Try labeling in each block in turn.
- If labeling in a block fails, backtracking to the previous block.
- If a block fails too many times (threshold) backtracks not to the previous but to one before that.

ISKP
Group - CLP Applications 2005

63

Results

- Implementation
in SICStus
**Prolog** - Tested up to proteins of size 80.
- Time varies between 1sec and 10 hours on a PC.
- Parallel CLP version.

Future Directions

- New Heuristics
- New
dedicated global
**constraints**/solver.

ISKP
Group - CLP Applications 2005

64

Protein
Prediction Structure in CSPCONS

- Initial Experimental Version
- Porting original code to CSPCONS
- AIMS:
- Investigating benefits from applying DSAC in the problem.
- Investigating new heuristics.
- Re-writing
non-linear
**constraints**to linear. - New Modeling?

ISKP
Group - CLP Applications 2005

65

References

*«Constraint Programming: In Pursuit of the Holy Grail»*Roman Bartak*Survey: Practical Applications of Constraint Programming,*Mark Wallace.*Constraint Logic Programming,*Pascal van Hentenryck*Constraint Logic programming: A survey*, J. Jaffar and Lassez.*Parallel and Constraint Logic Programming*, I. Vlahavas, P. Tsarcopoulos and I. Sakellariou, Kluwer Academic Publishers*Constraint Programming for Industrial Applications*, H. Simonis presentation.- Ideal architecture of residue packing and its observation in protein structures. Protein Science, 6:2072-2083, 1997. G. Raghunathan and R. L. Jernigan. 1997
*A. Dovier, M. Burato, and F. Fogolari.Using Secondary Structure Information for Protein Folding in CLP(FD). In Proc. of Workshop on Functional and Constraint Logic Programming, ENTCS vol. 76, 2002.**A. Dal Palù, A. Dovier, and F. Fogolari. Constraint Logic Programming approach to protein structure prediction. BMC Bioinformatics 2004, 5:186, 30 November 2004.**A. Dal Palu', A. Dovier, and E. Pontelli. Heuristics, Optimizations, and Parallelism for Protein Structure Prediction in CLP(FD). To appear in PPDP'05.*

Constraint
Logic Programming

Applications

Thanks.