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

File Description SizeFormat 
Kazazakis-N-2017-PhD-Thesis.pdfThesis2.97 MBAdobe PDFView/Open
Title: Parallel computing, interval derivative methods, heuristic algorithms, and their implementation in a numerical solver, for deterministic global optimization
Authors: Kazazakis, Nikolaos
Item Type: Thesis or dissertation
Abstract: 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.
Content Version: Open Access
Issue Date: Aug-2016
Date Awarded: Mar-2017
Supervisor: Adjiman, Claire
Sponsor/Funder: Engineering and Physical Sciences Research Council
Funder's Grant Number: EP/J003840/1
Department: Chemical Engineering
Publisher: Imperial College London
Qualification Level: Doctoral
Qualification Name: Doctor of Philosophy (PhD)
Appears in Collections:Chemical Engineering PhD theses

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commons