Constraint Programming

There are many programming paradigms out there. The following ones are probably the most known programming paradigms: imperative, declarative, procedural, object-oriented, functional, logic, event-driven, parallel, aspect-oriented, constraint, and so on.

These programming paradigms are not mutually exclusive, because many programming languages support multiple paradigms. Take Python as an example. Python can be used to write imperative, functional, declarative or object-oriented code. Or Java, it is object-oriented, functional, reflective, and parallel (aka concurrent) programming language.

Constraint programming

Constraint programming works in a way where we first define relationships and constraints on variables, without explicitly defining the sequence of steps to reach a solution, and then let a solver to find solutions that satisfy those constraints.

The most usual paradigms to solve programming tasks are — imperative and declarative programming (maybe we could also say functional and object-oriented, but let’s not go there as it is not the point in this article).

Imperative programming — we provide explicit instructions to the computer on how to perform a task step by step.

List<Customer> customers = new ArrayList<>();
customers.add(new Customer("John", "USA"));
customers.add(new Customer("Alice", "Canada"));
customers.add(new Customer("Bob", "USA"));
customers.add(new Customer("Eva", "USA"));

List<Customer> usaCustomers = new ArrayList<>();
for (Customer customer : customers) {
    if ("USA".equals(customer.getCountry())) {
        usaCustomers.add(customer);
    }
}

Declarative programming — we say what we want to get without specifying how to achieve it. We focus more on describing the result rather then the steps to get there.

SELECT * FROM Customers WHERE Country = 'USA';

Constraint programming — we define constraints and let the solver to find one or many solutions. We are going to explore how to do exactly that in the next section.

Introduction into Constraint programming

Imagine we have two variables x and y. We know that x*2 + y/2 have to be smaller or equal to 10. We can say, just by looking at the example, that when x=1 and y=1, we fulfill that condition.

This is very easy task to describe and solve, kind of “Hello world” level task. We are going to use MiniZinc constraint modeling language to implement that.

var 1..10: x;
var 1..10: y;

constraint x*2 + y/2 <= 10;

solve satisfy;

output ["x=", show(x), ", y=", show(y)];

If you want to try to execute the code, download their IDE here.

When we execute the code, we get following output: x=1, y=1.

Now, let’s ask the program different question. What is the maximum value of x while still satisfying the constraint?

var 1..10: x;
var 1..10: y;

constraint x*2 + y/2 <= 10;

solve maximize x;

% Output the solution
output ["x=", show(x), ", y=", show(y)];

We are going to get the following answer: x=4, y=1.

MiniZinc IDE

We can also end up in situation where there is no satisfiable solution. Here is an example, where we x is starting from 1, and if we multiply it by 20, it never equal to 10. When we execute the following code, we will get =====UNSATISFIABLE===== as a response.

var 1..10: x;

constraint x*20 = 10;

solve satisfy;

output ["x=", show(x)];

Using multiple constraints

Let’s create an example, where we define three tasks:

• Task 1 takes 2 hours
• Task 2 takes 3 hours
• Task 3 takes 4 hours

Now we can define the possible starts for each task and the constraints, in the way to say that task 2 can only start after task 1 is finished, and that task 3 can start only after the task 2 is finished.

% Declare the durations of three tasks (in hours)
int: duration_task1 = 2;
int: duration_task2 = 3;
int: duration_task3 = 4;

% Declare start times for each task (these are the possible starts)
var 0..10: start_task1;
var 0..10: start_task2;
var 0..10: start_task3;

% Constraints to ensure tasks are scheduled sequentially
constraint start_task1 + duration_task1 <= start_task2;
constraint start_task2 + duration_task2 <= start_task3;

output [
  "Task 1 starts at time ", show(start_task1), ", ",
  "Task 2 starts at time ", show(start_task2), ", ",
  "Task 3 starts at time ", show(start_task3)
];

When we run the code above, we get the following output: Task 1 starts at time 0, Task 2 starts at time 2, Task 3 starts at time 5.

Now we can rewrite this in more generic way, so it would work for any amount of tasks:

set of int: Tasks = {1, 2, 3};
array[Tasks] of int: duration = [2, 3, 4];  

array[Tasks] of var 0..10: start;

constraint forall(t1, t2 in Tasks where t1 < t2)(start[t2] >= start[t1] + duration[t1]);

solve minimize max(t in Tasks)(start[t] + duration[t]);

output ["Task start times: ", show(start), "\n"];

Real world applications for Constraints programming

Here are some ideas and reasoning for use cases that might be a perfect fit for constraints programming:

• Scheduling — because of limited resources, time constraints. For example: meeting scheduling, airline crew scheduling, shifts.
• Planning — because of limited resources, , deadlines, delays, time constraints, budget constraints, risks, decision-making rules, and dependencies between the tasks. For example: project planning, financial planning, production planning.
• Optimization — because of limited capacity, travel distances, resource availability. For example: cost minimization, efficient resource utilization, improved logistics.
• Resource allocation: because of limited availability of resources, dependencies between schedules. For example: classroom assignments.
• Puzzle solving and games: because of the game rules, dependencies between game elements. For example: Sudoku, or maybe even game AI.

Example: Meeting scheduling

Few years ago, we were building an application that was supposed to help users to schedule meetings across various timezones considering availability of multiple people and meeting rooms. The imperative code we wrote got very complex very quickly and this use case came on my mind, thinking “I have to try to implement it and see how easy it is, because scheduling meeting where people and meeting rooms have many constraints and it seems like a perfect case for constraints programming”.

Here is the code, it contains comments with more details:

% Define the number of time slots in a day, one per hour
int: num_slots = 24;

% Define the number of meeting rooms
int: num_rooms = 2;

% Hard-coded schedules for person 1, person 2, and meeting rooms
array[1..num_slots] of var 0..1: schedule_person1 = 
   [0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0];
array[1..num_slots] of var 0..1: schedule_person2 = 
   [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0];

array[1..num_rooms, 1..num_slots] of var 0..1: schedule_rooms = array2d(1..num_rooms, 1..num_slots, 
  [
    0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0,
    0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1
  ]
);

% Decision variables for the meeting time slot and room
var 1..num_slots: meeting_time_slot;
var 1..num_rooms: meeting_room;

% Meeting time slot must be available for both persons and in the chosen room
constraint schedule_person1[meeting_time_slot] = 0;
constraint schedule_person2[meeting_time_slot] = 0;
constraint schedule_rooms[meeting_room, meeting_time_slot] = 0;

% Objective: Minimize the meeting time slot
solve minimize meeting_time_slot;

% Output the schedules for person 1 and person 2
output ["Schedule for Person 1: ", show(schedule_person1), "\n"];
output ["Schedule for Person 2: ", show(schedule_person2), "\n"];

% Output the schedule for meeting rooms
output ["Schedule for Meeting Rooms:\n", show2d(schedule_rooms), "\n"];

% Output the result
output [
    "Meeting scheduled at time slot ", show(meeting_time_slot),
    " in meeting room ", show(meeting_room)
];

The code would get more complex, because we might want to create slots by 15 minutes, instead of 1 hour, we might need to put there multiple days and not just one, and mainly, we might want to add or change the constraints dynamically based on user’s request and prefferences. But still, it might be a better way to implement meeting scheduling than implementing it in imperative style.

Using Constraint programming in production

MiniZinc is a nice constraint modeling language but the question is how to use it in production.

MiniZinc Python & JavaScript interfaces

There are Python https://www.minizinc.org/doc-2.7.6/en/python.html and JavaScript https://www.minizinc.org/doc-2.7.6/en/javascript.html interfaces for MiniZinc.

We will execute the following MiniZinc script in Python and print out the value of x and y to demonstrate how we could use MiniZinc in our backend services.

Here is the script we want to execute on the backend:

var 1..10: x;
var 1..10: y;

constraint x*2 + y/2 <= 10;

solve maximize x;

Python solution (first, install pip install minizinc):

import minizinc

minizinc_model = """
var 1..10: x;
var 1..10: y;

constraint x*2 + y/2 <= 10;

solve maximize x;
"""

model = minizinc.Model()
model.add_string(minizinc_model)

solver = minizinc.Solver.lookup("gecode")

instance = minizinc.Instance(solver, model)

result = instance.solve()

print(result["x"], result["y"])

There is the following library for JavaScript (both web and NodeJS) https://github.com/MiniZinc/minizinc-js. But the configuration is quite tedious.

Other options: Java libraries

JaCoP

I tried to use JaCoP (https://github.com/radsz/jacop/) library, but didn’t get too far. It is missing documentation and I didn’t have enough time and energy to study their code and APIs (which is not intuitive).

Choco

Then I found Choco solver (https://github.com/chocoteam/choco-solver), which seems to be well maintained and also API look very usable and easy to understand (it is available for Java and Python).

First, provide the dependency in Gradle (Kotlin):

implementation("org.choco-solver:choco-solver:4.10.14")

Now we can implement our simple example in Java:

import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solution;
import org.chocosolver.solver.variables.IntVar;

import java.util.List;

public class Main {
    public static void main(String[] args) {
        Model model = new Model();
        IntVar x = model.intVar("x", 1, 10, false);
        IntVar y = model.intVar("y", 1, 10, false);

        model.arithm(x.mul(2).intVar(), "+", y.div(2).intVar(), "<=", 10).post();

        List<Solution> solutions = model.getSolver().findAllSolutions();
        System.out.println("The problem has " + solutions.size() + " solutions : ");

        for (Solution s : solutions) {
            System.out.println("x = " + s.getIntVal(x) + " and y = " + s.getIntVal(y));
        }
    }
}

When executed, it prints out all solutions to the equation:

The problem has 35 solutions : 
x = 1 and y = 1
x = 1 and y = 2
x = 1 and y = 3
x = 1 and y = 4
... and so on

Here is the documentation: https://choco-solver.org/docs/

Here are the examples, really great set of examples which helps a lot:

• Sudoku model
• Knapsack problem model
• N Queen problem model

There is more

Here is a list of other languages and libraries I was able to find that seemed to be somewhat relevant:

• https://pypi.org/project/python-constraint/ (Python)
• https://www.optaplanner.org/ (Java, Kotlin, Scala, Python)
• https://github.com/eomahony/Numberjack (Python)
• https://github.com/google/or-tools (Google tool for for solving combinatorial optimization problems)
• https://www.gecode.org/ (C++)
• https://bitbucket.org/oscarlib/oscar/wiki/Home (Scala)
• http://www.eclipseclp.org/ (looks like from year 1995)