GitHub

PolyhedralRelaxations.jl Function Reference

PolyhedralRelaxations.UnivariateFunctionData — Type

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.
source
PolyhedralRelaxations._bisect! — Method
_bisect!(partition::Vector{<:Real}, lower::Float64, upper::Float64)::RefinementInfo

This scheme bisects the partition defined by lower and upper values.

source
PolyhedralRelaxations._bisect_all! — Method
_bisect_all!(partition::Vector{<:Real}, refinement_width_tol::Float64)::RefinementInfo

This scheme bisects every partition provided the width of the partition is greater than refinement_width_tol value.

source
PolyhedralRelaxations._build_mccormick_relaxation! — Method
_build_mccormick_relaxation!(m, x, y, z)

McCormick relaxation of bilinear 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)
source
PolyhedralRelaxations._check_if_linking_constraints_are_needed — Method
_check_if_linking_constraints_are_needed(
    info::Dict{T,FormulationInfo} where {T<:Any}, 
    degree_limit::Union{Nothing,T} where {T<:Int64}
)::NamedTuple

This function checks to see if linking constraints are required given the vector of each multilinear terms' FormulationInfo struct

source
PolyhedralRelaxations._collect_bilinear_vertices — Method
_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)$

source
PolyhedralRelaxations._collect_vertices — Method
_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).

source
PolyhedralRelaxations._get_error_queue — Method
_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.

source
PolyhedralRelaxations._get_tangent_vertex — Method
_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.

source
PolyhedralRelaxations._non_uniform! — Method
_non_uniform!(partition, point, lower, upper, added_point_width_tol, ratio)::RefinementInfo

This scheme adds a small partition around the point using the ratio provided while satisfying the added_point_width_tolerance

source
PolyhedralRelaxations._refine_partition! — Method
_refine_partition!(
    partition::Vector{<:Real}, 
    point::T where {T<:Real},
    refinement_type::REFINEMENT_TYPE,
    refinement_ratio::Float64, 
    refinement_width_tol::Float64,
    refinement_added_point_width_tolerance::Float64,
    refine_largest::Bool)::RefinementInfo

Internal helper function to help in partition refinement

source
PolyhedralRelaxations.add_multilinear_linking_constraints! — Method
add_multilinear_linking_constraints!(m, info, partitions; max_degree_limit = nothing, 
    helper = Dict())::FormulationInfo

Add linking constraints for the different multilinear relaxations in the model using the lambda variables for each relaxation.

Reference information: Jongeun Kim, Jean-Philippe P. Richard, Mohit Tawarmalani, Piecewise Polyhedral Relaxations of Multilinear Optimization, http://www.optimization-online.org/DB_HTML/2022/07/8974.html

Mandatory Arguments

  • m::Jump.Model: model to which relaxation is to be added.
  • info::Dict{T,FormulationInfo} where {T<:Any}: dictionary keyed

by tuple of variables involved in multilinear term whose value is the FormulationInfo struct returned by added the multilinear relaxation for that term

  • partitions::Dict{JuMP.VariableRef,Vector{T}} where {T<:Real}: partition

of the domain of the variables.

Optional Keyword Arguments

  • max_degree_limit::Union{Nothing,T} where {T<:Int64}: this is a

control factor for limit the number of linking constraints added. Default value is nothing which will not limit the number of constraints added.

  • helper::Dict - default is the empty dictionary. This dictionary

contains the common subterms that are shared between the different multilinear terms. When the function is invoked the first time, the FormulationInfo returned contains this dictionary in extra[:common_subterm_data]. When invoked the subsequent times, passing this dictionary can save a lot on the computation time required to generate these constraints.

source
PolyhedralRelaxations.construct_bilinear_relaxation! — Method
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
PolyhedralRelaxations.construct_multilinear_relaxation! — Method
construct_multilinear_relaxation!(m,x,y,z,x_partition,y_partition)

Add polyhedral relaxation of z = product(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.
  • x::Tuple: JuMP variables in the multilinear term as a tuple.
  • z::JuMP.VariableRef: JuMP variable z.
  • partitions::Dict{JuMP.VariableRef,Vector{T}} where {T<:Real}: partition

of the domain of the x variables.

Optional Arguments

  • variable_pre_base_name::AbstractString: base_name that needs

to be added to the auxiliary variables for meaningful LP files

  • binary_variables::Dict{JuMP.VariableRef,T} where {T<:Any}: dictionary

of binary partitioning variables corresponding to each variable. If this dictionary has the binary variables corresponding to a variable involved in the multilinear term, it will re-use them, else it will create new ones. Everytime, this dictionary is populated with the binary variables that are created. So, the user only needs to create an empty dict the first time and keep passing this to the function at every call.

This function builds an lambda based SOS2 formulation for the piecewise polyhedral relaxation. Reference information: Kaarthik Sundar, Harsha Nagarajan, Jeff Linderoth, Site Wang, Russell Bent, Piecewise Polyhedral Formulations for a Multilinear Term, https://arxiv.org/abs/2001.00514

source
PolyhedralRelaxations.construct_univariate_relaxation! — Method
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