In column generation, including negative reduced cost columns does not improve the LP.
Answered
Hi,
I am using column generation to compute LP bound for the graph coloring problem.
The dual solution to the current restricted master problem (RMP) is used to generate columns with negative reduced costs. to improve its objective value.
For some graphs for some iterations of CG, including a column with the negative reduced cost does not improve RMP, and the RMP is not degenerate.
Can you please suggest possible reasons?
Thanks,
Yunzhuang
-
Hi Yunzhuang,
This is expected behaviour in column generation.
In your case, it may happen that using the colourings already produced, all the vertices are covered and the entering column (even though it has a negative reduced cost), will not enter the basis in the current iteration.
It may become basic in combination with other future columns or not at all.
This results in the objective remaining the same for several iterations and then jumping.
This is expected, and as long as you have formulated the master (in your case: set covering) and pricing (maximum-weight independent set, MWIS), and you terminate when a column has a non-negative reduced cost you should be alright (in the case of the MWIS, the weight is > 1).
Cheers,
David0 -
Hi David,
Thanks for your quick explanation.
I cannot understand "it may happen that using the colorings already produced, all the vertices are covered and the entering column (even though it has a negative reduced cost), will not enter the basis in the current iteration.".
Existing columns covering all vertices make a feasible restricted master and produce some dual solution, but why is this preventing a new negative-reduced-cost column from entering the basis and making improvements?
Thanks, Yunzhuang
0 -
Hi Yunzhuang,
This happens because the duals for some of the nodes are non-zero. This is just because the gap between the primal and dual has not been closed. Having a column not entering the basis happens regularly as it may not be beneficial.
I've attached a rough implementation of Mehrotra and Trick (1996). This very small trivial example exhibits this behaviour.
Iter 0 obj=7000.0
duals={4: 1000.0, 5: 1000.0, 6: 1000.0, 7: 1000.0, 1: 1000.0, 2: 1000.0, 3: 1000.0}
coloring=[6, 1, 2, 3]
Iter 1 obj=3001.0
duals={4: 1000.0, 5: 1000.0, 6: 1.0, 7: 1000.0, 1: 0.0, 2: 0.0, 3: 0.0}
coloring=[4, 5, 7]
Iter 2 obj=2.0
duals={4: 1.0, 5: 0.0, 6: 1.0, 7: 0.0, 1: 0.0, 2: 0.0, 3: 0.0}
coloring=[4, 6]
Iter 3 obj=2.0
duals={4: 1.0, 5: 0.0, 6: 0.0, 7: 0.0, 1: 1.0, 2: 0.0, 3: 0.0}
Solution found with 2 colors
color: 0 nodes: [6, 1, 2, 3]
color: 1 nodes: [4, 5, 7]At iteration 1, even though node 6 is already in the restricted master, the dual remains non-zero until the very last iteration.
At iteration 2, the same thing happens with node 4 which is now also in the restricted master.
At iteration 3, either node 4 or node 1 could be in the coloring but this meets the termination criteria.Clearly, we already have the optimal coloring at iteration 2, so any column produced after that will not enter the basis even though it has a non-negative reduced cost (>1 in this case) and is present in the restricted master.
Cheers,
David---
Mehrotra, A., & Trick, M. A. (1996). A column generation approach for graph coloring. informs Journal on Computing, 8(4), 344-354.
---
import re
import networkx as nx
from gurobipy import *
# import matplotlib.pyplot as plt
PENALTY = 1000
def solve(G):
master, constrs = init_master(G)
itr = 0
wisd = {}
while True:
master.optimize()
print(f"Iter {itr} obj={master.objVal}")
duals = {k: v.Pi for k, v in constrs.items()}
print(f"\t{duals=}")
cost, wis = sub(duals, G, itr)
if cost > 1:
master = update_master(master, constrs, wis, itr)
wisd[itr] = wis
print(f"\tcoloring={wis}")
else:
break
itr += 1
varss = master.getVars()
colors = [get_int(v.VarName) for v in varss if v.X > 0]
print(f"Solution found with {len(colors)} colors")
for c in colors:
print(f"color: {c} nodes: {wisd[c]}")
def init_master(G):
m = Model("Master problem (set covering)")
m.params.outputflag = 0
x = m.addVars(G.nodes(), lb=0.0, ub=GRB.INFINITY, name="x_dummy", obj=PENALTY)
constrs = m.addConstrs((x[n] >= 1 for n in G.nodes()), "V")
return m, constrs
def get_int(string: str):
return int(re.search(r"\d+", string).group())
def update_master(master, constrs, wis, itr):
c = [v for k, v in constrs.items() if k in wis]
master.addVar(obj=1.0, column=Column([1.0] * len(wis), c), name=f"x_{itr}")
return master
def sub(duals, G, itr):
m = Model(f"Subproblem {itr} (weighted independent set)")
m.params.outputflag = 0
z = m.addVars(G.nodes(), name="z", vtype=GRB.BINARY)
m.addConstrs((z[i] + z[j] <= 1 for (i, j) in G.edges()))
m.setObjective(sum(v * z[k] for k, v in duals.items()), GRB.MAXIMIZE)
m.optimize()
m.write(f"sub_{itr}.lp")
return m.objVal, [v for v in G.nodes() if z[v].X > 0]
if __name__ == "__main__":
G = nx.Graph()
G.add_nodes_from([4, 5, 6, 7])
G.add_edge(1, 4)
G.add_edge(1, 5)
G.add_edge(2, 4)
G.add_edge(3, 5)
G.add_edge(5, 6)
G.add_edge(7, 3)
G.add_edge(7, 6)
# nx.draw_networkx(G, with_labels=True)
# plt.show()
solve(G)0
Please sign in to leave a comment.
Comments
3 comments