`Alpine.Optimizer`

— TypeAlpine.Optimizer struct

`Alpine._add_multilinear_linking_constraints`

— Method`_add_multilinear_linking_constraints(m::Optimizer, λ::Dict)`

This internal function adds linking constraints between λ multipliers corresponding to multilinear terms that share more than two variables and are partitioned. For example, suppose we have λ[i], λ[j], and λ[k] where i=(1,2,3), j=(1,2,4), and k=(1,2,5). λ[i] contains all multipliers for the extreme points in the space of (x1,x2,x3). λ[j] contains all multipliers for the extreme points in the space of (x1,x2,x4). λ[k] contains all multipliers for the extreme points in the space of (x1,x2,x5).

Using λ[i], λ[j], or λ[k], we can express multilinear function x1*x2. We define a linking variable μ(1,2) that represents the value of x1*x2. Linking constraints are μ(1,2) == convex combination expr for x1*x2 using λ[i], μ(1,2) == convex combination expr for x1*x2 using λ[j], and μ(1,2) == convex combination expr for x1*x2 using λ[k].

Thus, these constraints link between λ[i], λ[j], and λ[k] variables.

Reference: J. Kim, J.P. Richard, M. Tawarmalani, Piecewise Polyhedral Relaxations of Multilinear Optimization, http://www.optimization-online.org/DB_HTML/2022/07/8974.html

`Alpine._get_discretization_dict`

— Method`_get_discretization_dict(m::Optimizer, lbs::Vector{Float64}, ubs::Vector{Float64})`

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

`Alpine._get_shared_multilinear_terms_info`

— Function`_get_shared_multilinear_terms_info(λ, linking_constraints_degree_limit)`

This function checks to see if linking constraints are necessary for a given vector of each multilinear terms and returns the approapriate linking constraints information.

`Alpine._is_fully_convexified`

— Method*is*fully_convexified(m::Optimizer)

`Alpine.add_adaptive_partition`

— Method`add_adaptive_partition(m::Optimizer; use_disc::Dict, use_solution::Vector)`

A built-in method used to add a new partition on feasible domains of variables chosen for partitioning.

This can be illustrated by the following example. Let the previous iteration's partition vector on variable "x" be given by [0, 3, 7, 9]. And say, the lower bounding solution has a value of 4 for variable "x". In the case when `partition_scaling_factor = 4`

, this function creates the new partition vector as follows: [0, 3, 3.5, 4, 4.5, 7, 9]

There are two options for this function,

```
* `use_disc(default=m.discretization)`:: to regulate which is the base to add new partitions on
* `use_solution(default=m.best_bound_sol)`:: to regulate which solution to use when adding new partitions on
```

This function can be accordingly modified by the user to change the behavior of the solver, and thus the convergence.

`Alpine.algorithm_automation`

— MethodA wrapper function that collects automated solver adjustments within the main while loop.

`Alpine.amp_convhull_prepare`

— Method`Method for general nonlinear terms`

`Alpine.amp_convhull_prepare`

— Method`Method for integers`

`Alpine.amp_convhull_α`

— Method`General Method for all term`

`Alpine.amp_convhull_λ`

— Method`Method for general nonlinear terms`

`Alpine.amp_post_convexification`

— Method`amp_post_convexification(m::Optimizer; use_disc = nothing)`

Wrapper function to apply piecewise convexification of the problem for the bounding MIP model. This function talks to nonconvex_terms and convexification methods to finish the last step required during the construction of bounding model.

`Alpine.amp_post_convhull_constrs`

— Method`Method for general multilinear terms`

`Alpine.amp_post_convhull_constrs`

— Method`Constraints for univariate quadratic terms`

`Alpine.amp_post_inequalities_cont`

— Method`Method for multilinear terms with only continuous variables`

`Alpine.bound_propagation`

— Method`detect_bound_from_aff(m::Optimizer)`

Detect bounds from parse affine constraint. This function examines the one variable constraints such as x >= 5, x <= 5 or x == 5 and fetch the information to m.l*var*tight and m.u*var*tight.

`Alpine.bound_tightening_wrapper`

— Method`bound_tightening_wrapper(m::Optimizer)`

Entry point to 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 in `optimization_based_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

`Alpine.bounding_solve`

— MethodAlp.bounding_solve(m::Optimizer; kwargs...)

This step usually solves a convex MILP/MIQCP/MIQCQP problem for lower bounding the given minimization problem. It solves the problem built upon a piecewise convexification based on the discretization sictionary of some variables. See `create_bounding_mip`

for more details of the problem solved here.

`Alpine.build_constr_block`

— MethodThis utility function builds a constraint reference by repeating one operator with a vector variable references. For example, input => y, x[1,2,3], :+ output => (y = x[1] + x[2] + x[3])::Expr

`Alpine.build_discvar_graph`

— Method`Alpine.check_exit`

— MethodSummarized function to determine whether to interrupt the main while loop.

`Alpine.check_solution_history`

— Methodcheck*solution*history(m::Optimizer, ind::Int)

Check if the solution is always the same within the last disc*consecutive*forbid iterations. Return `true`

if solution has stalled.

`Alpine.correct_point`

— Method`This function targets to address unexpected numerical issues when adding partitions in tight regions.`

`Alpine.create_bounding_mip`

— Method`create_bounding_mip(m::Optimizer; use_disc = nothing)`

Set up a 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 piecewise polyhedral/convex relaxations to tighten the basic relaxations of 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.

`Alpine.create_obbt_model`

— Method`create_obbt_model(m::Optimizer, 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 `optimization_based_bound_tightening`

.

`Alpine.detect_bilinear_term`

— Method```
Future MONOMIAL Cluster
Recognize bilinear terms: x * y, where x and y are continous variables
Recognize multilinear terms: x1 * x2 * .. * xN, where all x_i ∀ i are continous variables
Recognize monomial terms: x^2 or x * x, where x is continuous
```

`Alpine.detect_binprod_term`

— Method`Recognize products of binary variables : x1 * x2 * .. * xN`

`Alpine.detect_discretemulti_term`

— Method```
Recognize prodcuts of binary variables and multilinear products
General Case : x1 * x2 .. * xN * y1 * y2 .. * yM
where x are binary variables, y are continous variables
Leads to BINLIN terms, with BINPROD, INTPROD, INTLIN if necessary
```

`Alpine.detect_nonconvex_terms`

— Method`detect_nonconvex_terms(expr, m::Optimizer)`

This function recognizes, stores, and replaces a sub-tree `expr`

with available user-defined/built-in structures patterns. The procedure creates the required number of lifted variables based on the patterns that it is trying to recognize. Then, it goes through all built-in structures and performs operatins to convexify the problem.

Specific structure pattern information will be described formally.

`Alpine.discretization_to_bounds`

— Methoddiscretization*to*bounds(d::Dict, l::Int)

Same as `update_var_bounds`

`Alpine.ebd_I`

— Method`This function is the same I() function described in Vielma and Nemhauser 2011.`

`Alpine.ebd_S`

— Method`This function is the same S() function described in Vielma and Nemhauser 2011.`

`Alpine.ebd_binary`

— Method```
Built-in Encoding methods: binary encoding
This is a compatible encoding
```

`Alpine.ebd_gray`

— Method```
Built-in Encoding methods: gray encoding
This is a compatible encoding
```

`Alpine.ebd_link_expression`

— Method```
This is a utility function used in ebd_link_xα() that constructing the mapping that links partitions with
combinations of binary variables.
```

`Alpine.ebd_link_xα`

— Method```
This is the function that translate the bounding constraints (α¹b⁰+α²b¹ <= x <= α¹b¹+α²b²)
with log # of binary variables, i.e., generate these constraints using log # of binary variables.
```

`Alpine.ebd_support_binary_vec`

— Method`This is a utility function that convert the binary string into 0/1 vector`

`Alpine.ebd_support_bool_vec`

— Method`This is a utility function that convert the binary string into bool vector`

`Alpine.ebd_σ`

— Method`This function is the same σ() function described in Vielma and Nemhauser 2011.`

`Alpine.embedding_map`

— Function```
This function creates a mapping dictionary to link the right λ to the right bineary variables
based on how many partitions are required and a given encoding method.
```

`Alpine.expr_arrangeargs`

— MethodRe-arrange children by their type. Only consider 3 types: coefficients(Int64, Float64), :ref, :calls Sequence arrangement is dependent on operator

`Alpine.expr_constr_parsing`

— FunctionAlp.expr*constr*parsing(expr, m::Optimizer)

Recognize structural constraints.

`Alpine.expr_conversion`

— MethodSTEP 4: convert the parsed expressions into affine-based function that can be used for adding JuMP constraints

`Alpine.expr_finalized`

— MethodSTEP 5: collect information as needed for handy operations in the algorithm section

`Alpine.expr_flatten`

— FunctionRecursively pre-process the expression by treating the coefficients TODO: this function requires a lot of refining. Most issues can be caused by this function.

`Alpine.expr_initialization`

— MethodSTEP 1: initialize the expression/ space

`Alpine.expr_is_emptysum`

— MethodCheck if it is a sample of `+()`

`Alpine.expr_is_fractional_exponent`

— MethodCheck if a sub-tree(:call) is contains any non-integer exponent values

`Alpine.expr_isconst`

— MethodCheck if a sub-tree(:call) is totally composed of constant values

`Alpine.expr_isolate_const`

— MethodConverts ((a*1*x[1])^2 + (a*2*x[2])^2 + ... + (a_n*x[n])^2) to (a*1^2*x[1]^2 + a*2^2*x[2]^2 + ... + a_n^2*x[n]^2) Signs in the summation can be +/- Note: This function does not support terms of type (a*(x[1] + x[2]))^2 yet.

`Alpine.expr_linear_to_affine`

— MethodThis function takes a constraint/objective expression and converts it into a affine expression data structure Use the function to traverse linear expressions traverse*expr*linear*to*affine()

`Alpine.expr_parsing`

— MethodSTEP 3: parse expression for patterns on either the generic level or term level

`Alpine.expr_preprocess`

— MethodSTEP 2: preprocess expression for trivial sub-trees and nasty pieces for easier later process

`Alpine.expr_resolve_const`

— MethodCheck if a sub-tree is a constant or not

`Alpine.expr_resolve_const_denominator`

— MethodIf the expression's fraction has a constant denominator, then replace the expression as product of a constant and the expression

`Alpine.expr_resolve_sign`

— FunctionThis function is treats the sign in expression trees by cleaning the following structure: args ::+ || ::- ::Call || ::ref By separating the structure with some dummy treatments

`Alpine.expr_term_parsing`

— Function`expr_term_parsing(expr, m::Optimizer, level=0)`

Recognize and process nonlinear terms in an expression

`Alpine.fix_domains`

— Methodfix_domains(m::Optimizer)

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.

`Alpine.flatten_discretization`

— Method`flatten_discretization(discretization::Dict)`

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

`Alpine.get_active_partition_idx`

— MethodCollect active partition idx Need to be careful with the diverted point

`Alpine.get_candidate_disc_vars`

— Methodget*candidate*disc_vars(m:Optimizer)

A built-in method for selecting variables for discretization. This function selects all candidate variables in the nonlinear terms for discretization, if under a threshold value of the number of nonlinear terms.

`Alpine.global_solve`

— Methodglobal_solve(m::Optimizer)

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.

`Alpine.init_disc`

— Method`init_disc(m::Optimizer)`

This function initialize the dynamic discretization used for any bounding models. By default, it takes (.l*var*orig, .u*var*orig) 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 :Optimizer.discretization.

`Alpine.init_tight_bound`

— Method`init_tight_bound(m::Optimizer)`

Initialize internal bound vectors (placeholders) to be used in other places. In this case, we don't have to mess with the original bound information.

`Alpine.is_compatible_encoding`

— Method`This function checks whether the encoding method is compatible or not to obtain a valid mapping.`

`Alpine.local_solve`

— MethodAlp.local_solve(m::Optimizer, 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`

.

`Alpine.min_vertex_cover`

— Methodmin*vertex*cover(m::Optimizer)

`min_vertex_cover`

chooses the variables based on the minimum vertex cover algorithm for the interaction graph of nonlinear terms which are adaptively partitioned for global optimization. This option can be activated by setting `disc_var_pick = 1`

.

`Alpine.ncvar_collect_arcs`

— MethodReconsideration required

`Alpine.optimization_based_bound_tightening`

— Method`optimization_based_bound_tightening(m:Optimizer; 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 Nagarajan, Lu, Wang, Bent, Sundar, "An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs" link.

Several other user-input options can be used to tune the OBBT algorithm. For more details, see Presolve Options.

`Alpine.pick_disc_vars`

— Methodpick*disc*vars(m::Optimizer)

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 (Alp.get_option(m, :disc_var_pick)=0, default)`

: pick all variables involved in the non-linear term for discretization`min_vertex_cover (Alp.get_option(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, `Alp.get_option(m, :disc_var_pick)`

allows `::Function`

inputs. User can provide his/her own function to choose the variables for discretization.

`Alpine.populate_convhull_extreme_values`

— Function`Method for regular multilinear terms`

`Alpine.populate_convhull_extreme_values`

— Method`Method for power terms`

`Alpine.post_objective_bound`

— Method`post_objective_bound(m::Optimizer, bound::Float64; kwargs...)`

This function adds the upper/lower bounding constraint on the objective function for the optimization models solved within the OBBT algorithm.

`Alpine.presolve`

— Methodpresolve(m::Optimizer)

`Alpine.process_expr`

— Methodprocess_expr(expr; kwargs...)

High-level wrapper for processing expression with sub-tree operators

`Alpine.recategorize_var`

— Method`Recategorize :Int variables to :Bin variables if variable bounds are [0,1]`

`Alpine.relaxation_bilinear`

— Method```
relaxation_bilinear(
m::JuMP.Model,
z::JuMP.VariableRef,
x::JuMP.VariableRef,
y::JuMP.VariableRef,
lb_x::Number,
ub_x::Number,
lb_y::Number,
ub_y::Number)
```

General relaxation of a binlinear term (McCormick relaxation).

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

`Alpine.relaxation_multilinear_binary`

— Method```
relaxation_multilinear_binary(
m::JuMP.Model,
z::JuMP.VariableRef,
x::Vector{VariableRef})
```

Applies Fortet linearization (see https://doi.org/10.1007/s10288-006-0015-3) for z = prod(x), where x is a vector of binary variables.

`Alpine.resolve_convex_constr`

— Function```
Recognize convex constraints
A catch for type-A convex constraint expression
```

`Alpine.resolve_encoding_key`

— Method`This function parse the encoding key string and return the built-in encoding function.`

`Alpine.resolve_inf_bounds`

— Method`Resolving Inf variable bounds since Alpine relies on finite bounds to construct relaxations`

`Alpine.resolve_lifted_var_type`

— MethodMention the variable type of the lifted term. This function is with limited functionality

`Alpine.resolve_lifted_var_value`

— MethodFollow the definition of terms to calculate the value of lifted terms

`Alpine.resolve_var_bounds`

— Method```
resolve_var_bounds(nonconvex_terms::Dict, discretization::Dict)
For discretization to be performed, we do not allow a variable being discretized to have infinite bounds.
The lifted/auxiliary variables may have infinite bounds and the function infers bounds on these variables. This process
can help speed up the subsequent solve times.
Only used in presolve bound tightening
```

`Alpine.resolve_var_bounds`

— Method`resolve_var_bounds(m::Optimizer)`

Resolve the bounds of the lifted variable using the information in l*var*tight and u*var*tight. This method only takes in known or trivial bounds information to deduce lifted variable bounds and to potentially avoid the cases of infinity bounds.

`Alpine.set_mip_time_limit`

— Method`set_mip_time_limit(m::Optimizer)`

An utility function used to dynamically regulate MILP solver time limits to fit Alpine solver's time limits.

`Alpine.solve_obbt_model`

— Method`solve_obbt_model(m::Optimizer)`

A function that solves the min and max OBBT model.

`Alpine.summary_status`

— MethodThis function summarizes the eventual solver status based on all available information recorded in the solver. The output status is self-defined which requires users to read our documentation to understand the details behind every status symbols.

`Alpine.traverse_expr_linear_to_affine`

— Functiontraverse*expr*linear*to*affine(expr, lhscoeffs=[], lhsvars=[], rhs=0.0, bufferVal=0.0, bufferVar=nothing, sign=1.0, level=0)

This function traverses the left hand side tree to collect affine terms. Updated status : possible to handle (x-(x+y(t-z))) cases where signs are handled properly

`Alpine.update_disc_cont_var`

— Method```
Ranking of variables involved in nonlinear terms for piecewise adaptive partitioning:
Ranked based on the absolute gap between each variable's solution from the lower-bounding MIP and the best feasible solution to the MINLP.
Currently doesn't support recursive convexification
```

`Alpine.update_incumbent`

— MethodUpdate the data structure with feasible solution and its associated objective (if better)

`Alpine.update_opt_gap`

— Methodupdate*opt*gap(m::Optimizer)

Updates Alpine model's relative & absolute optimality gaps.

The relative gap calculation is

\[\textbf{Gap} = \frac{|UB-LB|}{ϵ+|UB|}\]

The absolute gap calculation is

`|UB-LB|`

`Alpine.update_var_bounds`

— Method`update_var_bounds(m::Optimizer, discretization::Dict; len::Float64=length(keys(discretization)))`

This function takes in a dictionary-based discretization information and convert them into two bounds vectors (l*var, u*var) 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}`

`Alpine.variable_values`

— Methodvariable_values(m::JuMP.Model)

Prints values of all the variables after optimizing the original JuMP model.

`MathOptInterface.optimize!`

— MethodHigh-level Function