Python Limitations - Limit Amount

Question

I have a constraint problem that I am trying to solve with python-constraint

So let's say I have 3 places: loc1,...loc3

In addition, I have 7 devices: device1,...device7

The maximum number of devices in each location: loc1:3, loc2:4, loc3:2 (for example, a maximum of 3 devices in loc1 , etc.)

And some restrictions regarding locations and devices:

loc1: device1, device3, device7 ,

loc2: device1, device3, device4, device5, device6, device7

loc3: device2, device4, device5, device6

(for example, only device1 , device3 and device7 can be in loc1 .)

I am trying to get a set of possible parameters for devices in places.

  from constraint import * problem = Problem() for key in locations_devices_dict: problem.addVariable(key,locations_devices_dict[key]) # problem.addVariable("loc1", ['device1', 'device3', 'device7']) problem.addConstraint(AllDifferentConstraint()) 

and I was fixated on how to make restrictions. I tried:

 problem.addConstraint(MaxSumConstraint(3), 'loc1') 

but it does not work, MaxSumConstraint does not summarize what I need.

All devices must be placed somewhere

Possible Solution:

 loc1: device1, device3 loc2: device4, device6, device7 loc3: device2, device5 

Does anyone have an idea?

(another python package / not using any package, also a good idea if anyone has suggestions ...)

Answer 1

edit: I wrote this answer before I saw @ErwinKalvelagen code. Therefore, I did not check his solution ...

So, I used the @ErwinKalvelagen approach and created a matrix that was a task. for each (i, j), x [i, j] = 1, if the device i can go to position j, 0 otherwise.

Then I used addConstraint(MaxSumConstraint(maxAmount[i]), row) for each row - this is a constraint representing the maximum devices in each place.

and addConstraint(ExactSumConstraint(1), col) for each column is a limitation that each device can only be located in one place.

next, I took all x [i, j] = 0 (the device I cannot be in location j) and for each t (i, j) addConstraint(lambda var, val=0: var == val, (t,))

This problem is similar to sudoku problem and I used this example for reference

The matrix for my example above is:

 (devices:) 1 2 3 4 5 6 7 loc1: 1 0 1 0 0 0 1 loc2: 1 0 1 1 1 1 1 loc3: 0 1 0 1 1 1 0 

My code is:

  problem = Problem() rows = range(locations_amount) cols = range(devices_amount) matrix = [(row, col) for row in rows for col in cols] problem.addVariables(matrix, range(0, 2)) #each cell can get 0 or 1 rowSet = [zip([el] * len(cols), cols) for el in rows] colSet = [zip(rows, [el] * len(rows)) for el in cols] rowsConstrains = getRowConstrains() # list that has the maximum amount in each location(3,4,2) #from my example: loc1:3, loc2:4, loc3:2 for i,row in enumerate(rowSet): problem.addConstraint(MaxSumConstraint(rowsConstrains[i]), row) for col in colSet: problem.addConstraint(ExactSumConstraint(1), col) s = getLocationsSet() # set that has all the tuples that x[i,j] = 1 for i, loc in enumerate(locations_list): for j, iot in enumerate(devices_list): t=(i,j) if t in s: continue problem.addConstraint(lambda var, val=0: var == val, (t,)) # the value in these cells must be 0 solver = problem.getSolution() 

example for solution:

 (devices:) 1 2 3 4 5 6 7 loc1: 1 0 1 0 0 0 1 loc2: 0 0 0 1 1 1 0 loc3: 0 1 0 0 0 0 0 

Answer 2

This is a simple model similar to assignment:

So, we have a binary variable indicating whether device d is assigned to L. Linear restrictions are valid:

• assign each device in one place
• each place has a maximum number of devices
• be sure to use only allowed assignments (modeled above allowed(L,d) )

This problem can be solved by any constraint resolver.

Enumerating all the possible solutions is a bit dangerous. For large instances too much. Even for this small problem, we already have 25 solutions:

For large tasks, this number will be astronomically large.

Using the Python constraint package, it might look like this:

 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 

For big problems, you can use dicts to speed things up.