Python constraint solver

In [1] a small problem is stated:

• We need to assign 7 devices to 3 locations
• The maximum number of devices assigned to a location is: loc1:3, loc2:4, loc3:2
• Not all assignments are allowed. The allowed assignments are:
     loc1: device1, device3, device7,
     loc2: device1, device3, device4, device5, device6, device7
     loc3: device2, device4, device5, device6
• Find all possible solutions

There is no objective and we need to enumerate all solutions. It makes sense to look at a Constraint Programming (CP) solver. A simple one is Python-constraints [2].

This looks like an assignment problem so we can define the decision variable: \[x_{L,d} = \begin{cases} 1 & \text{if device $d$ is assigned to location $L$} \\ 0 & \text{otherwise}\end{cases}\]

There are two main approaches to deal with the assignments that are not allowed.

1. Generate a full matrix \(x_{L,d}\) and add constraints \(x_{L,d}=0\) if an assignment is not allowed.
2. Generate only the variables \(x_{L,d}\) that are allowed.

I am partial to the second approach. With modern solvers there may not be much reason for this, but I have the feeling I know more what I am doing if I pay attention to such things. It forces me to be less sloppy.

The constraints are not very difficult:\[\begin{align} &\sum_{L|\mathit{allowed}(L,d)} x_{L,d} = 1 &\forall d\\ & \sum_{d|\mathit{allowed}(L,d)} x_{L,d} \le \mathit{MaxDev}_L& \forall L \end{align}\]

The Python code can look like:

from constraint import *

D = 7 # number of devices
L = 3 # number of locations

maxdev = [3,4,2]
allowed = [[1,3,7],[1,3,4,5,6,7],[2,4,5,6]]

problem = Problem()
problem.addVariables(["x_L%d_d%d" %(loc+1,d+1) for loc in range(L) for d in range(D) if d+1 in allowed[loc]],[0,1])
for loc in range(L):
    problem.addConstraint(MaxSumConstraint(maxdev[loc]),["x_L%d_d%d" %(loc+1,d+1) for d in range(D) if d+1 in allowed[loc]])
for d in range(D):
    problem.addConstraint(ExactSumConstraint(1),["x_L%d_d%d" %(loc+1,d+1) for loc in range(L) if d+1 in allowed[loc]])

S = problem.getSolutions()
n = len(S)
n

As you can see, I use the allowed list everywhere to restrict the tuples \((L,d)\). This solves very fast. There are 25 solutions for this small problem:

Notes:

• If you want to solve this as a MIP use a dummy objective, and preferably use the solution pool technology available in solvers like Cplex and Gurobi. This is also very fast. The picture above was from a GAMS/Cplex run.
• I expect the number of the solutions to quickly rise when the problem becomes bigger.
• The Python code above assume short lists of allowed devices in each location. If these lists become long, it is better to use a different data structure such as dicts.
• I don't think the Python code is very easy to read. I don't immediately recognize our mathematical constraints in the code.

References

1. Python constraints - constraining the amount, https://stackoverflow.com/questions/49655875/python-constraints-constraining-the-amount
2. Python-constraint, Constraint Solving Problem resolver for Python, https://labix.org/python-constraint