from mip import *
q=[[4,5,0,2],[3,2,1,0],[0,1,4,5],[3,2,0,1],[2,1,3,2],[4,3,2,1],[3,4,2,0],[5,0,3,1],[0,4,3,3],[4,0,4,1]]
s=[11,1,1,1,1,1,1,1,1,1]
r=[6,8,4,7]
a=range(0,10)
b =range(0,20)
c = range(0,4)
d =[12,9,6,6]
o = Model()
x= [[o.add_var('x({},{})'.format(i, j), var_type=BINARY) for j in b] for i in a]
y = [[o.add_var('y({},{})'.format(k, j), var_type=BINARY) for j in b] for k in c]
g = o.add_var(name='max_i', var_type=CONTINUOUS)
h = o.add_var(name='min_i', var_type=CONTINUOUS)
for i in a:
o += xsum(x[i][j] for j in b) == s[i]
for j in b:
o += xsum(x[i][j] for i in a) == 1
for k in c:
o += xsum(y[k][j] for j in b) == d[k]
for j in b:
for k in c:
o += r[k] *(xsum(y[k][jj] for jj in b if jj <= j)) >= (xsum(( xsum (q[i][k]* x[i][jj] for i in a )for jj in b if jj <=j)))
for j in b:
o += (xsum( xsum(r[k] * y[k][jj] for k in c) for jj in b if jj <= j)) - (xsum(xsum( xsum (q[i][k]* x[i][jj] for i in a) for k in c) for jj in b if jj<=j)) <= g
for j in b:
o += (xsum( xsum(r[k] * y[k][jj] for k in c) for jj in b if jj <= j)) - (xsum(xsum( xsum (q[i][k]* x[i][jj] for i in a) for k in c) for jj in b if jj<=j)) >= h
o.objective = minimize(g-h)
o.optimize()
print("Solution with {} found.".format(o.objective_value))
for x in o.vars:
print('{} : {}'.format(x.name, x.x))
"""I have tried to solve the above MILP using python mip and tried cbc, gurobi solvers, i can able to solve it for small problem , lets say when s=[20,0,0,0,0,0,0,0,0,0] and d = [14,13,0,6], and also when length of s is less than 5, but for the above inputs, it taking too much time (more than 8 hours and i can't wait).
In the above test case, I have 282 variables and 154 constraints only and I have seen that number of variables and number of constraints alone doesn't contribute to how much time, the solver takes to solve. I have 10k variables and 7k constraints in my main problem to solve for. I have tried constrained programming by limiting the values of variables by lb and ub, it didnt help. How can I solve it better? Help would be appreciated. ( g and h will be integers in all case, so I tried it by initializing as integer variables and giving close lb and ub, It also didn't help)"""