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

Simple item page
dc.contributor.authorChermakani, Deepak
dc.date.accessioned2017-12-18T21:18:28Z
dc.date.available2017-12-18T21:18:28Z
dc.date.issued2015-08
dc.description.abstractIn 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.
dc.description.degreeM.S.
dc.identifier.urihttp://hdl.handle.net/10125/51053
dc.languageeng
dc.publisherUniversity of Hawaii at Manoa
dc.relationTheses for the degree of Master of Science (University of Hawaii at Manoa). Electrical Engineering
dc.titleOptimal Aggregation of Blocks into Subproblems in Linear-Programs with Block-Diagonal-Structure
dc.typeThesis
dc.type.dcmiText

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
2015-08-ms-chermakani_r.pdf
Size:
2.49 MB
Format:
Adobe Portable Document Format
Description:
Version for non-UH users. Copying/Printing is not permitted
Download
No Thumbnail Available
Name:
2015-08-ms-chermakani_uh.pdf
Size:
2.5 MB
Format:
Adobe Portable Document Format
Description:
For UH users only
Download

Collections

M.S. - Electrical Engineering