GitHub

PiecewiseLinearOpt.jl

Build Status codecov

PiecewiseLinearOpt.jl is a JuMP extension for modeling optimization problems containing piecewise linear functions.

This package is an accompaniment to a paper entitled Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools, by Joey Huchette and Juan Pablo Vielma.

Getting help

If you need help, please ask a question on the JuMP community forum.

If you have a reproducible example of a bug, please open a GitHub issue.

License

PiecewiseLinearOpt.jl is licensed under the MIT license.

Installation

Install PiecewiseLinearOpt using Pkg.add:

import PkgPkg.add("PiecewiseLinearOpt")

Use with JuMP

Current support is limited to modeling the graph of a continuous piecewise linear function, either univariate or bivariate, with the goal of adding support for the epigraphs of lower semicontinuous piecewise linear functions.

Univariate

Consider a piecewise linear function f. The function is described a domain d, which is a set of breakpoints between pieces, and the function value fd at those breakpoints:

julia> f(x) = sin(x)f (generic function with 1 method)julia> d = 0:0.5:2pi0.0:0.5:6.0julia> fd = f.(d)13-element Vector{Float64}:  0.0  0.479425538604203  0.8414709848078965  0.9974949866040544  0.9092974268256817  0.5984721441039564  0.1411200080598672 -0.35078322768961984 -0.7568024953079282 -0.977530117665097 -0.9589242746631385 -0.7055403255703919 -0.27941549819892586

To represent this function in a JuMP model, do:

using JuMP, PiecewiseLinearOptmodel = Model()@variable(model, x)z = PiecewiseLinearOpt.piecewiselinear(model, x, d, fd; method = :CC)@objective(model, Min, z) # minimize f(x)

Bivariate

Consider piecewise linear approximation for the function $f(x, y) = exp(x + y)$:

using JuMP, PiecewiseLinearOptmodel = Model()@variable(model, x)@variable(model, y)z = PiecewiseLinearOpt.piecewiselinear(    model,    x,    y,    0:0.1:1,    0:0.1:1,    (u, v) -> exp(u + v);    method = :DisaggLogarithmic,)@objective(model, Min, z)

Methods

Supported univariate formulations:

  • Convex combination (:CC)
  • Multiple choice (:MC)
  • Native SOS2 branching (:SOS2)
  • Incremental (:Incremental)
  • Logarithmic (:Logarithmic; default)
  • Disaggregated Logarithmic (:DisaggLogarithmic)
  • Binary zig-zag (:ZigZag)
  • General integer zig-zag (:ZigZagInteger)

Supported bivariate formulations for entire constraint:

  • Convex combination (:CC)
  • Multiple choice (:MC)
  • Disaggregated Logarithmic (:DisaggLogarithmic)

Also, you can use any univariate formulation for bivariate functions as well. They will be used to impose two axis-aligned SOS2 constraints, along with the "6-stencil" formulation for the triangle selection portion of the constraint. See the associated paper for more details. In particular, the following are also acceptable bivariate formulation choices:

  • Native SOS2 branching (:SOS2)
  • Incremental (:Incremental)
  • Logarithmic (:Logarithmic)
  • Binary zig-zag (:ZigZag)
  • General integer zig-zag (:ZigZagInteger)