MAiNGO
How does MAiNGO work?

MAiNGO implements a relatively basic spatial Branch-and-Bound (B&B) algorithm, enhanced with some features for range reduction and a multi-start heuristic. The basic structure of the solver is as follows (where x includes both the integer and continuous variables):

Structure.PNG

Here, f, g, and h are bounded factorable functions (also including multivariate outer functions) that can be defined by some computer code not visible to the optimizer. The objective function and the constraints can either be modelled in C++ or via ALE as described in Modeling in MAiNGO. Based on this implementation, MAiNGO will evaluate the functions to construct a directed acyclic graph represention of the model first using the MC++ library. We use automatic differentiation via FADBAD++ in order to obtain first and second derivatives of the functions and provide them to the desired local solver. Convex and concave relaxations together with their subgradients are constructed through MC++ using the McCormick theorems, where the required intervals are obtained via FILIB++. Note that in contrast to current state-of-the-art global solvers, MAiNGO does not introduce auxiliary variables when constructing the lower bounding problem synergizing with the reduced-space philosophy of modelling in MAiNGO.

Each B&B node k, defined by its lower and upper bounds on the optimization variables x, is successively handed to wrappers for lower and upper bounding that communicate with the respective subsolvers and return the respective lower (LBD) and upper (UBD) bounds, as well as the optimal solution points (see Figure above). To obtain a lower bound, a relaxation of the original problem on the current node is constructed by relaxing the integrality requirements, replacing equalities by two inequalities each, and using the relaxations of the objective function and constraints obtained from MC++. However, in general the McCormick relaxations are non-smooth, and therefore a further affine relaxation based on linearization using the subgradients at one or more linearization points xLin is conducted to obtain a linear program (LP) and thus allow the use of robust LP solvers (shown for one linearization point, but multiple points can be used in analogy):

Relaxed_LBP.PNG

If MAiNGO detects the problem to be a (mixed-integer) linear program or a (mixed-integer) quadratic program, then it simply calls an available (MI)LP or (MI)QP solver to solve the problem. Otherwise, the problem is handled as a (mixed-integer) non-linear program and the solution procedure is as follows (in the following, UBD denotes the current global upper bound on the optimal objective value, i.e., the best objective value encountered at a feasible point so far, and LBD denotes the lower bound on the optimal objective value):

  • Step 0: Preprocessing at the root node

    • a: Initialization: Upper and lower bounding solvers and the branch-and-bound tree are initialized. The initial solution value is set to infinity.

    • b: Option check: MAiNGO checks for settings consistency, e.g., if specific heuristics are compatible with specific solvers, and informs the user about possibly modified settings. MAiNGO also performs a simple evaluation of McCormick relaxations at the middle point of the domain in order to directly throw interval or McCormick exceptions before even starting any computations (e.g., in case of division by zero).

    • c: Constraint propagation (optional): If BAB_constraintPropagation is turned on, constraint propagation is executed for the root node. Since no feasible point is available yet, we set the bounds of the objective to (-infinity, infinity). If constraint propagation finds variable bounds to be inconsistent with constraints this means that the problem is infeasible and MAiNGO will terminate.

    • d: OBBT (optional): If the number of OBBT max rounds is >0, several rounds of optimization-based bound tightening are conducted (cf., e.g., Gleixner et al., J. Global Optim. 67 (2017) 731). Since up to here no feasible point is known and UBD is equal to infinity, OBBT considers feasibility only, i.e., each variable may be maximized or minimized subject to the relaxed constraints to tighten the variable bounds. If any of the LPs solved is found to be infeasible, this means that the original problem was infeasible and MAiNGO will terminate. This also applies to the other instances where OBBT is used (Steps 0e and 2). The order in which variables are selected for OBBT is chosen according to the 'greedy' heuristic described by Gleixner et al., J. Global Optim. 67 (2017) 731.
      To balance the effort spent for OBBT and the gain through tightened bounds, we implemented the 'trivial filtering' heuristic described by Gleixner et al. Thus, you can adjust the minimum OBBT improvement (in [0,1]) to determine that a certain variable should only be considered for OBBT if this could improve its bound by at least LBP_obbtMinImprovement times the width of its interval bound in the current node. While this is not as crucial at the root node, it can make a big difference when using OBBT within the B&B loop.

    • e: Multi-start (optional): If the number of maximum local searches is >0 and steps 0c-d did not prove the problem to be infeasible, several runs of local optimization will be conducted using the local NLP solver specified by UBP_solverPreprocessing. If an initial point is specified by the user as part of the problem definition, it will be checked for feasibility first, then the first local search will start from here. The next local search starts from the midpoint of the root node, while all remaining searches start from randomly generated initial points within the root node.
      By default, output is only written about these local searches when a new incumbent (i.e., best solution point so far) is found. If you want to display the results of every local solution, enable PRE_printEveryLocalSearch.
      If you wish to perform a pure multi-start you can activate option PRE_pureMultistart. Steps 0b, 0c, 0e and 1-10 are then not performed at all and in step 0a only an upper bounding solver is initialized.

    • f: Constraint propagation (optional): If BAB_constraintPropagation is turned on, constraint propagation is executed for the root node. If a feasible point is available, we set the bounds of the objective to (-infinity, solution value) and to (-infinity,infinity) otherwise.

    • g: OBBT (optional): If OBBT was conducted in 0c and a feasible point was found in 0d, one additional round of OBBT is conducted that also considers optimality in additiona to feasibility. That is, when maximizing and minimizing each variable, a constraint that the relaxed objective function be equal to or smaller than UBD is added in addition to the relaxed versions of the original constraints. Locatelli & Schoen call this step 'standard range reduction'.

  • Steps 1-10: Main B&B loop (is executed while there are still nodes left in the B&B tree, or until the limits on CPU time, B&B iterations, or maximum number of nodes in memory are reached)

    • 1: Node selection: The next node (an instance of BabNode) to be treated is selected and extracted from the B&B tree. Available heuristics for node selection include choosing the one with the lowest lower bound (default, since it guarantees convergence), as well as the oldest or newest nodes in the tree. Also, the overall LBD (i.e., lowest lower bound of nodes in the B&B tree) is updated.

    • 2: Pre-processing (constraint propagation and OBBT, optional):
      • a: If BAB_constraintPropagation is turned on, constraint propagation is executed for the current node. If a feasible point is available, we set the bounds of the objective to (-infinity, solution value) and to (-infinity,infinity) otherwise.

      • b: If BAB_alwaysSolveObbt is turned on, OBBT is conducted for the current node. If a feasible point has already been found, it considers both feasibility and optimality, otherwise it uses feasibility only. While many established global solvers (at least by default) do not perform OBBT at every node because the computational cost can get prohibitive for problems containing many variables (recall that we need to solve two additional LPs per variable), we decided to implement it since by construction the problems that MAiNGO is designed for should have relatively few variables. Here, it can pay off to set LBP_obbtMinImprovement (cf. 0c) to limit OBBT to those variables for which significant improvements can be achieved.
        If the node is proven to be infeasible during OBBT, it is fathomed by infeasibility and thus simply discarded (i.e., we go back directly to 10 and then back to 1).

    • 3: Lower bounding: The lower bounding problem (LBP) is solved for the current node using one of the LBP solvers. If the LP is infeasible, the node is fathomed by infeasibility and thus, simply discarded (i.e., we go directly to 10 and then back to 1). Otherwise, if the computed lower bound is greater than the current incumbent UBD or above UBD but within tolerance, it is fathomed by value dominance and thus also discarded.

    • 4: Upper bounding: The original problem (UBP) is solved using the local NLP solver specified by UBP_solverBab. If available, the LBP solution point is used as an initial point. Otherwise, the center of the current node is used.
      The solution point returned by the NLP solver is checked for feasibility within the user-specified feasibility tolerances (deltaIneq, deltaEq) regardless of the return code of the NLP solver. If using binary variables, these are checked for integrality. If no NLP solver is used, a single function evaluation is conducted and feasibility is checked at the LBP solution point or the node center.
      If a feasible point was found this way, it is compared to UBD and if it is better, it is stored as the new incumbent and it is represented by an asterisk '*' in the B&B output. The asterisk is only shown if the new incumbent is at significantly better, i.e., is not within optimality tolerances of the previous best upper bound. In this case, all nodes in the B&B tree (possibly including the current one) with a (node) lower bound greater than this new UBD are fathomed by value dominance and thus deleted from the tree.

    • 5: Post-processing (DBBT & probing, optional): If duality-based bound tightening (DBBT) is activated, (cf. Ryoo & Sahinidis, J. Global Optim. 8 (1996) 107), we exploit dual information from the LBP solution to tighten bounds based on optimality. This only works if the LBP solution lies at a bound of the current node, and if the dual multipliers for this variable bound were successfully extracted from the underlying (MI)LP solver.
      If Probing is enabled, the remaining bounds can be treated as well by tentatively fixing the respective variable at the bound and re-solving the LBP. However, experience suggests that this often too expensive (at least in the current implementation that blindly applies this to all variables).

    • 6: Process the incumbent information: If a new incumbent has been found, the ID of the node holding the incumbent is updated. This is mainly done to enable tracking of the incumbent in the B&B algorithm.

    • 7: Branching: Two new nodes are created and inserted into the B&B tree. Options for selecting the variable to branch on include choosing the one with the largest diameter or with the largest diameter relative to the original one (i.e., the one specified by the user). Once the branching variable has been determined, the point to branch at is chosen as a convex combination between the LBP solution point and the node center. Currently, we always branch in the middle of the interval (this is due to initial testing which gave best results when branching in the middle). If the selected branching variable is binary, the floor or ceil functions are used to push the bounds of the child nodes to the respective integer values.

    • 8: Heuristic checks: Currently, it is only checked whether additional scaling in the lower bounding solver is needed. If the lower bound does not improve for a given number of iterations, we activate aggressive scaling in the lower bounding solver. It is planned to perform additional checks in this step in the future.

    • 9: Updating statistics: All information regarding number of iterations, solved upper and lower bounding problems etc. are augmented.

    • 10: Output: If B&B verbosity is set to anything other than VERB_NONE, output on the solution progress will be printed every BAB_printFreq nodes. Additionally, output will be printed whenever a new incumbent is found (marked by an asterisk in the first column). Note that LBP_verbosity and UBP_verbosity should only be changed from their default ( VERB_NONE ) for diagnostic reasons since they are very noisy (so is VERB_ALL for BAB_verbosity). By default, the printed output includes:
      • the ID of the node treated
      • the lower bound of the node (after solving the LBP, i.e., not the one inherited from the parent node)
      • the overall LBD before treating the current node
      • the current UBD after treating the current node
      • the number of nodes currently in the B&B tree
      • the absolute difference between UBP and LBP
      • the relative gap between UBP and LBP
      • the CPU time spent so far

  • Step 11: Final Output
    • The incumbent as well as its objective value are returned (if a feasible point has been found) along with a message stating the termination status. Note that the returned solution only corresponds to the global solution if MAiNGO reports regular termination. If it terminated because of surpassed CPU time or node limits, the solution may not even be a local optimum. If it reports the problem to be infeasible, this means it was actually proven to be infeasible through the LBPs and/or range reduction.
    • Statistics are also given on the total number of nodes treated, the number of LBPs solved, the number of UBPs solved, and the maximum number of nodes held in memory at any point during solution. This values can differ since for a node that is found infeasible during OBBT, neither LBP nor UBP will be solved. If a node is found infeasible during LBP, UBP is omitted.
    • If additional output variables were specified as part of the problem definition, the value of these variables will be calculated at the solution point and reported at the very end of the solution.
    • If writeLog is enabled, a log file is now written in the background that contains the same content as the screen output, except that the print frequency may be different (set through BAB_logFreq). Currently, the log file will be written in the working directory and is named bab.log.
    • If writeResFile is enabled, a result file is written after a regular termination of the optimization process. The result file contains the value of all variables, the objective and all constraints at the final solution point. A result file is only written if the problem is feasible.
    • Finally, the overall CPU time is reported.

Lower Bounding Solvers

MAiNGO currently supports four different lower bounding solvers, namely a MAiNGO internal solver, a solver based on interval arithmetics only, CLP and CPLEX. The MAiNGO internal solver relaxes constraints via natural interval extensions, linearizes the McCormick relaxations of the objective function at the mid point and then solves this very simple linear program. The interval-based solver uses interval arithmetics only in order to solve the lower bounding problem. Both solvers, MAiNGO and interval-based do not support OBBT or multiple-point linearization strategies. CPLEX is the third supported lower bounding solver and supports the full range of options implemented in MAiNGO. Note that the current version of CPLEX cannot work with values >1e19. This is automatically detected within MAiNGO and handled appropriately. CLP is the fourth supported lower bounding solver and supports the full range of options implemented in MAiNGO. Note that while CLP may be faster for small problems than CPLEX, it is more error-prone (all errors are caught by MAiNGO and handled properly). It is recommended to use CPLEX as lower bounding solver to achieve best computational results.

Upper Bounding Solvers

MAiNGO currently supports local solvers found in the NLopt package, IPOPT and Knitro. Additionally, you can optimize without any local solver by the use of simple function evaluations. IPOPT is an interior point optimizer. The NLopt package provides the two derivative free solvers Cobyla and Bobyqa and two gradient-based solvers LBFGS and SLSQP. Knitro is a commercial local (MI)NLP solver consisting of many different algorithms. For additional information, visit https://projects.coin-or.org/Ipopt , https://nlopt.readthedocs.io/en/latest/ and https://www.artelys.com/docs/knitro/2_userGuide/feasibility.html .