CLP #1: What is CLP?

Code	GitHub
Part 2	Einstein’s Riddle
Part 3	Scheduling Problem
Part 4	Optimization Problem

Introduction

Let’s start with explaining the abbreviation mentioned above. CLP (Constraint Logic Programming) is a form of constraint programming, which is a kind of a declarative approach. The main goal of CLP is to find solutions that will satisfy (all) imposed constraints.

Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it.

Eugene C. Freuder
CONSTRAINTS, April 1997

The general path of the solution:

1. Observation - thorough analysis of the problem to be solved;
2. Model - determining what conditions / relationships (presented as equations or inequalities) occur in a given problem;
3. Simulation - implementation all of these constraints to find a solution.
   
   

Solution - an assignment (of values to variables), which satisfies constraints.

How can we describe constraint in the simplest way? It’s a conglomeration of:

• Variables:    \(A, B, List\)
• Function symbols:    \(+, -, sin\)
• Relation symbols:    \(=, <\)

\(e.g.\)   \(A < 2\)    \(3A + 2B = 10\)

Note! The order of applying further constraints can change the solution. This is due to the algorithms used.

Simple Example

We have two sets:
\(A = { 4, 5, 6, 7, 8, 9, 10 }\)
\(B = { 3, 4, 5, 6 }\)

We want to find a pair of numbers that will satisfy the following constraints:
\(A>B\)
\(A+B=9\)

After a moment of reflection, we come to the conclusion that the solution may be:
\(A = 5, B = 4\)
\(A = 6, B = 3\)

As we can see, it was not difficult, but let us note that the example was trivial. You can try to imagine more sets and relationships between them.

CLP can be used to solve problems such as:

• Einstein’s Riddle;
• N-Queen problem;
• Knapsack problem;
• Scheduling.

How to Start

Let’s face facts, Java is one of the most popular programming languages. For this reason, it also has many libraries. The one that is meant for CLP is called JaCoP (download). You can find the user’s guide here.

After downloading the library, we must attach it to our project and paste the following lines of code:

import org.jacop.core.*;
import org.jacop.constraints.*;
import org.jacop.search.*;

Now we can start writing our program. We will need:

1. Some place for storing CLP variables;
2. An array for storing all sets;
3. Defined constraints - we will use the special impose() function for this purpose.

// Store for CLP variables
Store store = new Store();

// Array of sets
IntVar[] vars = new IntVar[2];

// Defining sets
vars[0] = new IntVar(store, "A", 4, 10);
vars[1] = new IntVar(store, "B", 3, 6);

// Imposing constraints
store.impose( new XgtY(vars[0], vars[1]) );
store.impose( new XplusYeqC(vars[0], vars[1], 9) );

Note that the representation of our set \(A\) will be vars[0], and the set \(B\) vars[1]. We will use this knowledge when imposing constraints.
XgtY means \(X>Y\) (gt - greater than) and XplusYeqC means \(X+Y=Const\) (eq - equal). You can find the whole list in the user’s guide.

Now we can look for a solution. We do this by adding the following lines to our program:

Search label = new DepthFirstSearch(); 
SelectChoicePoint select = new InputOrderSelect(store, vars, new IndomainMin());
label.labeling(store, select); 

Without going into details, we define here how we want to find a solution. As we know, there are 2 possible solutions in our example. However, the program result returns only one.

To see the second solution, we can change “new IndomainMin()” into “new IndomainMax()”. There is also a way to display all possible solutions.

Search label = new DepthFirstSearch(); 
label.getSolutionListener().searchAll(true); 
SelectChoicePoint select = new InputOrderSelect(store, vars, new IndomainMin());
label.getSolutionListener().recordSolutions(true); 
label.labeling(store, select);
label.printAllSolutions();

Summary

In conclusion, I hope that I have explained well what CLP is and I showed it is not so difficult. More advanced examples show its strength and become practically unfeasible for humans. In case of any problems, you can post comments below. In turn, the entire program can be found here.