python Constraints - constraining the amount

Question

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

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

Also, I have 7 devices: device1,...device7

Max amount of devices in each location: loc1:3, loc2:4, loc3:2 (for example maximum of 3 devices in loc1 and so on...)

And some constraints about the locations and the devices:

loc1: device1, device3, device7,

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

loc3: device2, device4, device5, device6

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

I'm trying to get a set of possible options for devices in locations.

    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'm stuck on how to do the constrains. I've tried:

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

but it doesn't work, MaxSumConstraint does not sum what I need.

All devices must be placed somewhere

possible solution:

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

Anyone has an idea?

(another python package/not to use any package, is also good idea if someone has any suggestions...)

Answer 1

This is simple assignment-like model:

So we have a binary variable indicating if device d is assigned to location L. The linear constraints are just:

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

This problem can be handled by any constraint solver.

Enumerating all possible solutions is a bit dangerous. For large instances there are just way too many. Even for this small problem we already have 25 solutions:

For large problems this number will be astronomically large.

Using the Python constraint package this 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

For large problems you may want to use dicts to speed things up.