Doctoral Degrees (Industrial Engineering)

Permanent URI for this collection

https://scholar.sun.ac.za/handle/10019.1/775

Browse

Browsing Doctoral Degrees (Industrial Engineering) by Author "Bennetto, Robert Andrew"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Evolutionary search strategies in constraint programming
    (Stellenbosch : Stellenbosch University, 2020-03) Bennetto, Robert Andrew; Van Vuuren, J. H.; Stellenbosch University. Faculty of Industrial Engineering. Dept. of Industrial Engineering.
    ENGLISH ABSTRACT: Successful approaches towards solving complex combinatorial optimisation problems straddle a boundary between art and science. Discrete search spaces are typically notoriously large, contain high-dimensional dependencies and usually remain intractable for large instances. Generalised mathematical relaxations that allow discrete problems to be solved in a near-trivial manner are not known. As such, researchers have focussed on approximate solution techniques, heuristics and metaheuristics for solving classes of such complex problems. Many of these techniques have forgone mathematical guarantees in favour of bio-inspired mechanisms which can produce good solutions. Constraint Programming (CP) is a discrete optimisation technique which, historically, has not received as much attention as its linear and mixed integer counterparts in the literature. CP has, however, gained popularity in recent years due to its direct modelling approach, its ability to solve a large range of medium-sized optimisation problems with complex constraints, and the maturity of the modelling language. It is advocated in this dissertation that a best-of-breed approach to combinatorial optimisation be adopted which leverages the modelling exibility of CP and evolutionary processes for searchpolicy generation as a function of the underlying abstract problem representation. Research into the algorithm selection problem which simultaneously solves the problem of generating new algorithms while allowing for selecting from an existing corpus of algorithms is limited. A literature review of the relevant solution components is provided. An incremental approach to testing these components is employed where the merits of the various algorithmic components are demonstrated, highlighting novelties in the methodology applied. Commentary on the computational performance and quality of results achieved is also provided. It is concluded that evolutionary algorithms serve as a suitable metaheuristic paradigm, capable of finding high-quality branching schemes for resolving constraint satisfaction problems more effectively than those of a benchmark algorithm. A single-objective and a multi-objective optimisation approach are tested, and it is found that the multi-objective approach facilitates the formation of higher-quality strategies during the evolutionary search process. It is further demonstrated that the search strategies uncovered not only extend their performance characteristics to unseen problem instances of the same class, but also that a deep learning model may be employed as a predictor of performance when selecting a strategy for an unseen problem instance. A commentary is provided as to likely areas of potential future work as a result of the methodology and findings of this dissertation.