# Special Case of Minimum Cost Flow Problem with Variable Cost

I am working on an optimization problem similar to MCF with variable cost, but with an adjustment in the objective function. The cost function $$f$$ to minimize that is continuous, piece-wise linear and strictly increasing with given lower and upper bounds (think of $$x^3$$ defined on a closet interval). However, $$f$$ is concave below $$0$$ and convex above $$0$$ (this means that the cost can take negative values as well, acting as reward or profit).

Had $$f$$ been convex everywhere, I could transform this problem to an equivalent LP one and solve it by using the linear segments of the PWL as inequality constraints.

I would like to do the same in my case but I am struggling to figure out the correct way. (The alternative is to model it as a MIP problem which I do not want to).

• The problem is nonconvex, so any linearization will require integer variables. Commented Jul 13 at 12:35
• @RobPratt Would it make sense to introduce a binary variable to split the constraint for $x < 0$ and $x > 0$? Commented Jul 13 at 13:10
• That will not be enough because you still would have nonconvexity for the $x<0$ portion. Commented Jul 13 at 13:34
• @RobPratt So, there is no way to handle this other than using binary variables for each linear segment of the PWL cost function? Commented Jul 13 at 14:31
• Cross-posted: math.stackexchange.com/questions/4945180/… Commented Jul 13 at 15:32