Heuristic Global Optimization
Mubashsharul Islam Shafique · 2017
Global Optimization (GO) problems occur quite frequently in real-life applications, but are very hard to solve.As a result there is an ever-growing demand to find effective, fast methods for solving GO problems.The goal of this research is to develop algorithms that can quickly find good quality solutions to large-scale nonconvex GO problems, which are the hardest form of GO problems.This research develops a fast heuristic multistart algorithm for solving large-scale GO problems.The new heuristic algorithm, Constraint Consensus Global Optimizer (CCGO), has two phases: global and local.The global phase is an approximate search that quickly explores the variable space using a variety of heuristics.The local phase launches local solvers from the most promising points found in the global phase.CCGO has been specifically designed to utilize the state-of-the-art hardware systems supporting concurrency in software execution.The components of the new heuristic algorithm have been thoroughly examined via a number of experiments.The performance of the new heuristic is then studied with respect to some state of the art complete and heuristic solvers.Empirical results show that the CCGO algorithm has an edge in runtime while offering competitive solution quality.CCGO's ability to find high-quality solutions quickly makes it an attractive choice in both theory and practice: (a) practical applications that need a solution as quickly as possible can use CCGO to get one and (b) optimization solvers that want to capitalize on an early incumbent solution can use CCGO or its approximate search feature within their workflow.iii This work is dedicated to: My parents, without whom I could never be who I am today, whose innumerable contributions surround my existence My amazing family, who has been a constant source of inspiration for me, who stood beside me during all hardships My siblings, who nourished me in all possible ways My teachers, from kindergarten to university, who taught me, who were patient in the face of my stupid questions, who guided me all the way -to think precisely in this fuzzy world.iv I am grateful to my creator who has given me the opportunity to enjoy all bounties in this world.My sincere gratitude goes to all of my teachers, who have inspired me since my childhood and whose lessons have enriched my knowledge.This thesis would not have been possible without the guidance of my supervisor Professor John W. Chinneck.I am deeply indebted to him.His motivations, suggestions, thoughts, and insights enlightened my heart and brought a success to this thesis