Functions

presolve(m::AlpineNonlinearModel)

global_solve(m::AlpineNonlinearModel)

Perform global optimization algorithm that is based on the adaptive piecewise convexification. This iterative algorithm loops over bounding_solve and local_solve until the optimality gap between the lower bound (relaxed problem with min. objective) and the upper bound (feasible problem) is within the user prescribed limits. Each bounding_solve provides a lower bound that serves as the partitioning point for the next iteration (this feature can be modified given a different add_adaptive_partition). Each local_solve provides an incumbent feasible solution. The algorithm terminates when atleast one of these conditions are satisfied: time limit, optimality condition, or iteration limit.

local_solve(m::AlpineNonlinearModel, presolve::Bool=false)

Perform a local NLP or MINLP solve to obtain a feasible solution. The presolve option is set to true when the function is invoked in presolve. Otherwise, the function is invoked from bounding_solve.

bounding_solve(m::AlpineNonlinearModel; kwargs...)

This process usually deals with a MILP or a MIQCP/MIQCQP problem for lower bounding the given problem. It solves the problem built upon a convexification base on a discretization Dictionary of some variables. The convexification utilized is Tighten McCormick scheme. See create_bounding_mip for more details of the problem solved here.

create_bounding_mip(m::AlpineNonlinearModel; use_disc::Dict)

Set up a JuMP MILP bounding model base on variable domain partitioning information stored in use_disc. By default, if use_disc is not provided, it will use m.discretizations store in the Alpine model. The basic idea of this MILP bounding model is to use Tighten McCormick to convexify the original Non-convex region. Among all presented partitions, the bounding model will choose one specific partition as the lower bound solution. The more partitions there are, the better or finer bounding model relax the original MINLP while the more efforts required to solve this MILP is required.

This function is implemented in the following manner:

* [`amp_post_vars`](@ref): post original and lifted variables
* [`amp_post_lifted_constraints`](@ref): post original and lifted constraints
* [`amp_post_lifted_obj`](@ref): post original or lifted objective function
* [`amp_post_tmc_mccormick`](@ref): post Tighten McCormick variables and constraints base on `discretization` information

More specifically, the Tightening McCormick used here can be generalized in the following mathematical formulation. Consider a nonlinear term

pickdiscvars(m::AlpineNonlinearModel)

This function helps pick the variables for discretization. The method chosen depends on user-inputs. In case when indices::Int is provided, the method is chosen as built-in method. Currently, there are two built-in options for users as follows:

• max-cover (m.disc_var_pick=0, default): pick all variables involved in the non-linear term for discretization
• min-vertex-cover (m.disc_var_pick=1): pick a minimum vertex cover for variables involved in non-linear terms so that each non-linear term is at least convexified

For advanced usage, m.disc_var_pick allows ::Function inputs. User can provide his/her own function to choose the variables for discretization.

fix_domains(m::AlpineNonlinearModel)

This function is used to fix variables to certain domains during the local solve process in the global_solve. More specifically, it is used in local_solve to fix binary and integer variables to lower bound solutions and discretizing variables to the active domain according to lower bound solution.

bound_tightening(m::AlpineNonlinearModel)

Entry point for the optimization-based bound-tightening (OBBT) algorithm. The aim of the OBBT algorithm

is to sequentially tighten the variable bounds until a fixed point is reached.

Currently, two OBBT methods are implemented minmax_bound_tightening.

* Bound-tightening with polyhedral relaxations (McCormick, Lambda for convex-hull) 
* Bound-tightening with piecewise polyhedral relaxations: (with three partitions around the local feasible solution)
If no local feasible solution is obtained, the algorithm defaults to OBBT without partitions

minmax_bound_tightening(m:AlpineNonlinearModel; use_bound::Bool=true, use_tmc::Bool)

This function implements the OBBT algorithm to tighten the variable bounds. It utilizes either the basic polyhedral relaxations or the piecewise polyhedral relaxations (TMC) to tighten the bounds. The TMC has additional binary variables while performing OBBT.

The algorithm as two main parameters. The first is the use_tmc, which when set to true invokes the algorithm on the TMC relaxation. The second parameter use_bound takes in the objective value of the local solve solution stored in best_sol for performing OBBT. The use_bound option is set to true when the local solve is successful in obtaining a feasible solution, else this parameter is set to false

For details, refer to section 3.1.1 of Nagarjan, Lu, Wang, Bent, Sundar, "An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs" URL: https://goo.gl/89zrDf

Several other parameters are available for the OBBT algorithm tuning. For more details, see Parameters.

create_bound_tightening_model(m::AlpineNonlinearModel, discretization::Dict, bound::Float64)

This function takes in the initial discretization information and builds the OBBT model. It is an algorithm specific function called by minmax_bound_tightening

solve_bound_tightening_model(m::AlpineNonlinearModel)

A function that solves the min and max OBBT model.

resolve_var_bounds(m::AlpineNonlinearModel)

Resolve the bounds of the lifted variable using the information in lvartight and uvartight. This method only takes in known or trivial bounds information to reason lifted variable bound to avoid the cases of infinity bounds.

resolve_var_bounds(nonconvex_terms::Dict, discretization::Dict)

For discretization to be performed, we do not allow for a variable being discretized to have infinite bounds.
The lifted variables will have infinite bounds and the function infers bounds on these variables. This process
can help speed up the subsequent solve in subsequent iterations.

Only used in presolve bound tightening

update_var_bounds(m::AlpineNonlinearModel, discretization::Dict; len::Float64=length(keys(discretization)))

This function take in a dictionary-based discretization information and convert them into two bounds vectors (lvar, uvar) by picking the smallest and largest numbers. User can specify a certain length that may contains variables that is out of the scope of discretization.

Output::

l_var::Vector{Float64}, u_var::Vector{Float64}

discretizationtobounds(d::Dict, l::Int)

Same as update_var_bounds

init_disc(m::AlpineNonlinearModel)

This function initialize the dynamic discretization used for any bounding models. By default, it takes (.lvarorig, .uvarorig) as the base information. User is allowed to use alternative bounds for initializing the discretization dictionary. The output is a dictionary with MathProgBase variable indices keys attached to the :AlpineNonlinearModel.discretization.

to_discretization(m::AlpineNonlinearModel, lbs::Vector{Float64}, ubs::Vector{Float64})

Utility functions to convert bounds vectors to Dictionary based structures that is more suitable for partition operations.

flatten_discretization(discretization::Dict)

Utility functions to eliminate all partition on discretizing variable and keep the loose bounds.

updatemiptime_limit(m::AlpineNonlinearModel) An utility function used to dynamically regulate MILP solver time limits to fit Alpine solver time limits.