Please use this identifier to cite or link to this item: http://hdl.handle.net/10125/51053

Optimal Aggregation of Blocks into Subproblems in Linear-Programs with Block-Diagonal-Structure

File Description SizeFormat 
2015-08-ms-chermakani_r.pdfVersion for non-UH users. Copying/Printing is not permitted2.55 MBAdobe PDFView/Open
2015-08-ms-chermakani_uh.pdfFor UH users only2.56 MBAdobe PDFView/Open

Item Summary

Title: Optimal Aggregation of Blocks into Subproblems in Linear-Programs with Block-Diagonal-Structure
Authors: Chermakani, Deepak
Issue Date: Aug 2015
Publisher: [Honolulu] : [University of Hawaii at Manoa], [August 2015]
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: M.S. University of Hawaii at Manoa 2015.
Includes bibliographical references.
URI/DOI: http://hdl.handle.net/10125/51053
Appears in Collections:M.S. - Electrical Engineering


Please contact sspace@hawaii.edu if you need this content in an alternative format.

Items in ScholarSpace are protected by copyright, with all rights reserved, unless otherwise indicated.