- 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

**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.

- Generate a full matrix \(x_{L,d}\) and add constraints \(x_{L,d}=0\) if an assignment is not allowed.
- 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 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

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

## No comments:

## Post a Comment