Contraint Programming Introduction

Share on facebook
Share on twitter
Share on linkedin
Share on pinterest
Share on whatsapp

Constraint Programming is a valuable  tool for solving different types of optimization problems (especially industrial programming problems). So today we’re going to introduce some basic definitions and the conceptual model behind it.

Constraint optimization, orconstraint scheduling (CP), is the name given to identifying feasible solutions from a very large set of candidates, where the problem can be modeled in terms of arbitrary constraints. CP is based on feasibility rather than optimization and focuses on constraints or variable domains instead of the target function.

We will dissect the solution of the “4 Queens Problem” example, which is to place four queens on a 4 x 4 chessboard so that they cannot be captured from each other, to demonstrate the concepts behind CP. We start by translating the problem into a mathematical model with variables and constraints. The solver then uses Backtracking toreach the solution.  

Variables represent  some decisions. They can contain any value included in their range or domain. In our problem we create variables for each box on the board. Each variable takes the value 1 if a queen is present in the given box, otherwise it is 0.

Constraints   prevent variables from taking arbitrary values. You cannot place two queens in the same row, same column, or diagonal.

Propagation –Variables can have different values, but the  solver  must delete some of those values to maintain all variables supported by the model.

Backtracking– Occasionally, the  solver is locked because it tries to assign some values to some variables that are simply not possible (or desirable) because they do not respect constraints. You need to rethink your previous choices and test other values. Backtracking also occurs when the solver  finds  a solution, but it is interested in continuing the search to find other solutions.

Now let’s see how the CP solver  comes to the solution for our problem:

1. You could start by placing the Queen in the upper left corner, so the corresponding variable is assigned to 1. Propagating constraints would cause the other variables in the top row, left column, and main diagonal to be assigned to 0, because no other Queen can already occupy these positions.

2. After a few steps, the solver  may encounter the following situation:

It is not possible to place the Queen in the third column without violating the restrictions. Therefore, you must go back and review your previous decision to place the Queen in the third row of the second column. That’s Backtracking.

3. After several propagation and resolution cycles, the solver hopes  to reach the solution:

Now let’s see how we would program this solution using ConstraintSolver  from the Google OR-Tools library:

 

  1. var n = 4; var solver = new Solver(“N-Queens”); // // Decision variables. q[i] row in i-th column where we place the queen // var q = solver.MakeIntVarArray(n, 0, n – 1, “q”); // // Constraints // solver.Add(q.AllDifferent()); var q1 = new IntVar[n]; var q2 = new IntVar[n]; //The following sets the constraint that no two queens can be on the same diagonal. for (int i = 0; i < n; i++) { q1[i] = (q[i] + i).Var(); q2[i] = (q[i] – i).Var(); } solver.Add(q1.AllDifferent()); solver.Add(q2.AllDifferent()); // // Search // var db = solver.MakePhase(q, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE); solver.NewSearch(db); var s = 1; while (solver.NextSolution()) { Console.WriteLine($”Solution {s++}: “); for (int i = 0; i < n; i++) { Console.Write(“{0} “, q[i].Value()); } Console.WriteLine(string.Empty); } solver.EndSearch();

 

In this example, 4 variables, one per row, have been used, which can take values between 0 and 3, indicating the column where the Queen would be placed.

And the result is:

Solution1: 1 3 0 2

Solution2: 2 0 3 1

Basically, that’s all. Happy programming!

You might also like

Environmental sustainability: real actions at Aquiles Solutions
  Thanks to a number of intiatives around the world...
AQUILES Solutions at Iberquimia Digital
This week AQUILES Solutions is participating in the second edition...
5 steps to avoiding wrong AI projects implementation
The need to implement latest technologies and new approaches into...