Assistance with GRB.Callback.MIPNODE for Branch and Cut in Generalized Benders Decomposition
AnsweredHello,
I am currently working on using the callback function with the GRB.Callback.MIPNODE parameter to implement a Branch and Cut algorithm for a generalized Benders decomposition. However, I have encountered some challenges with making the MIPNODE callback function work effectively in my model.
Could you please review my framework and provide some advice? Any guidance or suggestions would be greatly appreciated and extremely helpful.
Thank you in advance for your time and assistance!
Best regards,
Henry
--------------------------------------------------------------------------------------------------------------------------
Here is my Python code:
def mycallback(model,where):
x_cb={}
y_cb={}
Phi_cb={}
alpha1={};beta1={};lamb1={};gamma1={};TC1={};IC1={};LC1={};PC1={};SQ2={};
itimes=1
if where == GRB.Callback.MIPNODE:
print('\n')
print("MIPNODE callback triggered!")
print('\n')
for m in model.getVars():
if m.varName.startswith('x'):
j = int(m.varName.split('_')[1])
x_cb[j] = model.cbGetNodeRel(m)
if m.varName.startswith('y'):
r = int(m.varName.split('_')[1])
y_cb[r] = model.cbGetNodeRel(m)
if m.varName.startswith('Phi'):
s = int(m.varName.split('_')[1])
Phi_cb[s] = model.cbGetNodeRel(m)
for s in S:
alpha1[itimes,s],beta1[itimes,s],lamb1[itimes,s],gamma1[itimes,s],TC1[itimes,s],IC1[itimes,s],LC1[itimes,s],PC1[itimes,s],SQ2[itimes,s]=sub2(x_cb,y_cb,s) % This function will solve the subproblem for each s dimension
print('\n')
print('cacuSQ=%s'%( sum( (P[s+1]-P[s])*(TC1[itimes,s]+IC1[itimes,s]+LC1[itimes,s]+PC1[itimes,s]) for s in S) ))
print('SQ=%s'%(sum(SQ2[itimes,s] for s in S)))
print('Phi=%s'%(sum(Phi_cb[s] for s in S)))
print('\n')
print('\n')
print('---add GBD cut---')
print('\n')
# master_model.cbLazy( gp.quicksum(Phi[s] for s in S) >= gp.quicksum((P[s+1]-P[s])*(TC1[itimes,s]+IC1[itimes,s]+LC1[itimes,s]+PC1[itimes,s]) for s in S) + gp.quicksum(alpha1[itimes,s][j,t]*(x[j]-lamb1[itimes,s][j,t]-gamma1[itimes,s][j,t]) for j in J for t in T for s in S) + gp.quicksum(beta1[itimes,s][r,t]*(y[r]-lamb1[itimes,s][r,t]) for r in R for t in T for s in S) )
master_model.cbCut( gp.quicksum(Phi[s] for s in S) >= gp.quicksum((P[s+1]-P[s])*(TC1[itimes,s]+IC1[itimes,s]+LC1[itimes,s]+PC1[itimes,s]) for s in S) + gp.quicksum(alpha1[itimes,s][j,t]*(x[j]-x_cb[j]) for j in J for t in T for s in S) + gp.quicksum(beta1[itimes,s][r,t]*(y[r]-y_cb[r]) for r in R for t in T for s in S) )
master_model.cbCut( gp.quicksum(Phi[s] for s in S) >= gp.quicksum((P[s+1]-P[s])*(TC1[itimes,s]+IC1[itimes,s]+LC1[itimes,s]+PC1[itimes,s]) for s in S) * (1-gp.quicksum(x[j] for j in J if x_cb[j]==0)))
master_model.cbCut(gp.quicksum(Phi[s] for s in S) >= gp.quicksum((P[s+1]-P[s])*(TC1[itimes,s]+IC1[itimes,s]+LC1[itimes,s]+PC1[itimes,s]) for s in S) * (1-gp.quicksum(y[r] for r in R if y_cb[r]==0)))
itimes+=1
elif where == GRB.Callback.MIPSOL:
print('\n')
print("MIPSOL callback triggered!")
print('\n')
#---------------------- MP Model-------------------------------------------------------------------------
master_model = gp.Model("Master_model")
Phi={}
x={}
y={}
alpha1={};beta1={};lamb1={};gamma1={};TC1={};IC1={};LC1={};PC1={};SQ2={};
for j in J:
x[j]=master_model.addVar(vtype= GRB.BINARY, name="x_%s" % (j))
for r in R:
y[r]=master_model.addVar(vtype= GRB.BINARY, name="y_%s" % (r))
for s in S:
Phi[s] = master_model.addVar(vtype=GRB.CONTINUOUS, name='Phi_%s'%(s))
#------------master model Objective Function----------------------------------------------------------------------
mas_obj = sum(f[j]*x[j] for j in J)+sum(f[r]*y[r] for r in R)+gp.quicksum(Phi[s] for s in S)
master_model._vars = master_model.getVars()
master_model.setObjective(mas_obj, GRB.MINIMIZE)
#model parameters
master_model.Params.LogToConsole=True#
master_model.setParam('OptimalityTol', 1e-9)
master_model.setParam('FeasibilityTol', 1e-9)
master_model.setParam('IntFeasTol', 1e-9)
master_model.setParam('LazyConstraints', 1)
start=time.time()
master_model.optimize(mycallback)
end=time.time()
And here is my Log:
Set parameter OptimalityTol to value 1e-09
Set parameter FeasibilityTol to value 1e-09
Set parameter IntFeasTol to value 1e-09
Set parameter LazyConstraints to value 1
Gurobi Optimizer version 11.0.2 build v11.0.2rc0 (win64 - Windows 11.0 (22631.2))
CPU model: 13th Gen Intel(R) Core(TM) i9-13900H, instruction set [SSE2|AVX|AVX2]
Thread count: 14 physical cores, 20 logical processors, using up to 20 threads
Optimize a model with 0 rows, 29 columns and 0 nonzeros
Model fingerprint: 0x16514092
Variable types: 15 continuous, 14 integer (14 binary)
Coefficient statistics:
Matrix range [0e+00, 0e+00]
Objective range [1e+00, 6e+03]
Bounds range [1e+00, 1e+00]
RHS range [0e+00, 0e+00]
MIPSOL callback triggered!
Found heuristic solution: objective 0.0000000
Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 1 (of 20 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
User-callback calls 24, time in user-callback 0.00 sec
-
Hi Henry,
"Benders cuts" are actually "lazy constraints" using Gurobi terminology (see What is the difference between user cuts and lazy constraints?). You will need to add them using Model.cbLazy not Model.cbCut.
I would also experiment with adding the "cuts" from a MIPSOL callback instead of MIPNODE and see if it improves performance.
- Riley
0
Please sign in to leave a comment.
Comments
1 comment