Computational Aspects of Discrete Optimization via Simulation with Gaussian Markov Random Fields

Semelhago, Mark

doi:https://doi.org/10.21985/n2-f1rh-h960

Work

Computational Aspects of Discrete Optimization via Simulation with Gaussian Markov Random Fields

Public

Download PDF

Download All Files (.zip)

Optimization via simulation (OvS) is the practice of minimizing or maximizing the expected value of the output of a stochastic simulation model with respect to controllable decision variables. Stochastic simulation is a standard tool within operations research and is often required to model complex systems subject to uncertainty where it is impossible to analytically describe quantities of interest in the system. The scope of this dissertation is discrete OvS (DOvS) problems, where decision variables assume integer-ordered values. Specifically, focus is on improving an already existing algorithm, the Gaussian Markov Improvement Algorithm (GMIA). GMIA is a DOvS algorithm that uses a Gaussian Markov random field (GMRF), a type of discrete Gaussian process, as a metamodel to represent the unknown output of the simulation at different feasible solutions. Further, GMIA uses a modified expected improvement criterion, known as complete expected improvement (CEI), to guide search and simulation and to give an estimate as to the optimality gap at termination. While GMIA has many desirable properties, when the number of feasible solutions grows substantially, computational overhead at each iteration of GMIA grows large and can overtake the effort required in simulating feasible solutions. Much of this overhead involves computing necessary parameters of the joint distribution to be able to calculate the CEI at every feasible solution. The first project of this thesis illustrates the power in leveraging sparse linear algebra techniques to make computation of the joint distribution parameters more efficient. This allows GMIA to solve problems more efficiently and makes solving problems with large feasible regions possible. The second project begins by making the conjecture that, for problems with large feasible regions, many solutions will be of poor quality. As a result, considering such solutions as candidates to be simulated every iteration is wasteful since this involves computing CEI values of these solutions. With this in mind, the second project introduces the Rapid Gaussian Markov Improvement Algorithm (rGMIA). Central to rGMIA is the idea of search sets, which are sets of solutions that are extremely small in size, relative to the entire feasible region. For a large number of iterations, search and simulation are restricted to a search set (rapid search) and CEI values are only computed for these solutions. New search sets are constructed infrequently (global search) and consist of promising solutions; solutions are evaluated based on their CEI values. rGMIA results in far more rapid iterations, compared to GMIA, while preserving GMIA's the convergence guarantee. The final project of this dissertation introduces the q-point complete expected improvement (q-CEI) criterion. With the proliferation of parallel processing, the ability to simulate multiple solutions simultaneously is now common in stochastic simulation literature. It is natural, therefore, to require a criterion that considers the joint effect when considering which solutions should be simulated. Consideration of this joint effect results in an improved quality of search. Furthermore, the last chapter presents GMIA and rGMIA in a new object-oriented programming (OOP) framework that results in code that can be more easily interpreted, extended and maintained.

Creator