Optimal Aggregation of Blocks into Subproblems in Linear-Programs with Block-Diagonal-Structure
Date
2015-08
Authors
Contributor
Advisor
Department
Instructor
Depositor
Speaker
Researcher
Consultant
Interviewer
Narrator
Transcriber
Annotator
Journal Title
Journal ISSN
Volume Title
Publisher
University of Hawaii at Manoa
Volume
Number/Issue
Starting Page
Ending Page
Alternative Title
Abstract
In many large practical planning problems modelled as linear-programs with blockdiagonalstructure, it is desirable to minimize wall-clock-time for a solution to the entire set of diagonal blocks. When the number of available independent-processing-units is at least equal to the number of blocks, this wallclocktime is minimized by completely decomposing the linearprogram into as many smallsized subproblems as possible, each block resulting in a separate subproblem. This decomposition strategy does not necessarily work when the parallel processing capability is limited, causing multiple subproblems to be serially solved on the same processingunit. In such a situation, it might be better to aggregate blocks into larger sized subproblems. The optimal aggregation strategy depends on the computing-platform used. We show that optimal aggregation is NP-hard, when blocks are of unequal size. We also show that when blocks are of equal size, optimal aggregation can be achieved within polynomial-time. Experiments with solvers show substantial reduction of solution-times by using our optimal aggregation strategy, compared with trivial aggregation strategies. This is an important result for linear-programs that have diagonal blocks of the same size, since our approach can be used to minimize the expected solution-time of the set of subproblems in every iteration of any decomposition technique.
Description
Keywords
Citation
Extent
Format
Geographic Location
Time Period
Related To
Theses for the degree of Master of Science (University of Hawaii at Manoa). Electrical Engineering
Related To (URI)
Table of Contents
Rights
Rights Holder
Local Contexts
Collections
Email libraryada-l@lists.hawaii.edu if you need this content in ADA-compliant format.