Problem Rack Configuration
The rack configuration problem consists of plugging a set of electronic cards into racks with electronic connectors. Each card plugged into a rack uses a connector. In order to plug a card into a rack, the rack must be of a rack model. Each card is characterized by the power it requires. Each rack model is characterized by the maximal power it can supply, its size (number of connectors), and its price. The problem is to decide how many of the available racks are actually needed such that:
- every card is plugged into one rack
- the total power demand and the number of connectors required by the cards does not exceed that available for a rack
- the total price is minimized.
See CSPLib (Problem 31) for more information.
A Rack. Image from freesvg.org 
To build a COP (Constraint Optimization Problem) model, we need first to import the library PyCSP$^3$:
from pycsp3 import *
Then, we need some data. Here, we have 10 racks, 2 rack models (the number of connectors and the price is specified in that order for each of them), and 4 card types (the power and the demand is specified for each of them).
nRacks = 8
models = [[150, 8, 150], [200, 16, 210]] # rack models
types = [[20, 16], [40, 7], [50, 4], [75, 2]] # card types
From data, we build first some auxiliary lists that will be useful for writing our model. Note that we add a dummy model to deal with possibly unused racks.
models.append([0, 0, 0]) # we add first a dummy model (0,0,0)
powers, sizes, costs = zip(*models)
cardPowers, cardDemands = zip(*types)
nModels, nTypes = len(models), len(types)
We can check that everything is fine:
print("powers: ", powers)
print("sizes: ", sizes)
print("costs: ", costs)
print("cardPowers: ", cardPowers)
print("cardDemands: ", cardDemands)
powers: (150, 200, 0)
sizes: (8, 16, 0)
costs: (150, 210, 0)
cardPowers: (20, 40, 50, 75)
cardDemands: (16, 7, 4, 2)
We start our COP model by introducing an array $m$ of variables (one per rack). This will allow us to represent any configuration.
# m[i] is the model used for the ith rack
m = VarArray(size=nRacks, dom=range(nModels))
We can display the structure of the array, as well as the domain of the first variable (note that all variables have the same domain).
print("Array m: ", m)
print("Domain of any variable: ", m[0].dom)
Array m: [m[0], m[1], m[2], m[3], m[4], m[5], m[6], m[7]]
Domain of any variable: 0..2
When we choose a model for a rack, we need to be able to reason with its power, size and cost. The simplest way of doing this is to introduce three arrays of variables and to post some table constraints in order to establish a link between related variables.
# p[i] is the power of the model used for the ith rack
p = VarArray(size=nRacks, dom=powers)
# s[i] is the size (number of connectors) of the model used for the ith rack
s = VarArray(size=nRacks, dom=sizes)
# c[i] is the cost (price) of the model used for the ith rack
c = VarArray(size=nRacks, dom=costs)
The table we need is quite natural:
T = [(i, powers[i], sizes[i], costs[i]) for i in range(nModels)]
We can display it:
print(T)
[(0, 150, 8, 150), (1, 200, 16, 210), (2, 0, 0, 0)]
We can now post a group of constraints Extension:
satisfy(
# linking rack models with powers, sizes and costs
(m[i], p[i], s[i], c[i]) in T for i in range(nRacks)
);
We can display the internal representation of the posted constraints; this way, although a little bit technical, we can control that everything is fine.
print(posted())
extension(list:[m[0], p[0], s[0], c[0]], supports:(0,150,8,150)(1,200,16,210)(2,0,0,0))
extension(list:[m[1], p[1], s[1], c[1]], supports:(0,150,8,150)(1,200,16,210)(2,0,0,0))
extension(list:[m[2], p[2], s[2], c[2]], supports:(0,150,8,150)(1,200,16,210)(2,0,0,0))
extension(list:[m[3], p[3], s[3], c[3]], supports:(0,150,8,150)(1,200,16,210)(2,0,0,0))
extension(list:[m[4], p[4], s[4], c[4]], supports:(0,150,8,150)(1,200,16,210)(2,0,0,0))
extension(list:[m[5], p[5], s[5], c[5]], supports:(0,150,8,150)(1,200,16,210)(2,0,0,0))
extension(list:[m[6], p[6], s[6], c[6]], supports:(0,150,8,150)(1,200,16,210)(2,0,0,0))
extension(list:[m[7], p[7], s[7], c[7]], supports:(0,150,8,150)(1,200,16,210)(2,0,0,0))
At this stage, it is not very interesting to try solving the problem instance because one important thing is missing: controling the number of card (types) that can be connected to a rack. This is why we introduce the following array of variables:
# nc[i][j] is the number of cards of type j put in the ith rack
nc = VarArray(size=[nRacks, nTypes], dom=lambda i, j: range(min(max(sizes), cardDemands[j]) + 1))
We can control this new array, and in particular, the domains that are defined by a (lambda) function.
print("Array nc: ", nc)
print("Domain of variables in the first row of nc: ", [nc[0][j].dom for j in range(nTypes)])
Array nc: [
[nc[0][0], nc[0][1], nc[0][2], nc[0][3]]
[nc[1][0], nc[1][1], nc[1][2], nc[1][3]]
[nc[2][0], nc[2][1], nc[2][2], nc[2][3]]
[nc[3][0], nc[3][1], nc[3][2], nc[3][3]]
[nc[4][0], nc[4][1], nc[4][2], nc[4][3]]
[nc[5][0], nc[5][1], nc[5][2], nc[5][3]]
[nc[6][0], nc[6][1], nc[6][2], nc[6][3]]
[nc[7][0], nc[7][1], nc[7][2], nc[7][3]]
]
Domain of variables in the first row of nc: [0..16, 0..7, 0..4, 0..2]
We control the capacity of the racks with a group of constraints Sum:
satisfy(
# connector-capacity constraints
Sum(nc[i]) <= s[i] for i in range(nRacks)
);
We also guarantee that the demands are satisfied:
satisfy(
# demand constraints
Sum(nc[:, j]) == cardDemands[j] for j in range(nTypes)
);
Interestingly, by calling the function solve(), we can check that the problem is satisfiable (SAT). We can also display the found solution. Here, we call the function values() that collects the values assigned to a specified list of variables.
if solve() is SAT:
print("Models of racks: ", values(m))
print("Number of cards per rack and type:", values(nc))
Models of racks: [0, 0, 2, 2, 1, 2, 2, 2]
Number of cards per rack and type: [
[0, 7, 0, 0]
[6, 0, 0, 2]
[0, 0, 0, 0]
[0, 0, 0, 0]
[10, 0, 4, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
]
One can see that the number of cards per rack sometimes largely exceeds the power capacity and/or the number of connectors. We can post two groups of constraints; the former involving constraints Sum and the latter involving constraints Intension based on a dot product.
satisfy(
# connector-capacity constraints
[Sum(nc[i]) <= s[i] for i in range(nRacks)],
# power-capacity constraints
[nc[i] * cardPowers <= p[i] for i in range(nRacks)]
);
We can display them (note that ‘le’ stands for ‘less than or equal to’).
print(posted(-1))
sum(list:[nc[0][0], nc[0][1], nc[0][2], nc[0][3]], condition:(le,s[0]))
sum(list:[nc[1][0], nc[1][1], nc[1][2], nc[1][3]], condition:(le,s[1]))
sum(list:[nc[2][0], nc[2][1], nc[2][2], nc[2][3]], condition:(le,s[2]))
sum(list:[nc[3][0], nc[3][1], nc[3][2], nc[3][3]], condition:(le,s[3]))
sum(list:[nc[4][0], nc[4][1], nc[4][2], nc[4][3]], condition:(le,s[4]))
sum(list:[nc[5][0], nc[5][1], nc[5][2], nc[5][3]], condition:(le,s[5]))
sum(list:[nc[6][0], nc[6][1], nc[6][2], nc[6][3]], condition:(le,s[6]))
sum(list:[nc[7][0], nc[7][1], nc[7][2], nc[7][3]], condition:(le,s[7]))
sum(list:[nc[0][0], nc[0][1], nc[0][2], nc[0][3]], coeffs:[20, 40, 50, 75], condition:(le,p[0]))
sum(list:[nc[1][0], nc[1][1], nc[1][2], nc[1][3]], coeffs:[20, 40, 50, 75], condition:(le,p[1]))
sum(list:[nc[2][0], nc[2][1], nc[2][2], nc[2][3]], coeffs:[20, 40, 50, 75], condition:(le,p[2]))
sum(list:[nc[3][0], nc[3][1], nc[3][2], nc[3][3]], coeffs:[20, 40, 50, 75], condition:(le,p[3]))
sum(list:[nc[4][0], nc[4][1], nc[4][2], nc[4][3]], coeffs:[20, 40, 50, 75], condition:(le,p[4]))
sum(list:[nc[5][0], nc[5][1], nc[5][2], nc[5][3]], coeffs:[20, 40, 50, 75], condition:(le,p[5]))
sum(list:[nc[6][0], nc[6][1], nc[6][2], nc[6][3]], coeffs:[20, 40, 50, 75], condition:(le,p[6]))
sum(list:[nc[7][0], nc[7][1], nc[7][2], nc[7][3]], coeffs:[20, 40, 50, 75], condition:(le,p[7]))
We can run again the solver.
if solve() is SAT:
print("Models of racks: ", values(m))
print("Number of cards per rack and type:", values(nc))
print("Overall cost ", sum(c[i].value for i in range(nRacks)))
Models of racks: [2, 2, 0, 1, 1, 1, 1, 2]
Number of cards per rack and type: [
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 2]
[6, 2, 0, 0]
[0, 0, 4, 0]
[10, 0, 0, 0]
[0, 5, 0, 0]
[0, 0, 0, 0]
]
Overall cost 990
This times, we obtain a valid solution with 5 used racks (note that model 2 is the dummy model, and so, must be ignored).
To break some symmetries, one can constrain the order of models with a constraint Increasing. Note that the tag will be recorded in the generated XMl file (and so, can be identified by solvers).
satisfy(
# tag(symmetry-breaking)
Increasing(m)
);
We then obtain a solution with models given in increasing order.
if solve() is SAT:
print("Models of racks: ", values(m))
print("Number of cards per rack and type:", values(nc))
print("Overall cost ", sum(c[i].value for i in range(nRacks)))
Models of racks: [0, 0, 0, 0, 1, 1, 2, 2]
Number of cards per rack and type: [
[1, 3, 0, 0]
[0, 0, 0, 2]
[0, 3, 0, 0]
[7, 0, 0, 0]
[0, 0, 4, 0]
[8, 1, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
]
Overall cost 1020
We can see that the solution is not really optimized. Hence, we add an objective function as follows:
minimize(
# minimizing the total cost being paid for all racks
Sum(c)
);
We can run again the solver, with this optimization task. Note that we need to check that the status returned by the solver is now OPTIMUM.
if solve() is OPTIMUM:
print("Models of racks: ", values(m))
print("Number of cards per rack and type:", values(nc))
print("Overall cost: ", bound())
Models of racks: [0, 0, 0, 0, 0, 1, 2, 2]
Number of cards per rack and type: [
[3, 1, 1, 0]
[5, 0, 1, 0]
[5, 0, 1, 0]
[3, 1, 1, 0]
[0, 0, 0, 2]
[0, 5, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
]
Overall cost: 960
Finally, we give below the model in one piece. Here the data is expected to be given by the user (in a command line).
from pycsp3 import *
nRacks, models, cardTypes = data
models.append([0, 0, 0]) # we add first a dummy model (0,0,0)
powers, sizes, costs = zip(*models)
cardPowers, cardDemands = zip(*cardTypes)
nModels, nTypes = len(models), len(cardTypes)
T = {(i, powers[i], sizes[i], costs[i]) for i in range(nModels)}
# m[i] is the model used for the ith rack
m = VarArray(size=nRacks, dom=range(nModels))
# p[i] is the power of the model used for the ith rack
p = VarArray(size=nRacks, dom=powers)
# s[i] is the size (number of connectors) of the model used for the ith rack
s = VarArray(size=nRacks, dom=sizes)
# c[i] is the cost (price) of the model used for the ith rack
c = VarArray(size=nRacks, dom=costs)
# nc[i][j] is the number of cards of type j put in the ith rack
nc = VarArray(size=[nRacks, nTypes], dom=lambda i, j: range(min(max(sizes), cardDemands[j]) + 1))
satisfy(
# linking rack models with powers, sizes and costs
[(m[i], p[i], s[i], c[i]) in T for i in range(nRacks)],
# connector-capacity constraints
[Sum(nc[i]) <= s[i] for i in range(nRacks)],
# power-capacity constraints
[nc[i] * cardPowers <= p[i] for i in range(nRacks)],
# demand constraints
[Sum(nc[:, j]) == cardDemands[j] for j in range(nTypes)],
# tag(symmetry-breaking)
[
Decreasing(m),
If(m[0] == m[1], Then=nc[0][0] >= nc[1][0])
]
)
minimize(
# minimizing the total cost being paid for all racks
Sum(c)
)