API

Basic Usage

Here is an example illustrating the basic API for univariate functions.

using PolyhderalRelaxations, JuMP
m = Model() 
JuMP.@variable(m, -1.0 <= x <= 1.0)
JuMP.@variable(m, y)
f = x -> x^3
construct_univariate_relaxation!(m, f, x, y, [-1.0, 0.0, 1.0], true)

For bilinear functions, the basic API is as follows:

using PolyhderalRelaxations, JuMP
m = Model() 
JuMP.@variable(m, -1.0 <= x <= 1.0)
JuMP.@variable(m, -10.0 <= y <= 12.0)
JuMP.@variable(m, z)
construct_bilinear_relaxation!(m, x, y, z, [-1.0, 1.0], [-10.0, 12.0])

If there is only one partition (like above) for each variable, then the function formulates the McCormick relaxation. The package supports more than one partition only one of the variables x or y. Support for multi-variable partitioning will be added in the future versions. The following example illustrates the API for more than one partitions on the x2 variable:

using PolyhderalRelaxations, JuMP
m = Model() 
JuMP.@variable(m, -1.0 <= x1 <= 1.0)
JuMP.@variable(m, -1.0 <= x2 <= 1.0)
JuMP.@variable(m, z)
construct_bilinear_relaxation!(m, x1, x2, z, [-1.0, 1.0], [-1.0, -0.25, 0.25, 1.0])

For examples, the reader is referred to the unit tests in the test/ folder of the GitHub repository.

API for the MILP/LP Relaxation for Nonlinear Univariate function

The API documentation for both the MILP and the LP relaxations for a given nonlinear univariate function is as follows:

PolyhedralRelaxations.construct_univariate_relaxation! — Function

construct_univariate_relaxation!(m,f,x,y,x_partition;f_dash=x->ForwardDiff.derivative(f,x),error_tolerance=NaN64,length_tolerance=1e-6,derivative_tolerance=1e-6,num_additional_partitions=0,variable_pre_base_name="",formulation_info=FormulationInfo())

Add MILP relaxation of y=f(x) to given JuMP model and return an object with new variables and constraints.

Mandatory Arguments

m::JuMP.Model: model to which relaxation is to be added.
f::Function: function or oracle for which a polyhedral relaxation is required, usually non-linear.
x::JuMP.VariableRef: JuMP variable for domain of f.
y::JuMP.VariableRef: JuMP variable for evaluation of f.
x_partition::Vector{<:Real}: partition of the domain of f.
milp::Bool: build MILP relaxation if true, LP relaxation otherwise. Note that the MILP relaxation uses the incremental formulation presented in the paper, but the LP relaxation uses a lambda form that builds a formulation as the convex combination of triangle vertices that are at the intersection of tangents to the curve.

Optional Arguments

f_dash::Function: function or oracle for derivative of f, defaults to the derivative function from the ForwardDiff package.
error_tolerance::Float64: Maximum allowed vertical distance between over and under estimators of f, defaults to NaN64.
length_tolerance::Float64: maximum length of a sub-interval in a partition, defaults to $1 \times 10^{-6}$.
derivative_tolerance::Float64: minimum absolute difference between derivaties at successive elements of a partition for them to be considered different, defaults to $1 \times 10^{-6}$. If the difference of a partition sub-interval is smaller than this value, that sub-interval will be refined.
num_additional_partitions::Int64: budget on number of sub-intervals in partition, defaults to 0. Note that if the number of partitions is n and the number of additional partitions is m, then the function will return a relaxation with at most n+m partitions.
variable_pre_base_name::AbstractString: base_name that needs to be added to the auxiliary variables for meaningful LP files
formulation_info::FormulationInfo : FormulationInfo for another univariate function on the same variable that can be reused for the current relaxation.

Assume that:

f is a bounded function of 1 variable.
x_partition is a partition of the domain of f such that f is either convex or concave each sub-interval of the partition.
f_dash is not equal at two consecutive elements of x_partition.

This function builds an incremental formulation, which is the formulation presented in the following reference:

Kaarthik Sundar, Sujeevraja Sanjeevi, and Harsha Nagarajan (2022). Sequence of Polyhedral Relaxations for Nonlinear Univariate Functions, https://arxiv.org/abs/2005.13445.

source

The derivate of the function is an optional keyword argument. If the derivate is not specified, the package invokes ForwardDiff.jl to compute the derivative.

API for the MILP/LP Relaxation for Bilinear Term

The API for both the MILP and the LP relaxations for a bilinear term is as follows:

PolyhedralRelaxations.construct_bilinear_relaxation! — Function

construct_bilinear_relaxation!(m,x,y,z,x_partition,y_partition)

Add polyhedral relaxation of z = xy to given JuMP model and return an object with new variables and constraints.

Mandatory Arguments

m::Jump.Model: model to which relaxation is to be added.
x::Jump.VariableRef: JuMP variable x.
y::JuMP.VariableRef: JuMP variable y.
z::JuMP.VariableRef: JuMP variable z.
x_partition::Vector{<:Real}: partition of the domain of x.
y_partition::Vector{<:Real}: partition of the domain of y.

Optional Arguments

variable_pre_base_name::AbstractString: base_name that needs to be added to the auxiliary variables for meaningful LP files
formulation_info::FormulationInfo : FormulationInfo for another bilinear function where the variables that is partitioned has to be same on both; to enable partition variable reuse

This function builds an incremental formulation, and currently supports more than one partition only on one of the variables x or y and not on both. It will throw an error when more than one partitions are provided on both variables. When exactly one partition is input for both variables, it populates the model with the McCormick relaxation. The incremental formulation is similar to the triangle chain relaxation in the manuscript with the triangles replaced with tetrahedrons. Adjacent tetrahedrons share an edge (instead of a point in the triangles case).

source

Additional Algorithms for Relaxations of Univariate Functions

Apart from providing MILP and LP relaxations of graphs of univariate function $y=f(x)$ for a given partition, the package also implements some basic partitioning algorithms to refine the partition and provide tighter relaxations. Given a partition, PolyhedralRelaxations.jl can refine the partition using an interval-bisection algorithm detailed in the following reference:

K. Sundar, S. Sanjeevi, and H, Nagarajan (2020). Sequence of Polyhedral Relaxations for Nonlinear Univariate Functions. (arxiv link)

The partition refinement scheme is equipped with multiple stopping criteria that can be toggled by setting non-default values to the following keyword arguments in the standard API:

error_tolerance: this parameter measures the maximum vertical distance between the under- and over-estimators of the relaxation within the domain of the univariate function. By default, this value is set to NaN64. Setting a non-zero positive value for this parameter would result partition and a corresponding relaxation such that the maximum vertical distance between the under- and over-estimators of the relaxation is at most the value prescribed by error_tolerance.
num_additional_partitions: this parameter as the name suggests will refine the partition using the interval bisection algorithm till the total number of additional partitions reaches this number. It's default value is set to 0.

The refinement algorithm will stop if either of the above two stopping criteria is satisfied.

Tolerance parameters

The main functions to produce the relaxations are also equipped with the following two tolerance parameters:

length_tolerance: this parameter is used to control the refinement algorithm. A partition whose length is less than the length_tolerance is not partitioned further. The default value of this parameter is $\epsilon = 1 \times 10^{-6}$.
derivative_tolerance: when the refinement algorithm is used with the base_partition not containing the inflection points of the function in its domain, the resulting relaxations will be erroneous i.e., there is no guarantee that the relaxation obtained is even valid. One necessary condition to detect this issue is by ensuring that the derivatives at successive partition points are not equal. This condition is checked up to the tolerance specified by this parameter. The default value of this parameter is $\epsilon = 1 \times 10^{-6}$.