PiecewiseAffineApprox

Add convex (or concave) piecewise linear approximations of functions or a set of points to optimization models modelled in JuMP.

This package provides three main methods to fit a set of points:

1. creates and solves a MILP to fit a set of points, and adds the resulting linear constraints to the optimization model. This method is partially based on Toriello & Vielma, 2012.
2. uses a heuristic to fit the set of points. This method is based on Magnani & Boyd, 2009.
3. a progressive heuristic to add planes until a certain accuracy is met. This method is based on Kazda & Li, 2024

For non-convex functions, consider using PiecewiseLinearOpt.jl.

Usage

using JuMP, PiecewiseAffineApprox, HiGHS

m = Model(HiGHS.Optimizer)
@variable(m, x)
# Create a piecewise linear approximation to x^2 on the interval [-1, 1]
pwa = approx(x -> x[1]^2, [(-1, 1)], Convex(), MILP(optimizer = HiGHS.Optimizer, planes=5))
# Add the pwa function to the model
z = pwaffine(m, x, pwa)
# Minimize
@objective(m, Min, z)
# Check approximation/solution at x = 0.5
@constraint(m, x >= 0.5)
optimize!(m)
value(z) # 0.2653

To keep dependencies light, PiecewiseAffineApprox does not include plotting by default. If the Makie or Plots package is loaded before using the module, some simple plotting routines will be available

The following demonstrates how this can be achieved:

using PiecewiseAffineApprox, CairoMakie, HiGHS

x = LinRange(0, 1, 20)
f(x) = first(x)^2
pwa = approx(f, [(0, 1)], Convex(), MILP(optimizer = HiGHS.Optimizer, planes = 3))
p = plot(x, f.(x), pwa)

save("approx.svg", p)

Animation showing the accuracy when adding more cuts: Approximation of 3D function