More Web Proxy on the site http://driver.im/

article

Free access

Distributed nested decomposition of staircase linear programs

Editor: Ronald Boisvert Authors:

R. P. SundarrajAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 23, Issue 2

Pages 148 - 173

https://doi.org/10.1145/264029.264031

Published: 01 June 1997 Publication History

Abstract

This article considers the application of a primal nested-decomposition method to solve staircase linear programs (SLPs) on distributed-memory, multiple-instruction-multiple-data computers. Due to the coupling that exists among the stages of an SLP, a standard parallel-decompositon algorithm for these problems would allow only a subset of the subproblem processes to overlap with one another at any give time. We propose algorithms that seek to increase the amount of overlap among the processes as well as utilize idle time beneficially. Computational results testing the effectiveness of our algoritms are reported, using a standard set of test problems.

References

[1]

BARR, R. S. AND HICKMAN, B. 1993. Reporting computational experiments with parallel algorithms: Issues, measures and experts' opintions. ORSA J. Comput. 5, 1, 2-18.

[2]

BONNIGER, T., ESSER, R., AND KREKEL, D. 1995. CM-5E, KSR2, Paragon XP/S: A comparative description of massively parallel computers. Parallel Comput. 21, 2 (Feb.), 199-232.

[3]

DANTZIG, a. B. AND WOLFE, P. 1960. The decomposition principle for linear programs. Oper. Res. 8, 101-111.

[4]

ENTRIKEN, R. 1989. The parallel decomposition principle of linear programs. Ph.D dissertation, Stanford Univ., Stanford, Calif.

[5]

FORREST, J. J. g. AND TOMLIN, J.A. 1990. Vector processing in simplex and interior methods for linear programming. Ann. Oper. Res. 22, 1-4 (Jan.), 71-100.

[6]

FOURER, R. 1979. Solving staircase linear programs by simplex method, 1: Inversion. Ph.D dissertation, Stanford Univ., Stanford, Calif.

[7]

GAY, D. 1985. Electronic mail distribution of linear programming test problems. COAL Newslett. 13, 10-12.

[8]

GLASSEY, R.C. 1973. Nested decomposition of multi-stage linear programs. Manage. Sci. 20, 282-292.

[9]

GNANENDRAN, S. K. AND go, J. K. 1993. Load balancing in the parallel optimization of block-angular linear programs. Math. Program. 62, 1 (Oct. 21) 41-67.

[10]

Ho, J.K. 1976. Implementation and application of a nested decomposition algorithm. In Proceedings of the Bicentennial Conference on Mathematical Programming (Gaithersburg, Md.), 21-30.

[11]

Ho, J. K. 1980. A successive linear optimization approach to the dynamic traffic assignment problem. Transp. Sci. 14, 295-305.

[12]

Ho, J. K. AND LOUTE, E. 1980. A set of staircase linear programming test problems. Math. Program. 20, 245-250.

[13]

Ho, J. K. AND MANNE, A. S. 1974. Nested decomposition of dynamic models. Math. Program. 6, 121-140.

[14]

Ho, J. K. AND SUNDARRAJ, R.P. 1993. A timing model for the revised simplex method. Oper. Res. Lett. 13, 67-73.

[15]

Ho, J. K. AND SUNDARRAJ, R.P. 1994. On the efficacy of distributed simplex algorithms for linear programming. Comput. Optim. Appl. 3, 4 (Oct.), 349-363.

[16]

Ho, J. K., LEE, T. C., AND SUNDARRAJ, R.P. 1988. Decomposition of linear programs using parallel computation. Math. Program. 42, 2 (Feb. 1), 391-405.

[17]

KARP, A.g. 1987. Programming for parallelism. Computer 20, 5 (May), 43-57.

[18]

MAIER, R. 1989. Parallel solution of large-scale structured optimization problems. Ph.D dissertation, Univ. of Minnesota, Minneapolis, Minn.

[19]

MEDHI, D. 1990. Parallel bundle-based decomposition for large-scale structured mathematical programming problems. Ann. Oper. Res. 22, 1-4 (Jan.), 101-127.

[20]

MURTAGH, B. AND SAUNDERS, M. 1983. MINOS 5.1 user's guide. Rev. ed. Rep. SOL 83-2OR. Dept. of Operations Research, Stanford Univ., Stanford, Calif.

[21]

NEVES, K. W. 1984. Vectorization of scientific software. In High Speed Computations. NATO ASI Series, vol. 7. Springer-Verlag, Berlin, 277-291.

[22]

ROSEN, J.B. 1964. Primal partitioning programming for block diagonal matrices. Numer. Math. 6, 250-260.

[23]

ROSEN, J. B. AND MAIER, R.S. 1990. Parallel solution of large-scale, block-angular linear programs. Ann. Oper. Res. 22, 1-4 (Jan.) 23-41.

[24]

TOMLIN, J.A. 1973. LPMluser's guide. Systems Optimization Laboratory, Stanford Univ., Stanford, Calif. Unpublished.

Cited By

Wilczyński AJakóbik (Krok) AJakóbik (Krok) AKołodziej J(2016)Stackelberg Security Games: Models, Applications and Computational AspectsJournal of Telecommunications and Information Technology10.26636/jtit.2016.3.7493:2016(70-79)Online publication date: 30-Sep-2016
https://doi.org/10.26636/jtit.2016.3.749
Ho J(2016)Large-Scale SystemsEncyclopedia of Operations Research and Management Science10.1007/978-1-4419-1153-7_518(864-867)Online publication date: 23-Jan-2016
https://doi.org/10.1007/978-1-4419-1153-7_518
Ederer TLorenz UMartin AWolf J(2011)Quantified linear programsProceedings of the 19th European conference on Algorithms10.5555/2040572.2040596(203-214)Online publication date: 5-Sep-2011
https://dl.acm.org/doi/10.5555/2040572.2040596
Show More Cited By

Index Terms

Distributed nested decomposition of staircase linear programs

Recommendations

A balanced nested-decomposition algorithm for staircase linear programs
Revised dantzig-wolfe decomposition for staircase-structured linear programs

Staircase structured linear programs arise naturally in the study of engineering economic systems. One general approach to solving such LP's is the technique of nested decomposition of the primal or dual problem. The research described in this paper ...
Advances in a nested decomposition algorithm for solving staircase linear programs

Reviews

Reviewer: Sven-Ake Gustafson

In this research paper, the authors investigate various methods of exploiting the special structure of staircase linear programs to achieve rapid computational treatment. They consider parallel processing and give some theoretical results on achievable speedups and efficiencies. They report the results of extensive computational experiments. They have treated a set of test problems that are available from Netlib. Although the paper is generally well written, the many acronyms used are burdensome. The experimental results are lucidly presented in tables and graphs. The authors' analysis of the observed results is thorough and interesting. The references are comprehensive and up to date.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 23, Issue 2

June 1997

163 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/264029

Editor:
Ronald Boisvert
National Institute of Standards and Technology, Gaithersburg, MD

Issue’s Table of Contents

Copyright © 1997 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1997

Published in TOMS Volume 23, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
489
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)6

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wilczyński AJakóbik (Krok) AJakóbik (Krok) AKołodziej J(2016)Stackelberg Security Games: Models, Applications and Computational AspectsJournal of Telecommunications and Information Technology10.26636/jtit.2016.3.7493:2016(70-79)Online publication date: 30-Sep-2016
https://doi.org/10.26636/jtit.2016.3.749
Ho J(2016)Large-Scale SystemsEncyclopedia of Operations Research and Management Science10.1007/978-1-4419-1153-7_518(864-867)Online publication date: 23-Jan-2016
https://doi.org/10.1007/978-1-4419-1153-7_518
Ederer TLorenz UMartin AWolf J(2011)Quantified linear programsProceedings of the 19th European conference on Algorithms10.5555/2040572.2040596(203-214)Online publication date: 5-Sep-2011
https://dl.acm.org/doi/10.5555/2040572.2040596
Ederer TLorenz UMartin AWolf J(2011)Quantified Linear Programs: A Computational StudyAlgorithms – ESA 201110.1007/978-3-642-23719-5_18(203-214)Online publication date: 2011
https://doi.org/10.1007/978-3-642-23719-5_18
Gnanendran KSundarraj R(2006)Alternative model representations and computing capacityDecision Support Systems10.1016/j.dss.2005.11.00842:3(1413-1430)Online publication date: 1-Dec-2006
https://dl.acm.org/doi/10.1016/j.dss.2005.11.008
Ho J(2005)Large-scale systemsEncyclopedia of Operations Research and Management Science10.1007/1-4020-0611-X_518(440-442)Online publication date: 25-Oct-2005
https://doi.org/10.1007/1-4020-0611-X_518

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents