Benders optimality cut for a LP subproblem with piecewise linear objective

Ongoing

Yue Xiao

• December 09, 2021 08:42

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

0

• 

  Yue Xiao

  • December 10, 2021 13:20
  • Edited

  

  

  

  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

Please sign in to leave a comment.