Please use this identifier to cite or link to this item:
Optimal Aggregation of Blocks into Subproblems in Linear-Programs with Block-Diagonal-Structure
|2015-08-ms-chermakani_r.pdf||Version for non-UH users. Copying/Printing is not permitted||2.55 MB||Adobe PDF||View/Open|
|2015-08-ms-chermakani_uh.pdf||For UH users only||2.56 MB||Adobe PDF||View/Open|
|Title:||Optimal Aggregation of Blocks into Subproblems in Linear-Programs with Block-Diagonal-Structure|
|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.
|Appears in Collections:||M.S. - Electrical Engineering|
Please contact firstname.lastname@example.org if you need this content in an ADA compliant alternative format.
Items in ScholarSpace are protected by copyright, with all rights reserved, unless otherwise indicated.