PolyhedralRelaxations.jl Function Reference

The struct FormulationInfo holds two dictionaries, one for variable references and the other for constraint references.

Empty contructor for struct FormulationInfo

The struct UnivariateFunctionData holds the inputs provided by the user. It takes in the function and its derivative (as lambda expressions), the partition on the independent variable that the user provides, and the following 3 tolerance values:

• error tolerance denotes the strength of the relaxation (the closer to zero the stronger the relaxation)
• length tolerance (maximum difference between successive derivative values)
• derivative tolerance denotes the tolerance for checking equality of derivative values at subsequent partition points, and finally, the maximum number of additional partition intervals.

Vertex2d is a pair $(x, y)$

Vertex3d is a pair $(x, y, z)$

_build_bilinear_relaxation!(m, x, y, z, x_partition, y_partition, pre_base_name)

Build incremental formulation for $z = xy$ given partition data.

function _build_mccormick_relaxation!(m, x, y, z)

McCormick relaxation of binlinear term

z >= JuMP.lower_bound(x)*y + JuMP.lower_bound(y)*x - JuMP.lower_bound(x)*JuMP.lower_bound(y)
z >= JuMP.upper_bound(x)*y + JuMP.upper_bound(y)*x - JuMP.upper_bound(x)*JuMP.upper_bound(y)
z <= JuMP.lower_bound(x)*y + JuMP.upper_bound(y)*x - JuMP.lower_bound(x)*JuMP.upper_bound(y)
z <= JuMP.upper_bound(x)*y + JuMP.lower_bound(y)*x - JuMP.upper_bound(x)*JuMP.lower_bound(y)

_build_univariate_lp_relaxation!(m, x, y, univariate_function_data, pre_base_name)

Build LP relaxation for $y=f(x)$ given the univariate function data.

_build_univariate_milp_relaxation!(m,x,y,function_data,pre_base_name)

Return a MILPRelaxation object with constraint and RHS information of the MILP formulation of the polyhedral relaxation.

_collect_bilinear_vertices(x_partition, y_partition)

Return a pair of lists with origin vertices as the first element and the non origin vertices as the second element.

Each vertex is an object of the struct Vertex3d $(x, y, xy)$

_collect_vertices(univariate_function_data)

Return a pair of lists with secant vertices as the first element and tangent vertices as the second element.

Each element in the secant vertex list is a pair (x,y) where

• x is an element of univariate_function_data.partition,
• y is the value of the given univariate function at x.

All secant vertices lie on the curve.

Each element in the tangent vertex list is also a pair (x,y). Each position i of the list contains the vertex formed by intersection of tangents of the curve y=univariate_function_data.f(x) at secant_vertices[i] and secant_vertices[i+1]. No tangent vertex will lie on the curve (except for the trivial case where the curve is linear, and all triangles are flat lines).

_get_error_bound(derivative, lb, ub)

Get error bound of a function with derivative derivative in the closed interval [lb,ub].

_get_error_queue(univariate_function_data)

Build a max-priority-queue holding errors of each partition interval in univariate_function_data.partition. Keys of the queue are indices of starting positions of the partition interval in univariate_function_data.partition. Priorities are error bounds of partition intervals. The queue is built as a max-queue for easy access to the maximum error.

_get_lp_relaxation_vertices(univariate_function_data::UnivariateFunctionData)::Vector{Vertex2d}

Return vertices of the LP relaxation of the given function.

_get_max_error_bound(univariate_function_data)

Compute and return maximum value of error bound among all partition intervals.

_get_tangent_vertex(prev_secant_vertex, next_secant_vertex, derivative)

Return $(x,y)$ coordinates of the intersection of tangents drawn at prev_secant_vertex and next_secant_vertex.

_is_refinement_feasible(univariate_function_data, error_queue)

This function checks if the refinement is feasible

_make_filtered_logger(level::Logging.LogLevel)

Helper function to create the filtered logger for PMD

_pr_metafmt(level::Logging.LogLevel, _module, group, id, file, line)

MetaFormatter for ConsoleLogger for PR to adjust log message format

_refine_partition!(univariate_function_data)

Partition refinement schemes (interval bisection)

_validate(x, y, x_partition, y_partition)

Variable bounds and partition consistency checker for bilinear terms

_validate(x, partition)

Variable bounds and partition consistency checker

_validate(univariate_function_data)

Input univariate function data validator

_validate_point(univariate_function_data, x)

Input data point validator

function _variable_domain(var)

Computes the valid domain of a given JuMP variable taking into account bounds and the varaible's implicit bounds (e.g. binary).

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

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).

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)

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

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 paper.

reset_logging_level!()

Resets the log level to Info

restore_global_logger!()

Restores the global logger to its default state (before PMD was loaded)

set_logging_level!(level::Symbol)

Sets the logging level for PR: :Info, :Warn, :Error, :Debug

silence!()

Sets loglevel for PMD to :Error, silencing Info and Warn