• Login
    View Item 
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    High performance computing algorithms for discrete optimization

    Thumbnail
    View/Open
    MUNGUIACONEJERO-DISSERTATION-2017.pdf (3.090Mb)
    Date
    2017-11-03
    Author
    Munguia Conejero, Lluis-Miquel M.
    Metadata
    Show full item record
    Abstract
    This thesis concerns the application of High Performance Computing to Discrete Optimization, and the development of massively parallel algorithms designed to accelerate the solving process of Mixed-Integer Programs (MIPs). We begin by presenting a portfolio of scalable parallel primal heuristics, which focus on providing the end-user with high quality feasible solutions to any MIP program quickly. In some cases, we show our algorithms to be several orders of magnitude more effective than current state-of-the-art approaches. The first of the contributions in this category is a specialized primal heuristic for the Fixed Charge Multicommodity Network Flow problem. The presented computational experiments back the superior effectiveness of our method at finding substantially better primal solutions when compared to state-of-the-art commercial MIP solvers, even when the latter are allowed five times as much time. We further generalize the introduced notions and develop Parallel Alternating Criteria Search: a general-purpose parallel primal method prepared for handling any unstructured MIP. We show how the combination of parallelism and simple large neighborhood search schemes can provide a powerful tool for generating high quality solutions for any given problem. Our parallel method is able to produce competitive or better and faster results for more than 90% of the tested instances against CPLEX. Parallel Alternating Criteria Search becomes especially useful in the context of large instances and time-sensitive optimization problems, where traditional branch-and-bound methods may not be able to provide competitive upper bounds and attaining feasibility may be challenging. The modular nature of Parallel Alternating Criteria Search can provide an excellent platform for rapid prototyping parallel domain-specific heuristics. We show this particular achievement on the Maritime Inventory Routing Problem, a complex optimization problem that combines network flows with inventory management. In the presented results, tailored versions of our parallel algorithm are able to significantly outperform domain-specific state-of-the-art heuristics and parallel MIP solvers alike. The second half of this thesis is dedicated to the introduction of PIPS-SBB, a parallel distributed-memory solver for deterministic equivalent two-stage stochastic MIPs (sMIPs). The newly introduced solver features multiple levels of nested parallelism. It is also designed with data parallelism in mind, allowing the problem data to be partitioned across multiple distributed-memory machines. We then present two Branch-and-Bound parallelizations extending the already parallel solver. We investigate the effects of leveraging multiple levels of parallelism and their part in improving the scaling performance beyond thousands of cores. We also compare our algorithms against a distributed-memory implementation of a commercial MIP solver. The latter proves to be the best performer at small problem scales. However, the specialized nature of the methods present in PIPS-SBB-based solvers allow them to be the best performers in large SMIP instances. The direct product of this thesis is a set of algorithms ready to be used in massively parallel systems to quickly find high quality solutions to any MIP problem. The presented works ultimately increase our understanding of the use of parallelism in the context of Discrete Optimization and its important part in improving the effectiveness and performance of its algorithms.
    URI
    http://hdl.handle.net/1853/60689
    Collections
    • College of Computing Theses and Dissertations [1191]
    • Georgia Tech Theses and Dissertations [23877]
    • School of Computational Science and Engineering Theses and Dissertations [100]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology