Transcription of Parallelising the dual revised simplex method
{{id}} {{{paragraph}}}
Example: marketing
Parallelising the dual revised simplex method
Parallelising the dual revised simplex methodJulian Hall1Qi Huangfu2 Miles Lubin31 School of Mathematics, University of Edinburgh2 FICO3 MITC onvex Optimization and BeyondEdinburgh27 June 2014 Parallelising 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 / 42 Linear programming (LP)minimizecTxsubject toAx=b x 0 BackgroundFundamental 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 / 42 Solving 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=0 Primal basic variablesxBgiven by b=B 1bDual non-basic variablessNgiven by cTN=cTN cTBB 1 NPartiti
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
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document:
Related search queries
1149.1 Boundary-Scan Standard, Revised, Scan, ENHANCEMENTS, Boundary Scan Tutorial, SUPPLY CHAIN ENHANCEMENTS, 2011 Edition, Content Map For Career & Technology, Content Map For Technology Career, Implementation of a continuous scanning, Parallelising the dual revised simplex, NON-EXEMPTIBLE CRIMES, California, NON-EXEMPTIBLE CRIMES Revised, CLUSTERING WITH RESAMPLING AND CONSIDERATIONS ON TUNING