Introduction

PiecewiseAffineApprox is a package designed to compute and 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
optimizer = optimizer_with_attributes(HiGHS.Optimizer, MOI.Silent()=>true)

m = Model(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, 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)
round(value(z), digits=4)

# output
0.2653

Visualization

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 the use of the plotting functions with Makie:

2D

using PiecewiseAffineApprox, CairoMakie, HiGHS, JuMP
optimizer = optimizer_with_attributes(HiGHS.Optimizer, MOI.Silent()=>true)
x = LinRange(0, 1, 20)
f(x) = first(x)^2
pwa = approx(f, [(0, 1)], Convex(), MILP(;optimizer, planes = 3))
p = plot(x, f.(x), pwa)

save("approx.svg", p)

# output
CairoMakie.Screen{SVG}

Animation showing the accuracy when adding more cuts:

3D

Approximation of 3D function

Default plot with 3D plot and error distribution for all points as well as allocation to planes for each plot (for Heuristic)

Acknowledgements

TODO: Add project references.