Parallel computing, interval derivative methods, heuristic algorithms, and their implementation in a numerical solver, for deterministic global optimization

This thesis presents new algorithms for the deterministic global optimization of general non-linear programming problems (NLPs). It is proven that the αBB general underestimator may provide exact lower bounds on a function only if rigorous conditions are satisfied. These conditions are derived and the μ-subenergy methodology is proposed to achieve tighter αBB underestimation when they are violated. An interval lower bounding test is proposed to improve αBB lower bounds and avoid expensive algorithmic steps. Piecewise-linear relaxations (PLR) are proposed for the underestimation of general functions. Calculation of these relaxations is accelerated using parallel computing. Quality bounds tightening (QBT) is proposed to reduce the cost of bounds tightening algorithms by avoiding unnecessary calculations. Violation branching is proposed to improve the performance of branching strategies by considering constraint violation when selecting a branching variable. Furthermore, a novel bounds tightening method, PLR bounds tightening (PLR-BT), is proposed. Variable-based convexity (VBC) is proposed as a general reformulation algorithm, to build tighter relaxations by exploiting underlying convexity. This work also introduces algorithms for parallel branching for the global solution of NLPs. A parallel node subdivision strategy, Multisection Branching, is proposed to achieve tighter bounds, and a parallel node selection strategy, Future Branching, is proposed to accelerate the investigation of the branch-and-bound tree. A parallel solver is presented, where MPI is used to distribute node calculations and an asynchronous bounds tightening algorithm is proposed to reduce bounds tightening wall times. This algorithm is implemented using multithreading for asynchronous feasibility-based bounds tightening (AF-BBT). All algorithms are implemented in a global solver, and its parallel architecture and features are described. This solver is used to perform numerical studies on the benefits of using the new algorithms in tandem. The new solver is benchmarked against the BARON 15.9.22 global solver for a set of problems, in which it achieves comparable performance.Open Acces