PolyhedralRelaxations.jl Function Reference
PolyhedralRelaxations.FormulationInfo
— TypeThe struct FormulationInfo
holds two dictionaries, one for variable references and the other for constraint references.
PolyhedralRelaxations.FormulationInfo
— MethodEmpty contructor for struct FormulationInfo
PolyhedralRelaxations.UnivariateFunctionData
— TypeThe 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.
PolyhedralRelaxations.Vertex2d
— TypeVertex2d is a pair $(x, y)$
PolyhedralRelaxations.Vertex3d
— TypeVertex3d is a pair $(x, y, z)$
PolyhedralRelaxations._at_point!
— Method_at_point!(partition::Vector{<:Real}, point::T where {T<:Real})::RefinementInfo
This scheme adds the point to the partition.
PolyhedralRelaxations._bisect!
— Method_bisect!(partition::Vector{<:Real}, lower::Float64, upper::Float64)::RefinementInfo
This scheme bisects the partition defined by lower
and upper
values.
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.
PolyhedralRelaxations._build_bilinear_milp_relaxation!
— Method_build_bilinear_relaxation!(m, x, y, z, x_partition, y_partition, pre_base_name)
Build incremental formulation for $z = xy$ given partition data.
PolyhedralRelaxations._build_linking_constraints!
— Methodbuildlinking_constraints!(m, info, partitions, helper)
Build a linking constraints using the lamba variables for multilinear terms that share more than 2 variables.
PolyhedralRelaxations._build_mccormick_relaxation!
— Method_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)
PolyhedralRelaxations._build_multilinear_convex_hull_relaxation!
— Method_build_multilinear_convex_hull_relaxation!(m, x, z, partitions, pre_base_name)
Build a convex hull formulation LP for for $z = prod(x)$ given partition data.
PolyhedralRelaxations._build_multilinear_sos2_relaxation!
— Method_build_multilinear_milp_relaxation!(m, x, z, partitions, pre_base_name)
Build a piecewise polyhedral relaxation for for $z = prod(x)$ given partition data.
PolyhedralRelaxations._build_univariate_lp_relaxation!
— Method_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.
PolyhedralRelaxations._build_univariate_milp_relaxation!
— Method_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.
PolyhedralRelaxations._check_consistency
— Method_check_consistency(formulation_info, num_vars)
Checks consistency between provided variables and partition sizes
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
PolyhedralRelaxations._check_partition_variable_consistency
— Method_check_partition_variable_consistency(formulation_info, num_vars)
Checks consistency between provided variables and partition sizes
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)$
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).
PolyhedralRelaxations._get_error_bound
— Method_get_error_bound(derivative, lb, ub)
Get error bound of a function with derivative derivative
in the closed interval [lb,ub]
.
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.
PolyhedralRelaxations._get_lp_relaxation_vertices
— Method_get_lp_relaxation_vertices(univariate_function_data::UnivariateFunctionData)::Vector{Vertex2d}
Return vertices of the LP relaxation of the given function.
PolyhedralRelaxations._get_max_error_bound
— Method_get_max_error_bound(univariate_function_data)
Compute and return maximum value of error bound among all partition intervals.
PolyhedralRelaxations._get_slice_indices
— Method_get_slice_indices(var_id::Int64, slice_id::Int64, cartesian_indices)::Vector
Helper function to get all the linear indices corresponding to a variable and slice
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
.
PolyhedralRelaxations._is_refinement_feasible
— Method_is_refinement_feasible(univariate_function_data, error_queue)
This function checks if the refinement is feasible
PolyhedralRelaxations._make_filtered_logger
— Method_make_filtered_logger(level::Logging.LogLevel)
Helper function to create the filtered logger for PR
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
PolyhedralRelaxations._pr_metafmt
— Method_pr_metafmt(level::Logging.LogLevel, _module, group, id, file, line)
MetaFormatter for ConsoleLogger for PR to adjust log message format
PolyhedralRelaxations._refine_partition!
— Method_refine_partition!(univariate_function_data)
Partition refinement schemes (interval bisection)
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
PolyhedralRelaxations._validate
— Method_validate(x, y, x_partition, y_partition)
Variable bounds and partition consistency checker for bilinear terms
PolyhedralRelaxations._validate
— Method_validate(x, partition)
Variable bounds and partition consistency checker
PolyhedralRelaxations._validate
— Method_validate(x, partitions)
Variable bounds and partition consistency checker
PolyhedralRelaxations._validate
— Method_validate(univariate_function_data)
Input univariate function data validator
PolyhedralRelaxations._validate_point
— Method_validate_point(univariate_function_data, x)
Input data point validator
PolyhedralRelaxations._variable_domain
— Methodfunction _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).
PolyhedralRelaxations.add_multilinear_linking_constraints!
— Methodadd_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.
PolyhedralRelaxations.construct_bilinear_relaxation!
— Methodconstruct_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 variablex
.y::JuMP.VariableRef
: JuMP variabley
.z::JuMP.VariableRef
: JuMP variablez
.x_partition::Vector{<:Real}
: partition of the domain ofx
.y_partition::Vector{<:Real}
: partition of the domain ofy
.
Optional Arguments
variable_pre_base_name::AbstractString
: base_name that needs to be added to the auxiliary variables for meaningful LP filesformulation_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).
PolyhedralRelaxations.construct_multilinear_relaxation!
— Methodconstruct_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 variablez
.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
PolyhedralRelaxations.construct_univariate_relaxation!
— Methodconstruct_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 off
.y::JuMP.VariableRef
: JuMP variable for evaluation off
.x_partition::Vector{<:Real}
: partition of the domain off
.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 off
, defaults to thederivative
function from theForwardDiff
package.error_tolerance::Float64
: Maximum allowed vertical distance between over and under estimators off
, 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 isn
and the number of additional partitions ism
, then the function will return a relaxation with at mostn+m
partitions.variable_pre_base_name::AbstractString
: base_name that needs to be added to the auxiliary variables for meaningful LP filesformulation_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 off
such thatf
is either convex or concave each sub-interval of the partition.f_dash
is not equal at two consecutive elements ofx_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.
PolyhedralRelaxations.reset_logging_level!
— Methodreset_logging_level!()
Resets the log level to Info
PolyhedralRelaxations.restore_global_logger!
— Methodrestore_global_logger!()
Restores the global logger to its default state (before PR was loaded)
PolyhedralRelaxations.set_logging_level!
— Methodset_logging_level!(level::Symbol)
Sets the logging level for PR: :Info, :Warn, :Error, :Debug
PolyhedralRelaxations.silence!
— Methodsilence!()
Sets loglevel for PR to :Error, silencing Info and Warn