Benders optimality cut for a LP subproblem with piecewise linear objective
Ongoing
Hello everyone,
I am solving a LP model using Benders decomposition. The subproblem is a LP with piecewise linear objective. I am a bit puzzled at what the objective function of the dual of the subproblem is. I have tried the standard way of expressing the objective function as a weighted sum of the dual variables multiplied by their curresponding RHS, however, this way of calculating the dual objective value does not seem to be correct when the variable with the piecewise linear objective is beyond the first linear segment.
I am aware that I can retrieve the subproblem objective value by calling
subproblem.objVal
but I need the expression of the dual objective function for Benders optimality cut. How can we find a valid Benders cut with piecewise linear subproblem?
Thanks,
Yue
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
Update: Since the piecewise linear function is convex in my case, I have solved the problem by treating the piecewise linear term as a minimax problem.
This is done by introducing an auxiliary variable M and assign constraints such that it represents the pointwise maximum w.r.t the original variable V with piecewise linear term in the objective. That is
M >= y[n] + (y[n+1] - y[n])/(x[n+1] - x[n]) * (V - x[n]) for n = 1,2,...,N-1
where x,y contain a set of N points defining the piecewise linear function segments.
Although this works, introducing these new constraints and new variables slowed down the model significantly. I wonder if there are other more efficient way to do this?
0
Post is closed for comments.
Comments
2 comments