Gurobi reports negative reduced costs in optimal solution
回答済みI am trying to solve a graph partitioning problem using column generation. Unfortunately with my current implementation I observe the following:
- master problem provides negative reduced costs for some constraints (which I cannot explain and do not expect)
- after some iterations my pricing problem suggests columns that are already known to the master problem
Can you provide a hint as to what is going wrong here?
Note: I am aware that Gurobi might report negative reduced costs in some cases as discussed here - so I have dropped the upper bound on the lambda variables in my relaxed master problem accordingly.
Model outline
Given a graph G with nodes V, edges E and associated weights for each edge we want to find a partition of the nodes V such that the sum of all edge weights that cross the partition-"boundaries" is minimized. Informal speaking: Cut the graph in small pieces by removing edges, and avoid removing edges with high edge weights.
Using the following notation we formalize the problem as follows:
Master problem - initialization
# initialize with existing patterns (these are guaranteed to provide a covering of all nodes)
self.var_pattern = model.addVars(
pattern_indices,
obj=costs,
vtype=GRB.CONTINUOUS,
name="lambda")
# covering constraint
self.constr_covering = model.addConstrs(
(gp.quicksum(self.var_pattern[p]
for p in pattern_indices if i in patterns[p])
== 1
for i in self.nodes),
name="covering_constraint")
# objective function
model.modelSense = GRB.MINIMIZE
Pricing problem
self.var_x = self.m.addVars(
self.nodes,
obj=[-self.pi[i] for i in self.nodes],
vtype=GRB.BINARY,
name="x")
self.var_c = self.m.addVars(
self.edges,
obj=[0.5]*len(self.edges),
vtype=GRB.CONTINUOUS,
name="c")
self.constr_limit_pattern_size = self.m.addConstr(
gp.quicksum(self.var_x[i] for i in self.nodes) <= self.cluster_size_max,
name="limit_pattern_size")
self.constr_avoid_trivial_pattern = self.m.addConstr(
gp.quicksum(self.var_x[i] for i in self.nodes) >= 1,
name="avoid_trivial_pattern")
self.constr_edge_cutting_costs_1 = self.m.addConstrs(
((self.var_x[i] - self.var_x[j]) * self.edge_weights(i,j) <= self.var_c[(i,j)]
for i,j in self.edges)
)
self.constr_edge_cutting_costs_2 = self.m.addConstrs(
((self.var_x[j] - self.var_x[i]) * self.edge_weights(i,j) <= self.var_c[(i,j)]
for i,j in self.edges)
)
# objective function
self.m.modelSense = GRB.MINIMIZE
Master problem udpate
range_new_patterns = range(n_current_patterns, n_current_patterns + len(add_patterns))
# add variables to gurobi model and python tupledict
self.var_pattern.update(model.addVars(
range_new_patterns,
obj=add_costs,
vtype=GRB.CONTINUOUS,
name="lambda"))
model.update()
# adjust existing constraints
for p in range_new_patterns:
pattern = self.patterns[p]
model.getCol(self.var_pattern[p]).addTerms(
[1.0]*len(pattern), # coefficient in constraint is 1 for each node in pattern p
[self.constr_covering[i] for i in pattern]) # only need to update those constraints corresponding to active nodes in pattern p
-
-
Gurobi Staff
Hi Julian,
This is sometimes the case with column generation and degeneracy.
Have you tried changing the covering constraint to \(\geq\) (as you are minimising and there is nothing else in the master problem this should be OK, but feel free to change it back later to solve the final MIP).
Cheers,
David0 -
-
Hi David,
thank you for your quick reply! I have followed your advice and relaxed the covering constraint as shown below. This indeed helped me retain positive reduced costs, thus solving my first issue (1.). Unfortunately my second issue (2.) was not solved by this. I can see that after adding new columns with negative reduced costs generated by the pricing problem to the master problem the following happens:
- the dual values provided by the master problem stay constant
- thus the MIP formulation of the pricing problem (see above) suggests the same columns to add to the master problem
Now I am wondering whether the updating routine for the master problem (see above) might be insufficient - e.g., does not alter the model as expected?
Relaxed covering constraint
# covering constraint
self.constr_covering = model.addConstrs(
(gp.quicksum(self.var_pattern[p]
for p in pattern_indices if i in patterns[p])
>= 1
for i in self.nodes),
name="covering_constraint")0 -
-
-
Hi Julian,
- thus the MIP formulation of the pricing problem (see above) suggests the same columns to add to the master problem
Indeed, this is a sign that something is not quite working as expected.
To debug this you can write the model to a file via \(\texttt{model.write(f"master{iter}.lp")}\) (using model.write()).
In this case, I think the code# adjust existing constraints
for p in range_new_patterns:
pattern = self.patterns[p]
model.getCol(self.var_pattern[p]).addTerms(
[1.0]*len(pattern), # coefficient in constraint is 1 for each node in pattern p
[self.constr_covering[i] for i in pattern]) # only need to update those constraints corresponding to active nodes in pattern pDoes not do what you expect as the changes in the column will not persist in the original column (similarly when you do the same for rows).
You can add them as follows:for p in range_new_patterns:
pattern = self.patterns[p]
col = gp.Column([1.0] * len(pattern), [self.constr_covering[i] for i in pattern])
v = model.addVar(
obj=add_costs, vtype=GRB.CONTINUOUS, name=f"lambda{p}", column=col
)
Then update \(\texttt{self.var_pattern}\), please note that it is a tupledict.
Do you want me to open an internal ticket to discuss this further?
Cheers,
David0 -
-
Hi David,
thanks again for the quick reply! I adjusted my pattern update code as you suggested and now everything works as expected. At this point I do not need to discuss further - thank you for the support :)
Best regards,
Julian0 -
サインインしてコメントを残してください。
コメント
4件のコメント