Add to Google Calendar
Date:  Fri, July 24, 2015
Time:  1pm-3pm
Location:  Holmes Hall 389
Speaker:  Deepak Chermakani, candidate for MS

 Wall-clock-time for a solution is minimized, by decomposing a linear-program with block-diagonal-structure into as many small-sized subproblems as possible, each block resulting in a separate subproblem, when the number of available parallel-processing-units is at least equal to the number of blocks. This is not necessarily the case when the parallel processing capability is limited, causing multiple subproblems to be serially solved on the same processing-unit. 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 stochastic linear-programs that have similar diagonal blocks, since our approach can be used to minimize the expected solution-time to the set of blocks in every iteration of any decomposition technique.