Solving Constraints Optimization Problem with Python

Constraint Optimization is the class of problems that requires identifying feasible solution among a very large set of possibilities. The problem can be modelled in terms of contraints

Constraint Optmization(also called Constraint Programming – CP) is based on finding a feasible solution(feasibility) rather than finding an optimal solution(optimization). Unlike normal linear, programming, the focus here is on the constraints rather than on the cost function.

Employee Scheduling Example

A typical example of where CP is applied is in the employee scheduling. For instance, a company that runs 3 8-hour daily shift for its employee. And there are four employees. Three of the 4 employees need to be assigned to different shift each day while the 4th employee has a day off. Here you can see that the number of possible schedules is much – 4! = 4 * 3 * 2 * 1 = 24. For a week we have 247. That is very much! Therefore, to narrow down the number, we need to apply some constraints.For example, each employee must work certain minimum number of days in a week. CP allows us to keep track of solutions that remains feasible as constraints are added.

A Simple Example with Python

There are three variables x, y and z that could assume on of three values: 0, 1, 2.

There is once constraint that says: x ≠ y

Solution

We follow 5 steps to solve this problem in Python

Step 1: Declare your model

You will first import the cp_model from ortools.sat.python

# Declare the model
from ortools.sat.python import cp_model
model = cp_model.CpModel()

Step 2: Define the variables: x, y and z

# Define your variables
num_vars = 3
x = model.NewIntVar(0, num_vars - 1, 'x')
y = model.NewIntVar(0, num_vars - 1, 'y')
z = model.NewIntVar(0, num_vars - 1, 'z')

Step 3: Add the constraint

In this case, we have only one constraint: x ≠ y

# Add the constraint
model.Add(x != y)

Step 4: Invoke the solver

You must call  the CpSolve() method of the solver

# Invoke the solver
solver = cp_model.CpSolver()
status = solver.Solve(model)

Step 5: Display your results

In this case we would display the optimal solution

# Display the results
if status == cp_model.OPTIMAL:
    print('x = %i' %solver.Value(x))
    print('y = %i' %solver.Value(y))
    print('z = %i' %solver.Value(z))

The output is shown below:

x = 1
y = 0
z = 0

The complete program shown below displays all the the results, not just the optimal one.