Skip to content

Latest commit

 

History

History
69 lines (48 loc) · 3.12 KB

README.md

File metadata and controls

69 lines (48 loc) · 3.12 KB
Raw

PiecewiseLinearOpt

A package for modeling optimization problems containing piecewise linear functions. Current support is for (the graphs of) continuous univariate 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.

Build Status

Coverage Status

codecov.io

This package offers helper functions for the JuMP algebraic modeling language.

Consider a piecewise linear function. The function is described in terms of the breakpoints between pieces, and the function value at those breakpoints.

Consider a JuMP model

using JuMP, PiecewiseLinearOpt
m = Model()
@variable(m, x)

To model the graph of a piecewise linear function f(x), take d as some set of breakpoints along the real line, and fd = [f(x) for x in d] as the corresponding function values. You can model this function in JuMP using the following function:

z = piecewiselinear(m, x, d, fd)
@objective(m, Min, z) # minimize f(x)

For another example, think of a piecewise linear approximation for for the function $f(x,y) = exp(x+y)$:

using JuMP, PiecewiseLinearOpt
m = Model()
@variable(m, x)
@variable(m, y)

z = piecewiselinear(m, x, y, 0:0.1:1, 0:0.1:1, (u,v) -> exp(u+v))
@objective(m, Min, z)

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.

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)
  • Dissaggregated 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)