Using CPLEX Piecewise Linear function

Specific Domains Optimization (Mathematical)
,
1

I’m trying to solve a MILP with an piecewise linear function in the cost function. At the moment, i’m using a binairy variable per linear piece wich is not the state of the art (see for example http://www.mit.edu/~jvielma/publications/A-Note-on-a-Superior.pdf)

CPLEX has a dediacted function to create the constraints to ensure the structure of a piecewise linear function. (see IBM Documentation)
This performs way better than my implementation (getting great cuts and reducing number of variables etc). The problem is, I’ve only used this function in python and I wasn’t able to make it work through JuMP.

Is it even possible to make it work with JuMP?

btw i’m aware of the package PiecewiseLinearOpt.jl but it doesn’t do the trick for me as I’m looking at non-continous piecewise linear function.

Also, I transitioned to modeling using julia only recently, so it might as well be something simple I didn’t understand.

Explanations would be greatly appreciated :slight_smile:

2

There is no easy to use syntax in JuMP for adding piecewise linear function in a solver-independent way but we designed the solver interface to be easily extensible precisely for this kind of use cases.
To extend JuMP to a new objective function, just do

struct PiecewiseLinear <: MOI.AbstractScalarFunction
    variable::MOI.VariableIndex
    breakpoints::Vector{Int}
    slopes::Vector{Float64}
    x0::Float64
    y0::Float64
end

to use it in JuMP as in the CPLEX example, do

model = direct_model(CPLEX.Optimizer)
@variable(model, x)
set_objective_sense(model, MOI.MIN_SENSE)
obj = PiecewiseLinear(index(x), [4.0, 5.0, 7.0], [-0.5, 1.0, -1.0, 2.0], 4.0, 2.0)
set_objective_function(model, obj)

Now you need to implement MOI.set(::CPLEX.Optimizer, ::MOI.ObjectiveFunction{PiecewiseLinear}, ::PiecewiseLinear) to pass it to CPLEX.

2 Likes
3

Thanks a lot for your help!

I’ve been trying to implement MOI.set(::CPLEX.Optimizer, ::MOI.ObjectiveFunction{PiecewiseLinear}, ::PiecewiseLinear) but I don’t really know how… i’ve read through the entirety of the MOI documentation and i’m still unsure how to “talk to CPLEX”. Also, in my use case, the piecewise linear function is not the only term in my objective. Is their a predefined addition between objective function, or do I have to implement it as a constraint on a dummy variable?
As I said, i’m very new to this.

thanks again for your help

4

I don’t really know how… i’ve read through the entirety of the MOI documentation and i’m still unsure how to “talk to CPLEX”

That’s really specific to solver interfaces, you can check https://github.com/JuliaOpt/CPLEX.jl/blob/master/src/ for examples.

Also, in my use case, the piecewise linear function is not the only term in my objective

What are the other terms ? The sum of a affine function and a piecewise linear one can be written as a piecewise linear one, can’t it ? It’s best to mirror the CPLEX interface so if CPLEX allows setting the objective as a sum of a linear function and a piecewise linear one then it makes sense to add a field in PiecewiseLinear to add linear terms.

5

That’s really specific to solver interfaces, you can check https://github.com/JuliaOpt/CPLEX.jl/blob/master/src/ for examples.

I’ll read it carefully.

What are the other terms ? The sum of a affine function and a piecewise linear one can be written as a piecewise linear one, can’t it ?

The other terms depend on other variables including somme binairy variables and integer variables (such as activation cost in my specific problem). Also for another application, i would like to have min f(x) + g(y) where f and g are piecewise linear function depending on different varialbes and that dosen’t share breakpoints. In thoses cases, I don’t see how i could express my objective as one piecewise linear function as you mentionned

6

If the CPLEX interface supports objective that is the sum of two piecewise linear functions, there is nothing blocking you to transfer that to CPLEX from JuMP.

7

Piecewise linearization falls into two categories: one where the breakpoint is a jump discontinuity, and another where the breakpoint is C0 continuous.

The former appears simpler, while the latter is more challenging to implement, as it requires not only optimizing the breakpoint location but also the function value at the breakpoint.

For the former, we have LinearSegmentation.jl; for the latter, we have EllZeroTrendFiltering.jl. However, EllZeroTrendFiltering.jl also suffers from significant performance issues and lacks support for weighted segmentation.

8

a jump discontinuity is harder?

By the way, is this type of modeling adoptable in a real-world problem?

9

In the case of jump discontinuity, the optimal line for each segment is the least-squares line for that interval. However, this is not the case for each segment of a continuous piecewise linear function. Instead, it is a linear interpolation uniquely determined by the values of its left and right endpoints, which are coupled together.

I believe it can be used. You can output the errors for the PWL method and the nonlinear method to make the results more convincing.