A parallel decomposition algorithm for staircase linear programs
Stanford University, Dept. of Operations Research, Systems Optimization Laboratory, 1988 - Mathematics - 20 pages
A simple diet planning problem is used to demonstrate the principles of the algorithm's development and performance. When applied to this problem, the parallel decomposition algorithm shows promise relative to present serial optimization codes. The nonlinear optimization code MINOS 5.1 is used both as a basis for comparison and as a generic subproblem solver. The greatest room for speedup is in exploiting problem structures. The results show that decomposition can improve efficiency even with a single processor. Examples are given where multiple processors lead to still greater efficiency."
What people are saying - Write a review
We haven't found any reviews in the usual places.
Add Constraint ALGORITHM FOR STAIRCASE Benders decomposition code MINOS 5.1 collection of variables computer architecture constraints corresponding DAY1 DAY2 deadlock Department of Operations DIET1 DIET2 distributed-memory dual extreme points dual feasible dual solutions dual variables entire SLP equilibrium exploiting problem structures finishes unbounded implementation last subproblem loop minimize cfxi subject minimize cTx multiprocessor n-period SLP National Security Agency nonzero coefficients number of iterations number of processors number of subproblems One-Day Diet Problem Operations Research Stanford optimal selection optimal solution optimization code MINOS parallel algorithm parallel computer parallel decomposition algorithm pend queue primal and dual primal feasible reformulating run queue Sequent Balance 8000 set to zero simplex method single processor sleep queue solution is found SOLVE step Staircase Linear Programs Stanford University Sub INF UNB subproblem dimension subproblem solution subproblems are solved three subproblems three-day diet problem totals two-period SLP U.S. Air Force U.S. Department unbounded solution WAIT FOR MESSAGE