Get root node solution in B&C
I'm working on a B&C framework in Gurobi/Python and I would like retrieve the optimal solution of the root node problem to verify if it does not violate the added cuts . How can I do that?.
I attach an example of what I'm running. At each iteration in the root node, I'm printing the type of solution (fractional or integer) and the added cut. This way, the last solution (optimal) shouldn't be violating any cut (so should be printing 'FracSol_NoCuts'), but that does not happen in this case.
Thanks.
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
from gurobipy import *
def ins_run(n, alpha, t=0):
np.random.seed(t)
depot = n + 1
nodos = [i + 1 for i in range(depot)]
pos = dict(zip([i for i in nodos],list(map(tuple,np.random.random([n, 2]) * 5))))
pos[depot] = pos[1]
c_cam = {(i, j): np.sqrt((pos[i][0] - pos[j][0]) ** 2 + (pos[i][1] - pos[j][1]) ** 2)
for i in nodos for j in nodos if i != j}
c_drone = {e: alpha * c_cam[e] for e in c_cam} # Velocidad del drone
return pos, c_cam, c_drone
def delta_out(arcos, i):
aux = list()
for e in arcos:
if e[0] == i:
aux.append(e)
return aux
def delta_in(arcos, i):
aux = list()
for e in arcos:
if e[1] == i:
aux.append(e)
return aux
def delta_out_S(arcos, S):
aux = list()
for i in S:
for e in delta_out(arcos, i):
if e[1] not in S:
aux.append(e)
return aux
def run_DisconnectedCycle(G, nodos, capacity, peso):
# Los arcos con valor no nulo tienen capacidad 1 y se determinan todos los subciclos desconectados
G.remove_edges_from(list(G.edges))
edges = list()
for (i, j) in capacity:
if capacity[i, j] > 1e-8:
edges.append((i, j))
G.add_edges_from(edges)
st_list = list(nx.strongly_connected_components(G))
subtour_list = list()
for i in st_list:
if 1 not in i:
peso_subtour = {j: peso[j] for j in i}
subtour_list.append((i, max(peso_subtour, key=peso_subtour.get)))
return subtour_list
def run_MinCut(G, nodos, capacity, peso):
# Para todo j != depot, se hace min-cut. Sobre todos, se elige el subtour mas violado, junto al peso respectivo (gamma)
G.remove_edges_from(list(G.edges))
G.add_edges_from(capacity)
for (i, j) in capacity:
G[i][j]['capacity'] = capacity[i, j]
subtour_list = list()
subtour = None
for j in nodos:
if j != 1:
(cap, (S, S_c)) = nx.minimum_cut(G, 1, j)
if cap - peso[j] < 0:
subtour_list.append((cap - peso[j], j, S_c))
if subtour_list:
subtour = min(subtour_list, key=lambda x: x[0])
return subtour
if __name__ == '__main__':
def PCTSP_CB(m, where):
def get_sol(model):
x_sol = list()
for e in index_2:
arco_x = model.cbGetSolution([x[e]])
if arco_x[0] > 0.5:
x_sol.append(e)
return x_sol
# Nodo fraccionario
if where == GRB.Callback.MIPNODE:
depth = m.cbGet(GRB.Callback.MIPNODE_NODCNT)
# Nodo raiz
if depth == 0:
x_recurso = m.cbGetNodeRel(x)
if m.cbGet(GRB.Callback.MIPNODE_STATUS) == GRB.Status.OPTIMAL:
print('Optimal Solution')
print('Objective value: {}'.format(sum([c[e] * x_recurso[e] for e in index_2])))
print('Feasible solutions: {}'.format(m.cbGet(GRB.Callback.MIPNODE_SOLCNT)))
gamma_recurso = m.cbGetNodeRel(gamma)
solutions.append((x_recurso, gamma_recurso))
st_DisconnectedCycle = run_DisconnectedCycle(graph.G, nodos, x_recurso, gamma_recurso)
if st_DisconnectedCycle:
print('FracSol_DisconnectedCycle cut added')
print('')
for subtour in st_DisconnectedCycle:
m.cbCut(quicksum(x[e] for e in delta_out_S(index_2, subtour[0])) >= gamma[subtour[1]])
else:
# Si no hay subciclos desconectados, se agrega un Min-Cut
st_MinCut = run_MinCut(graph.G, nodos, x_recurso, gamma_recurso)
if st_MinCut:
print('FracSol_MinCut cut added')
print('')
m.cbCut(quicksum(x[e] for e in delta_out_S(index_2, st_MinCut[2])) >= gamma[st_MinCut[1]])
else:
print('FracSol_NoCuts\n')
# Nodo entero
elif where == GRB.Callback.MIPSOL:
x_recurso = {e: 0 for e in index_2}
x_sol = get_sol(m)
for e in x_sol:
x_recurso[e] = 1
gamma_recurso = {i: sum([x_recurso[e] for e in delta_out(index_2, i)]) for i in nodos}
depth = m.cbGet(GRB.Callback.MIPSOL_NODCNT)
st_DisconnectedCycle = run_DisconnectedCycle(graph.G, nodos, x_recurso, gamma_recurso)
# Nodo raiz
if depth == 0:
solutions.append((x_recurso, gamma_recurso))
print('Objective value: {}'.format(sum([c[e] * x_recurso[e] for e in index_2])))
print('Feasible solutions: {}'.format(m.cbGet(GRB.Callback.MIPSOL_SOLCNT)))
if st_DisconnectedCycle:
print('IntSol_DisconnectedCycle cut added')
print('')
for subtour in st_DisconnectedCycle:
m.cbCut(quicksum(x[e] for e in delta_out_S(index_2, subtour[0])) >= gamma[subtour[1]])
else:
print('IntSol_NoCuts\n')
# Nodo de mayor profundidad
else:
if st_DisconnectedCycle:
for subtour in st_DisconnectedCycle:
m.cbLazy(quicksum(x[e] for e in delta_out_S(index_2, subtour[0])) >= gamma[subtour[1]])
class Graph():
def __init__(self):
self.G = nx.DiGraph()
self.S_track = list()
class Cuts():
def __init__(self):
self.SEC_frac_DC = 0
self.SEC_frac_MC = 0
self.SEC_int = 0
# Data
n = 5
seed = 15
alpha = 0.5
pos, c, d = params.run(n, alpha, seed)
depot = n + 1
nodos = [i + 1 for i in range(depot)]
index_2 = [(i, j) for i in nodos for j in nodos if i != j]
graph = Graph()
cuts = Cuts()
solutions = list()
model = Model()
model.Params.OutputFlag = 0
model.Params.LazyConstraints = 1
model.Params.PreCrush = 1
x = model.addVars(index_2, vtype=GRB.BINARY, name='x')
gamma = model.addVars(nodos, vtype=GRB.BINARY, name='z')
model.addConstrs(quicksum(x[e] for e in delta_in(index_2, i)) == gamma[i] for i in nodos)
model.addConstrs(quicksum(x[e] for e in delta_out(index_2, i)) == gamma[i] for i in nodos)
model.addConstr(x[depot, 1] == 1)
model.addConstr(x[1, depot] == 0)
model.addConstr(gamma[1] == 1)
model.addConstr(gamma[depot] == 1)
model.addConstrs(x[e] <= quicksum(x[r] for r in delta_in(index_2, depot) if r[0] <= e[1]) for e in delta_out(index_2, 1))
model.addConstr(quicksum(gamma[i] for i in nodos) >= round((len(nodos) - 1) / 2 + 0.1) + 1)
obj = quicksum(x[e] * c[e] for e in index_2)
model.setObjective(obj, GRB.MINIMIZE)
model.optimize(PCTSP_CB)
-
It could just be that Gurobi aborts the root cut loop and goes into branching even though you might still be able to find violated cuts. This is an important decision for performance whether one continues with the cut separation or whether one goes into branching. Usually, you don't want to cut forever.
If you want to let the cut loop run until no more cuts can be found, you need to set the "CutPasses" parameter to a very large value.
Regards,
Tobias
0 -
Tobías,
Thank you for your answer. I tried setting CutPasses to a very large value and the problem remains.
Could something else be causing this?
0
Please sign in to leave a comment.
Comments
2 comments