I want to generate a 20x38 binary matrix based on some constraints that I have using a dpcplex model. Some of the matrix cells are predefind as below (row,col,parameter):
[(8,3,0),(14,0,0),(14,2,0),(16,0,0),(16,1,0),(12,0,0),(10,0,0),(10,8,0),(10,9,0),(17,7,0),(17,8,0),(8,0,0),(13,8,0),(13,9,0),(1,0,1),(15,19,0)]
I need to fill out the other matrix cells with some constraints:
The problem is that my model doesn't return any solutions. I am not sure if my model is correct.
here is my code:
from docplex.mp.model import Model
cond=[[8,3,0],[1,37,0],[6,9,0]]
model = Model("MatrixComple")
R = [i for i in range(20)]
R1=[i for i in range(38)]
R2=[34,35,36,37]
R3=[i for i in range(36)]
R4=[i for i in range(34)]
R5=[i for i in range(37)]
idx = [(i, j) for i in R for j in R1 ]
x = model.binary_var_dict(idx,name= "x")
"""pre-defined cells"""
for i in R:
for j in R1:
for item in cond:
i1,i2,i3=item
model.add_constraint(x[i1, i2] == i3)
"""sum of columns must be equal to 10 """
model.add_constraints(model.sum(x[i, j] for i in R) == 10 for j in R2)
"""sum of rows must be equal to 19 """
model.add_constraints(model.sum(x[i, j] for j in R1) == 19 for i in R)
"""(apply to all rows)last 4 cells of each row must be alternative: just 1010 or 0101 is allowed"""
model.add_constraints(model.sum(x[(i, j)] for j in R2 ) == 2 for i in R )
model.add_constraints(x[(i, 34)] ==x[(i, 36)] for i in R )
"""no more that 2 consecutive 0s or 1s : 110 or 001 or 101 or 010
this rule can not be applied to pre-defined cells. For example if we have 000 or 111 in pre-defined conditions,
we need to apply this rule for the rest of matrix not the pre-defined cells
"""
model.add_constraints(model.sum(x[i, j]+x[i,j+1]+x[i,j+2] for j in R3) <=2 for i in R)
model.add_constraints(model.sum(x[i, j]+x[i,j+1]+x[i,j+2] for j in R3) >=1 for i in R)
""" (apply to all rows) sum of every 5 cells in each row must be in range [2,3] : no 11011 or 00100 is allowed """
model.add_constraints(model.sum(x[i, j]+x[i,j+1]+x[i,j+2]+x[i,j+3]+x[i,j+4]for j in R4) <=3 for i in R)
model.add_constraints(model.sum(x[i, j]+x[i,j+1]+x[i,j+2]+x[i,j+3]+x[i,j+4]for j in R4) >=2 for i in R)
""" (apply to all rows) sum of pair of consecutive 0s must be <=3 : in each row we are not allowed to have
more than 3 pair of 00 """
for i in R:
s=0
for j in R5:
if x[i, j]==x[i,j+1]==0:
s+=1
model.add_constraint(s<= 3)
""" (apply to all rows) sum of pair of consecutive 1s must be <=3 : in each row we are not allowed to have
more than 3 pair of 11 """
for i in R:
s=0
for j in R5:
if x[i, j]==x[i,j+1]==1:
s+=1
model.add_constraint(s<= 3)
solution = model.solve()
print(solution)
I found out what makes the model impossible: The constraint "no more than two consecutive 0s or 1s" was incorrect (and so is the constraint about 5 consecutive cells. You should not sum over the whole row, but pot one range per cell:
"""no more that 2 consecutive 0s or 1s : 110 or 001 or 101 or 010
this rule can not be applied to pre-defined cells. For example if we have 000 or 111 in pre-defined conditions,
we need to apply this rule for the rest of matrix not the pre-defined cells
"""
for i in R:
for j in R3:
s3ij = x[i, j]+x[i,j+1]+x[i,j+2]
model.add_range(1, s3ij, 2, f"range3_{i}_{j}")
Similarly, the constraint on five consecutive cells can be written as:
for i in R:
for j in R4:
s5ij = x[i, j]+x[i,j+1]+x[i,j+2] +x[i,j+3] +x[i,j+4]
model.add_range(2, s5ij, 3, f"range5_{i}_{j}")
With these changes, the model becomes feasible.
Hope this helps.
Philippe.