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 Prolog processes that communicate via a message passing mechanism over channels.
• 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
• 250 jobs, geographically distributed, 118 technicians, with different attributes (skill, start/end time), 11 bases where the technicians belong to, skill constraints for each job, travel time and a cost function determining the quality of the solution.

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.