Customization Guidelines

This section contains general guidelines on how the functionality of EAGO can be extended for specific use cases. Many functions in EAGO are extensible, so examples are not provided for every possible case, but some important functions are covered. If there is a use case you do not see provided here, but would like to see, please contact Robert Gottlieb.

1) Creating an Extension

Extensibility in EAGO is based on the EAGO.ExtensionType type. To create customized functions, the recommended method is to create a new structure, as follows:

using EAGO

struct MyNewStruct <: EAGO.ExtensionType end

To let EAGO know that you would like to use this extension (and any functions you overload), when you create the JuMP model, declare your new type in the SubSolvers field of EAGO's optimizer as follows:

using JuMP

factory = () -> EAGO.Optimizer(SubSolvers(; t = MyNewStruct() ))
model = Model(factory)

The key point to note here is that the new structure is set to SubSolvers.t, which is the field that holds any user-defined extension type. Now, when EAGO calls any of its functions, it will check to see if a custom function for this new extension has been created. If so, it will use the new one; if not, it will use the default version of that function.

2) Preprocessing

In EAGO's branch-and-bound routine, preprocessing is performed prior to solving the lower and upper problems. By default, linear and quadratic contractor methods are performed, followed by interval constraint propagation, then optimization-based bounds tightening. An important outcome of EAGO's default preprocessing is that the _preprocess_feasibility field of the EAGO.GlobalOptimizer is set to true, unless the subproblem at the current node has been proven infeasible. Therefore, to bypass preprocessing for your own problem, you must, at a minimum, set this field to true. For example:

import EAGO: preprocess!
function EAGO.preprocess!(t::MyNewStruct, x::EAGO.GlobalOptimizer)
    x._preprocess_feasibility = true
end

The user-defined preprocessing step can be as simple or complex as desired, but if _preprocess_feasibility is not set to true, EAGO will assume each node is infeasible.

3) Lower problem

By default, EAGO applies Kelley's cutting-plane algorithm[1] to solve the lower bounding problem. This can be overloaded using the same syntax as for the other functions. Necessary changes to the EAGO.GlobalOptimizer that occur within the lower problem are changing the _lower_objective_value and _lower_feasibility fields. If the _lower_objective_value field is not changed, branch-and-bound will not update the lower bound. If _lower_feasibility is not set to true, the node will be discarded as infeasible. A minimum functional (though not useful) lower problem extension is as follows:

import EAGO: lower_problem!
function EAGO.lower_problem!(t::MyNewStruct, x::EAGO.GlobalOptimizer)
    x._lower_objective_value = -Inf
    x._lower_feasibility = true
end

Any arbitrarily complex lower problem can be substituted here in place of EAGO's default method, as long as these fields are updated. Note also that, although there is a separate upper problem function, if the lower problem is being replaced by an algorithm that also calculates an upper objective value, the necessary fields to update in upper_problem! can simply be updated here, and the upper_problem! can be overloaded by a function that does nothing.

4) Upper problem

By default, the upper bounding problem is run on every node up to depth upper_bounding_depth, and is triggered with a probability of 0.5^(depth - upper_bounding_depth) afterwards for continuous problems. For integer problems, this approach is used in addition to running on every node up to depth upper_bounding_depth + cont_depth, with another trigger of probability 0.5^(depth - upper_bounding_depth - cont_depth). The upper_bounding_depth and cont_depth are fields of GlobalOptimizer._parameters and can be changed from their default values when the JuMP model is created, or at any time afterwards. If any of these trigger conditions are met, the default EAGO upper problem runs a local NLP solve.

The important fields to update in the upper_problem! are the _upper_objective_value and _upper_feasibility fields. If _upper_objective_value is not updated, the upper bound in the branch-and-bound algorithm will not update and the problem will not converge. If _upper_feasibility is not set to true, then any changes made to _upper_objective_value will not be updated for each node and the problem will not converge. A minimum functional (though not useful) upper problem extension is as follows:

import EAGO: upper_problem!
function upper_problem!(t::MyNewStruct, x::EAGO.GlobalOptimizer)
    x._upper_objective_value = Inf
    x._upper_feasibility = true
end

This example upper problem will set the upper bound on the objective value to Inf for each node. Given that no useful information is provided here, we could also have set x_upper_feasibility to false (or equivalently, remove the line where we set it to true), and the global upper bound would never be updated.

Note that if the _upper_objective_value is changed elsewhere, such as in the definition for the lower_problem!, the _upper_feasibility flag must be set to true. If this is not done, the change to the _upper_objective_value will be discarded.

5) Convergence check

By default, EAGO checks to see if the lower and upper bounds have converged to within either the absolute or relative tolerance. This method of checking convergence may not be desired if, for example, only the absolute tolerance is relevant, and you want to ensure that the program does not end prematurely due to a relative tolerance limit being reached. The fields to check are _lower_objective_value and _upper_objective_value for the best-identified global lower and upper bounds, respectively. This function should return true if the lower and upper bounds have converged, and false otherwise. An example of how to specify that the convergence check only use the absolute tolerance is as follows:

import EAGO: convergence_check
function EAGO.convergence_check(t::MyNewStruct, x::EAGO.GlobalOptimizer)
    gap = (x._upper_objective_value - x._lower_objective_value)
    return (gap <= x._parameters.absolute_tolerance)
end

6) Postprocessing

Postprocessing is the final step before a node is branched on. By default, EAGO performs duality-based bounds tightening[2] up to an iteration limit set by dbbt_depth in the GlobalOptimizer._parameters field. The important field to update in postprocessing is _postprocess_feasibility, which must be set to true for EAGO to branch on any given node. The minimum working postprocessing function is therefore:

import EAGO: postprocess!
function EAGO.postprocess!(t::MyNewStruct, x::EAGO.GlobalOptimizer)
    x._postprocess_feasibility = true
end

If _postprocess_feasibility is not set to true, no nodes will be branched on.

7) Termination check

This is the check that occurs on each iteration of the branch-and-bound algorithm that determines whether the algorithm continues or not. By default, several conditions are checked for such as the satisfaction of absolute or relative tolerances, solution infeasibility, or other specified limits. This function returns true if any of the stopping conditions have been met, and branch-and-bound should stop, and false otherwise. The important fields to update are _end_state, which takes values of EAGO.GlobalEndState, _termination_status_code, which takes values of MathOptInterface.TerminationStatusCode, and _result_status_code, which takes values of MathOptInterface.ResultStatusCode. Combined, these fields provide information about the branch-and-bound completion status and result feasibility.

As an example, suppose we have updated the convergence_check function to only check for absolute tolerance, and based on our knowledge of the problem, this is the only condition we care about, and we know the solution will be optimal. We could then overload the termination_check function as follows:

import EAGO: termination_check
function EAGO.termination_check(t::MyNewStruct, x::EAGO.GlobalOptimizer)
    flag = EAGO.convergence_check(t, x)
    if flag
        x._end_state = EAGO.GS_OPTIMAL
        x._termination_status_code = MathOptInterface.OPTIMAL
        x._result_status_code = MathOptInterface.FEASIBLE_POINT
    end
    return flag
end

References:

Kelley, J. E. “The Cutting-Plane Method for Solving Convex Programs.” Journal of the Society for Industrial and Applied Mathematics, vol. 8, no. 4, pp. 703–12 (1960).
Tawarmalani, M., Sahinidis, N. V. "Global optimization of mixed-integer nonlinear programs: A theoretical and computational study." Math. Program., Ser. A, 99, pp. 563-591 (2004).