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.
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:
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:
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.
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
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.
By default, EAGO applies Kelley's cutting-plane algorithm 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_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
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
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
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_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
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
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
_upper_feasibility flag must be set to
true. If this is not done, the change to the
_upper_objective_value will be discarded.
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
_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)
Postprocessing is the final step before a node is branched on. By default, EAGO performs duality-based bounds tightening 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
_postprocess_feasibility is not set to
true, no nodes will be branched on.
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
_termination_status_code, which takes values of
_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)
x._end_state = EAGO.GS_OPTIMAL
x._termination_status_code = MathOptInterface.OPTIMAL
x._result_status_code = MathOptInterface.FEASIBLE_POINT
- 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).