Modelling non-continuous piecewise linear functions

[Galois]

I have an optimization problem where the objective (and some of the constraints) contain piecewise linear functions. The problem is relatively large and my attempts at solving it with pyomo and SCIP have not been very successful in terms on runtime. So I wanted to give it a shot using Julia after I learned about PiecewiseLinearOpt.jl

I am new to Julia and JuMP so maybe I have misunderstood things, but can I model a non-continuous piecewise linear function in PiecewiseLinearOpt.jl? If my understanding is correct, I need to pass in the breakpoints and the corresponding values. But with a non-coninuous function I don’t see how this can be done.

For example, consider the following function:

So at 2 and 4, the function is not continuous. And I was interested in trying PiecewiseLinearOpt.jl because it offers different formulations. I have modelled this using binary variables and big-M but the runtime is just horrendous (my problem involves summing millions of non continuous piecewise functions).

[odow]

I don’t think PiecewiseLinearOpt supports discontinuities. You likely do need to use a binary formulation that selects the piece.

my problem involves summing millions of non continuous piecewise functions

This just sounds like a very difficult problem to solve. What is the application? Why are you modeling it like this?

[Galois]

Ah, unfortunate but thanks for help!

The problem I am trying to solve is essentially a profit maximisation problem with churn. So i have a set of customers that have a probability of churning (depending on what price I offer them, call it x_n). So something like this:

\sum_{n}(1-prob_{n})(1+x_n)

Where prob_{n} =

\begin{cases} 0.25, & x_n \geq 2 \\ 0, & 0 < x_n < 2 \\ 0.05, & x \leq 0 \\ \end{cases}

Where prob_n is the probability of churning and instead of just (1+x_n) I have x_n with some additional parameters indexed by n. But basically I want to maximise expected profits.

The above is obviously not an interesting problem. In the real problem, I have additional constraints that turns this into a knapsack problem of sorts. But since the set of customers is very large, it is taking very long to solve.

[odow]

Is your churn probability really discontinuous like this? You can probably find a different functional form that leads to a nicer problem to solve.

But otherwise, yes, your binary formulation is likely pretty reasonable, and I would expect this to be very difficult to solve.

[Galois]

Given the industry I am trying to apply this for, this is surprisingly how we expect churn to look. I was thinking about removing the x_n \leq 0 segment, and turning the remaining segments into a ReLU shaped function and see if that helps. In the worst case scenario I will simply have to group customers together reduce the size of the problem.