Piecewise linear objective brainstorming

[IainNZ]

So Gurobi has solver support for piecewise linear, and we have the world expert on piecewise linearity, so, lets think about how to model it. What do we need to have to express a piecewise linear function?

• Gurobi does it on a per variable basis, i.e. a list of points in domain of x and corresponding values of the objective, so

z = 2x, x in [0,1]
   = 3x-1, x in [1,2]

would be represented as

xs = [0, 1, 2]
zs = [0, 2, 5]

An alternative reduced form is have the breakpoints, the gradient, and an offset, e.g.

xs = [0, 1, 2]
gr = [2, 3]
of = [0, -1]

I suppose.

Heres some syntax ideas

@setObjective(m, Min, {{2x, 0, 1}, {3x-1, 1, 2}})

To be continued, got to catch plane

[joehuchette]

What about

@setObjective(m, Min, {3x-1 in [0,1],
                         2x in [1,2]})

[yeesian]

I like @joehuchette's proposal. Here're some ideas (for the other form):

@setObjective(m, Min, connect{(x[i],z[i]), i in 1:n})

inclusive-or

@setObjective(m, Min, connect{(x,z), (x,z) in breakpoints1})

inclusive-or

@setObjective(m, Min, connect{(x,f(x)), x in breakpoints2})

inclusive-or

@setObjective(m, Min, connect{f(x), x in breakpoints2})

where

breakpoints1 = [(x[1],z[1]),
                (x[2],z[2]),
                ...,
                (x[n],z[n])]

and

breakpoints2 = [x[1],x[2],...,x[n]]

Some Remarks

• (where applicable) f(x[i]) == z[i]
• (optional?) x[i] < x[i+1] for all i=1:n-1

[mlubin]

What about a more general concept of a variable that is a piecewise linear function of another variable (or variables)? This is useful not just in objective functions.

[tkelman]

If this is done in a way that only works for scalar, single-variable-only functions then it would be of limited usefulness, for me anyway.

For piecewise linear, I'd need to be able to define high-dimensional polyhedral partitions, and PWA functions over those partitions. That's the full-generality version of this.

Separate issue, but I also really want ifelse for nonlinear, so I can stop manually doing smoothed sigmoidal approximations of piecewise nonlinear functions.

[IainNZ]

@tkelman you can do multivariable affine functions over boxes using this kind of format, its pretty useful at least in our field.

The kind of thing you are talking about (piecewise affine over general polyhedra) is getting into the more advanced areas of modeling that JuMP hasn't strayed into yet, e.g. disjunctive programming.

[mlubin]

@tkelman, could you open an issue on ReverseDiffSparse for support for ifelse?

[tkelman]

@mlubin sure, after I finish writing docs for julia support on Travis (spoilers).

[joehuchette]

There's no reason we can't do a nice syntax for univariate/multivariate box PWL functions using macros, as well as a more general mechanism for more complex PWL structure. The macros could just be a pleasant way of constructing a PiecewiseLinear type.

[tkelman]

The kind of thing you are talking about (piecewise affine over general polyhedra) is getting into the more advanced areas of modeling that JuMP hasn't strayed into yet, e.g. disjunctive programming.

Yeah it could make sense for the most complicated and hard-to-get-right variants to be done in a higher-level extension. Maybe we try to win over some folks at ETH Zurich and convince them to start making a port of MPT. Sorry for being so hard to please, JuMP is already awesome and continuing to get better impressively quickly.

[mlubin]

Closing this as speculative and out of scope for JuMP 1.0.

[joehuchette]

I'll take this one :)

[mlubin]

@joehuchette as a separate package, right?

[joehuchette]

Yep

On Sat, Dec 10, 2016 at 8:43 PM, Miles Lubin notifications@github.com wrote:

@joehuchette https://github.com/joehuchette as a separate package, right?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/JuliaOpt/JuMP.jl/issues/317#issuecomment-266254933, or mute the thread https://github.com/notifications/unsubscribe-auth/ABTzUkNM9WP0gcIqozDPo3bOZa131St3ks5rG1VLgaJpZM4C_O26 .

[mlubin]

So technically still out of scope :)