Parallelising the dual revised simplex method

← Back to document page

Parallelising the dual revised simplex methodJulian Hall1Qi Huangfu2Miles Lubin31School of Mathematics, University of Edinburgh2FICO3MITConvex Optimization and BeyondEdinburgh27 June 2014Parallelising the dual revised simplex method : OverviewBackgroundThree approachesMultiple iteration parallelism for general LPSingle iteration parallelism for general LPData parallelism for stochastic LPConclusionsJulian HallParallelising the dual revised simplex method2 / 42Linear programming (LP)minimizecTxsubject toAx=b x 0BackgroundFundamental model in optimaldecision-makingSolution techniques simplex method (1947) Interior point methods (1984)Large problems have 103 107/8variables 103 107/8constraintsMatrixAis (usually) sparseExampleSTAIR: 356 rows, 467 columns and 3856 nonzerosJulian HallParallelising the dual revised simplex method3 / 42Solving LP problemsminimizefP=cTxmaximizefD=bTysubj ect toAx=b x 0(P)subject toATy+s=c s 0(D)Optimality conditionsFor a partitionB Nof the variable set with nonsingularbasis matrixBinBxB+NxN=bfor (P)and[BTNT]y+[sBsN]=[cBcN]for (D)withxN=0andsB=0Primal basic variablesxBgiven by b=B 1bDual non-basic variablessNgiven by cTN=cTN cTBB 1NPartition is optim

Simplex algorithm: Each iteration RHS ba q abT p bcT N ba pq bc q bb bb N B Dual algorithm: Assume bc N 0 Seek bb 0 Scan bb i, i 2B, for a good candidate p to leave B CHUZR Scan bc j=ba pj, j 2N, for a good candidate q to leave N CHUZC Update: Exchange p and q between Band N

  Revised, Scan, Simplex, Dual, Parallelising the dual revised simplex, Parallelising