API reference

PiecewiseLinear(f::Function, x; method = nothing, direction = Graph())
PiecewiseLinear(x, z::AbstractVector; method = nothing, direction = Graph())
PiecewiseLinear(f::Function, x, y; triangulation = K1Triangulation(), method = nothing, direction = Graph())
PiecewiseLinear(x, y, z::AbstractMatrix; triangulation = K1Triangulation(), method = nothing, direction = Graph())
PiecewiseLinear(f::Vector{<:Function}, x::Vector{<:AbstractVector}; method = nothing, direction = Graph())
PiecewiseLinear(x::Vector{<:AbstractVector}, z::Vector{<:AbstractVector}; method = nothing, direction = Graph())
PiecewiseLinear(pwl::PWLFunction; method = nothing, direction = Graph())

A piecewise linear function together with the method and direction to formulate it with, which is called like a function. The univariate and bivariate forms build the function as UnivariatePWLFunction and BivariatePWLFunction do, but take the function first, so that it can be given with a do block.

A univariate function can also be given in pieces, e.g. with a discontinuity between them: piece k interpolates the function f[k], or the values z[k], at the strictly increasing breakpoints x[k]. Each piece must start where the previous piece ends, or later, which leaves a gap in the domain. Where two pieces meet with different values, the model may take either value, as a strict inequality such as x < 0 cannot be modeled, while evaluating the function gives the value of the left piece.

Keyword arguments

• method: the formulation method. If nothing, the default is Logarithmic() for continuous univariate functions, MultipleChoice() for discontinuous ones, DisaggregatedLogarithmic() for relaxations, see UnivariatePWLRelaxation, and DisaggregatedLogarithmic() for functions of three or more variables. For bivariate functions it depends on the triangulation: K1() for a K1Triangulation, UnionJack() for a UnionJackTriangulation, GreedyTriangleSelection() for any other grid triangulation and DisaggregatedLogarithmic() for unstructured segments.
• direction: whether the outputs equal (Graph()), are at least (Epigraph()) or are at most (Hypograph()) the function value.
• triangulation: how each cell of the grid of a bivariate function is split into two triangles, see GridTriangulation.

Calling

The object belongs to no model, and can be used in several. Calling it as

f(x...; name = nothing, output_var = nothing)

with an input variable, affine expression or constant for each input of the function adds the function to the model of the inputs, as add_formulation does, and returns the output, or a tuple of outputs for a function with several outputs. Each call adds a new formulation, so a function of the same inputs that is used several times should be added once, e.g. with @expression(model, fx, f(x)). If all inputs are constants and no output_var is given, the function is evaluated instead.

The name is the prefix of the names of the variables created, and output_var an existing output variable or expression of a function with one output, see add_formulation.

Example

using JuMP, PiecewiseLinearOptmodel = Model()@variable(model, x[1:2])f = PiecewiseLinear(sin, 0:0.5:2π)g = PiecewiseLinear(0:0.25:1, 0:0.25:1; method = SixStencil()) do a, b    return (a - 1)^2 + (b - 0.5)^2end@expression(model, fx, f(x[1]))@objective(model, Min, fx + g(x[1], x[2]))@constraint(model, fx ≥ -0.5)

add_formulation(
    model,
    f::PiecewiseLinear,
    x...;
    name = nothing,
    output_vars = nothing,
)

Adds the piecewise linear function f of the inputs x to model, and returns the tuple (output_vars, formulation). Calling f(x...) does the same, but returns the output only.

Arguments

• model: the JuMP model.
• f: the piecewise linear function, with the method and direction to formulate it with.
• x: an input variable, expression or constant for each input of f.

Keyword arguments

• name: the prefix of the names of the variables created. If nothing, a name of the form pwl1, pwl2, ... is used.
• output_vars: a vector or tuple with an output variable or expression for each output of f. If nothing, new variables are created, bounded by the smallest and largest function value (only from below for Epigraph() and only from above for Hypograph()).

If the function cannot be formulated, an error is thrown and the model is left unchanged.

Returns

• output_vars::Vector: the outputs of the function.
• formulation::PWLFormulation: the variables and constraints that were added.

Example

using JuMP, PiecewiseLinearOptmodel = Model()@variable(model, x)f = PiecewiseLinear(xi -> xi^2, 0:0.1:1)(y,), formulation = add_formulation(model, f, x; name = "square")

PWLFormulation

The variables and constraints that add_formulation added to a model to formulate a piecewise linear function.

Fields

• model: the model
• name: the prefix of the names of the variables
• method: the formulation method
• variables: the variables added, including the output variables unless they were given by the user
• constraints: the constraints added, excluding bounds and integrality restrictions of the variables

Use JuMP.delete(model, formulation) to remove the function from the model.

Direction

The abstract type of the direction keyword of PiecewiseLinear, which gives how the outputs y relate to the function value f(x): Graph (the default), Epigraph or Hypograph.

Graph()

The direction where the outputs equal the function value, y == f(x). This is the default.

Epigraph()

The direction where the outputs are at least the function value, y >= f(x), which suffices when the function is minimized. The new output variables are then only bounded from below.

Hypograph()

The direction where the outputs are at most the function value, y <= f(x), which suffices when the function is maximized. The new output variables are then only bounded from above.

PWLFunction(segments::Vector{SegmentPointRep{D,F}}, structure::SegmentStructure{D})

A piecewise linear function from R^D to R^F, given by its segments. The structure describes how the segments are arranged, e.g. Intervals() for a univariate function, a GridTriangulation for a bivariate function on a grid, or Unstructured{D}().

See also UnivariatePWLFunction and BivariatePWLFunction for constructing functions from breakpoints and function values, and UnivariatePWLRelaxation for a relaxation, whose segments have several values at a point.

UnivariatePWLFunction(x, f::Function)
UnivariatePWLFunction(x, z::AbstractVector)

The piecewise linear function with the strictly increasing breakpoints x, which interpolates f(x[i]), or z[i], at the breakpoints.

BivariatePWLFunction(x, y, f::Function; triangulation = K1Triangulation())
BivariatePWLFunction(x, y, z::AbstractMatrix; triangulation = K1Triangulation())

The piecewise linear function on the grid with breakpoints x and y, which interpolates f(x[i], y[j]), or z[i, j], at the grid points. Each cell of the grid is split into two triangles as given by triangulation, see GridTriangulation.

UnivariatePWLRelaxation(x, lower, upper)

A piecewise linear relaxation of a univariate function, i.e. the band between a lower and an upper piecewise linear bound. The band consists of the points (x, y) with l(x) ≤ y ≤ u(x), where l and u are the piecewise linear functions with the strictly increasing breakpoints x that interpolate lower[i] and upper[i], or lower(x[i]) and upper(x[i]) when the bounds are given as functions, at the breakpoints. For example, a function that is within ε of its interpolant has the relaxation UnivariatePWLRelaxation(x, t -> f(t) - ε, t -> f(t) + ε).

Each segment of the relaxation is the convex hull of the four points of the bounds at the ends of an interval, so the relaxation has several values at a point and cannot be evaluated. It is formulated by IndependentBranching and DisaggregatedLogarithmic, which model both bounds with the binary variables of a single function, half as many as two separate functions for the bounds would need (Lyu, Hicks and Huchette, 2025). The other methods reject it.

SegmentPointRep{D,F}(input_vals, output_vals)

A piece of a piecewise linear function from R^D to R^F, given by the points input_vals and the function values output_vals at them. The piece is the convex hull of the points, and the function is affine on it. A piece of a relaxation has several values at the same input, see UnivariatePWLRelaxation.

SegmentStructure{D}

How the segments of a piecewise linear function of D inputs are arranged.

Intervals()

The segments of a univariate function or relaxation, which lie over intervals.

Unstructured{D}()

Segments without any known structure, e.g. a triangulation in three or more dimensions.

GridTriangulation

A triangulation of a rectangular grid, where each cell is split into two triangles along one of its diagonals. The subtypes describe how the diagonals are chosen when constructing a BivariatePWLFunction.

K1Triangulation()

Every cell is split along the diagonal from its upper left to its lower right corner.

UnionJackTriangulation()

The diagonals alternate between neighboring cells, forming a Union Jack pattern.

UpperTriangulation()

Every cell is split along the diagonal with the larger average of the function values at its end points, which gives the largest interpolant.

LowerTriangulation()

Every cell is split along the diagonal with the smaller average of the function values at its end points, which gives the smallest interpolant.

BestFitTriangulation()

Every cell is split along the diagonal whose midpoint value is closest to the function value at the center of the cell. This requires the function, not only its values at the grid points.

RandomTriangulation(seed = nothing)

Every cell is split along a random diagonal. If seed is nothing, the seed is derived from the size of the grid.

UnstructuredTriangulation()

A grid triangulation without any known structure, e.g. one built segment by segment.

LogarithmicEmbedding()
Logarithmic()

The logarithmic embedding formulation of univariate continuous piecewise linear functions (Vielma, 2018), the default method for univariate functions.

For d segments, it uses ceil(log2(d)) binary variables and 2 * ceil(log2(d)) constraints in addition to the d + 1 convex multipliers. It can also be used as the axis method of the bivariate grid formulations.

LogarithmicIndependentBranching()

The logarithmic independent branching formulation of univariate continuous piecewise linear functions (Vielma and Nemhauser, 2011), based on the binary reflected Gray code.

For d segments, it uses ceil(log2(d)) binary variables and 2 * ceil(log2(d)) constraints in addition to the d + 1 convex multipliers. See also IndependentBranching.

IndependentBranching(scheme::Symbol = :biclique)

Logarithmically sized ideal formulation of univariate piecewise linear functions, based on independent branching over the ordered segments (Lyu, Hicks and Huchette, 2023). It supports discontinuous functions and relaxations, see UnivariatePWLRelaxation, and can be used as the axis method of the bivariate grid formulations.

The scheme gives the construction of the branching levels:

• :biclique: biclique cover from a balanced reversed edge ranking (Theorem 4).
• :balanced: balanced Gray code (Theorem 1 and Remark 4).
• :brgc: binary reflected Gray code (Theorem 1), equivalent to LogarithmicIndependentBranching for continuous functions.

ZigZagBinary()

The binary zig-zag formulation of univariate continuous piecewise linear functions (Huchette and Vielma, 2023).

For d segments, it uses ceil(log2(d)) binary variables and 2 * ceil(log2(d)) constraints in addition to the d + 1 convex multipliers.

ZigZagInteger()

The general integer zig-zag formulation of univariate continuous piecewise linear functions (Huchette and Vielma, 2023).

For d segments, it uses ceil(log2(d)) bounded general integer variables and 2 * ceil(log2(d)) constraints in addition to the d + 1 convex multipliers.

Incremental()

The incremental formulation of univariate continuous piecewise linear functions (see Vielma, Ahmed and Nemhauser, 2010).

For d segments, it uses d - 1 binary variables and d continuous variables for the fill of each segment.

NativeSOS2()

Formulates univariate continuous piecewise linear functions with the convex multipliers in a special ordered set of type 2 (MOI.SOS2), leaving the branching to the solver. It adds no integer variables.

For solvers without support for SOS2 constraints, such as HiGHS, MathOptInterface reformulates the constraint with binary variables. For solvers with support, e.g. Gurobi, it can also be a good axis method for the bivariate formulations.

ConvexPieces(encoding = :mc)

Formulation of univariate piecewise linear functions with a binary variable for each convex piece.

It is meant for the Epigraph or Hypograph direction, where only the convex pieces of the function need integer variables, rather than its segments. With Epigraph, consecutive segments that join continuously with nondecreasing slopes form a convex piece, whose epigraph is a convex polyhedron. The epigraph of the function is the union of the epigraphs of its pieces, which is formulated with a copy of the input and output for each piece, as MultipleChoice does for segments (Balas, 1998). With Hypograph, the pieces are concave instead. A function that is convex in the direction needs no integer variables, and e.g. an S-shaped utility that is maximized needs one for the concave part and one for each segment of the convex part. With the default direction, every segment is a piece, which gives the MultipleChoice formulation.

With encoding = :mc, there is a binary variable for each piece, and the formulation is ideal. With encoding = :log, the active piece is encoded with ceil(log2(p)) binary variables for p pieces, as in DisaggregatedLogarithmic.

The function may be discontinuous, and the pieces then end at the jumps.

SixStencil(axis_method = Logarithmic())

Formulation of bivariate continuous piecewise linear functions on any grid triangulation (Huchette and Vielma, 2023).

It combines an SOS2 constraint along each axis, formulated with axis_method, with 6 binary variables to select the triangle in the chosen cell. Fewer are needed on small grids, or when the diagonals of all cells have the same direction, as levels that separate nothing are left out.

NineStencil(axis_method = Logarithmic())

Formulation of bivariate continuous piecewise linear functions on any grid triangulation (Huchette and Vielma, 2023).

It combines an SOS2 constraint along each axis, formulated with axis_method, with 9 binary variables to select the triangle in the chosen cell. Fewer are needed on small grids, as levels that separate nothing are left out.

GreedyTriangleSelection(axis_method = Logarithmic(); tries = 200)

Formulation of bivariate continuous piecewise linear functions on any grid triangulation, which selects the triangle with a few binary variables found by a greedy heuristic.

It combines an SOS2 constraint along each axis, formulated with axis_method, with a triangle selection like that of OptimalTriangleSelection, but the levels that select the triangle are found greedily instead of by a mixed-integer program. The cells are inserted into the first level where they fit, and the best of tries random orders of the cells is kept. This takes milliseconds, needs no solver, and typically gives the optimal number of binary variables: 2 for K1Triangulation, 1 for UnionJackTriangulation, and a few more for irregular triangulations. The result is cached for each triangulation.

OptimalTriangleSelection(
    sub_solver,
    axis_method = Logarithmic();
    time_limit = 60.0,
)

Formulation of bivariate continuous piecewise linear functions on any grid triangulation (Huchette and Vielma, 2023).

It combines an SOS2 constraint along each axis, formulated with axis_method, with the smallest number of binary variables that select the triangle in the chosen cell, typically 2 to 4. That number is found by solving a mixed-integer program with sub_solver, e.g. HiGHS.Optimizer, and the result is cached for each triangulation.

The program only searches for fewer binary variables than the greedy selection of GreedyTriangleSelection uses, which is often optimal. Proving this takes about a second for regular triangulations of grids up to 8×8, but can take much longer for irregular ones. If it is not done within time_limit seconds, a warning is given and the greedy selection is used. This result is also cached, so the time limit is only spent again with a longer time limit. GreedyTriangleSelection is therefore usually the better choice for large or irregular grids.

HiGHS sets up its threads at the first solve in a Julia session. If HiGHS is both the sub-solver and the solver of a main model with a single thread, also give the sub-solver a single thread, i.e. optimizer_with_attributes(HiGHS.Optimizer, "threads" => 1), or the main model fails to solve.

K1(axis_method = Logarithmic())

Formulation of bivariate continuous piecewise linear functions on a K1Triangulation, the default method for it. Every cell of such a grid is split along the diagonal from its upper left to its lower right corner.

It combines an SOS2 constraint along each axis, formulated with axis_method, with 2 binary variables to select the triangle in the chosen cell.

UnionJack(axis_method = Logarithmic())

Formulation of bivariate continuous piecewise linear functions on a UnionJackTriangulation, the default method for it (Vielma and Nemhauser, 2011). The diagonals of such a grid alternate between neighboring cells.

It combines an SOS2 constraint along each axis, formulated with axis_method, with 1 binary variable to select the triangle in the chosen cell.

OptimalIndependentBranching(sub_solver; time_limit = 60.0)

Independent branching formulation with the fewest binary variables.

It formulates bivariate continuous piecewise linear functions on any grid triangulation with the smallest number of binary variables (Huchette and Vielma, 2019), at least ceil(log2(t)) for t triangles.

That number is found by solving a mixed-integer program with sub_solver, e.g. HiGHS.Optimizer, and the result is cached for each triangulation. Computing it is only practical for small grids, up to about 4×4 points with a regular triangulation, and an error is thrown if no solution is found within time_limit seconds. This failure is also cached, so it is only tried again with a longer time limit. For larger grids, use e.g. GreedyTriangleSelection or OptimalTriangleSelection.

See OptimalTriangleSelection on the number of threads when the sub-solver is HiGHS.

ConvexCombination()

The convex combination formulation of continuous piecewise linear functions.

It works for functions of any dimension (see Vielma, Ahmed and Nemhauser, 2010), with a convex multiplier for each breakpoint and a binary variable for each segment.

It can also be used as the axis method of the bivariate grid formulations.

DisaggregatedLogarithmic()

The logarithmic disaggregated convex combination formulation.

It works for piecewise linear functions of any dimension (see Vielma, Ahmed and Nemhauser, 2010), with a convex multiplier for each vertex of each segment. As the segments do not share multipliers, the function may be discontinuous, and the segments may have several values at a point, as in a UnivariatePWLRelaxation.

For d segments, it uses ceil(log2(d)) binary variables.

MultipleChoice()

The multiple choice formulation of piecewise linear functions of any dimension (see Vielma, Ahmed and Nemhauser, 2010), with a copy of the input and a binary variable for each segment. The segments must be simplices, but the function may be discontinuous.

PWLMethod

The abstract type of the formulation methods, which are passed to PiecewiseLinear with the method keyword.

A new method is a subtype of PWLMethod that implements formulate_pwl!. The subtypes SOS2Method and TriangleSelectionMethod only need to implement a part of the formulation. See the manual on extending the package for details.

SOS2Method <: PWLMethod

The abstract type of methods that formulate the SOS2 constraint on a vector of convex multipliers, i.e. that at most two of them, and those adjacent, are nonzero. A subtype must implement formulate_sos2!, and then formulates continuous univariate functions through the convex multipliers of the breakpoints. It can also be used as the axis method of a TriangleSelectionMethod.

TriangleSelectionMethod <: PWLMethod

The abstract type of methods for continuous bivariate functions on a grid triangulation.

These methods select a cell of the grid with an SOS2 constraint along each axis, formulated with axis_method, and then a triangle in the cell with formulate_triangle_selection!. A subtype must implement the latter, and axis_method unless it has a field axis_method.

formulate_pwl!(
    formulation::PWLFormulation,
    x::NTuple{D},
    y::NTuple{F},
    pwl::PWLFunction{D,F},
    method::PWLMethod,
    direction::Direction,
)

Adds variables and constraints to formulation.model so that the outputs y relate to the function pwl of the inputs x as given by direction.

Implement this for a new PWLMethod, for the dimensions D and F it supports. The inputs and outputs are variables, affine expressions or constants, see Scalar. The segments of pwl are given by segments. Every variable and constraint created must be passed through record!, so that the formulation can be deleted again, and the variables should be named with variable_name. Use constrain_output! to relate an output to its function value in the given direction. Throw an error if pwl is not supported, e.g. because it is discontinuous; the model is then restored.

formulate_sos2!(formulation::PWLFormulation, λ::Vector, method::PWLMethod)

Adds variables and constraints to formulation.model so that at most two of the convex multipliers λ, and those adjacent, are nonzero. The multipliers are variables or affine expressions, and already sum to one.

Implement this for a new SOS2Method. Every other method has a default implementation, which formulates a piecewise linear function whose outputs are the multipliers.

formulate_triangle_selection!(
    formulation::PWLFormulation,
    λ::Matrix,
    nw_se::Matrix{Bool},
    method::TriangleSelectionMethod,
)

Adds variables and constraints to formulation.model that select a triangle in a cell of the grid.

The convex multipliers λ of the grid points are nonzero on at most the four corners of one cell, ensured by the SOS2 constraints along the axes, and must be restricted to one of the two triangles of that cell. Cell (i, j) has the corners λ[i, j], λ[i + 1, j], λ[i, j + 1] and λ[i + 1, j + 1], and is split along the diagonal from λ[i, j + 1] to λ[i + 1, j] if nw_se[i, j] is true, and along the other diagonal otherwise; see cell_diagonals.

Implement this for a new TriangleSelectionMethod. Throw an error if the triangulation is not supported.

axis_method(method::TriangleSelectionMethod)

The method that formulates the SOS2 constraints along the axes of the grid. Defaults to the field axis_method of method.

record!(formulation::PWLFormulation, x)

Registers the variable, constraint, or array of them, x as part of formulation, and returns x. Every variable and constraint that a method adds to the model must be passed through this function, e.g.

z = record!(formulation, JuMP.@variable(model, [1:k], Bin))record!(formulation, JuMP.@constraint(model, sum(z) == 1))

variable_name(formulation::PWLFormulation, name::String)

The base name for variables of formulation called name, e.g. "pwl1_z", to pass as base_name to JuMP.@variable.

constrain_output!(formulation::PWLFormulation, y, value, direction::Direction)

Adds the constraint that the output y equals, is at least or is at most the expression value of the function value, as given by direction.

add_biclique_cover!(formulation::PWLFormulation, λ::AbstractArray, cover)

Adds the independent branching formulation given by a biclique cover.

For each level (L, R) in cover, it adds a binary variable z and the constraints sum(λ[L]) ≤ z and sum(λ[R]) ≤ 1 - z, so that the multipliers in L and those in R cannot be nonzero at the same time (Huchette and Vielma, 2019). The levels are pairs of vectors of indices into λ, either integers or tuples for a matrix. A level with an empty side separates nothing and is left out.

The formulation is valid for a disjunctive constraint on the support of λ if no level separates two multipliers that may be nonzero together, and every pair that may not is separated by some level.

cell_diagonals(nw_se::Matrix{Bool}, i::Int, j::Int)

Returns the diagonals of cell (i, j) of a grid triangulation as (edge, non_edge), where edge is the diagonal that splits the cell into its two triangles and non_edge is the other. Each is a pair of grid indices, e.g. ((i, j + 1), (i + 1, j)), into the matrix of multipliers passed to formulate_triangle_selection! together with nw_se.

A triangle selection must prevent the two ends of non_edge from being nonzero together.

PiecewiseLinearOpt.Scalar

The type of the inputs and outputs of a function in a formulation: variables, expressions or constants.

segments(pwl::PWLFunction{D,F})

The segments of pwl, a vector of SegmentPointRep{D,F}. Read their points with input_values and output_values.

input_values(segment::SegmentPointRep{D,F})

The points of segment, a vector of NTuple{D,Float64}.

output_values(segment::SegmentPointRep{D,F})

The function values at the points of segment, a vector of NTuple{F,Float64}.