Abstract
Restricted simplicial decomposition (RSD) is a very useful technique for certain large-scale pseudoconvex programming problems such as the traffic assignment problem and other network flow problems. The “restricted” version of this method allows the user to treat the maximum size of the generated simplices as a parameter. When the parameter is at its minimum value, the method reduces to the Frank-Wolfe algorithm; when at its maximum, the original simplicial decomposition of von Hohenbalken and Holloway results. Computer storage requirements increase linearly with the parameter, but our computational experiments on a variety of test problems show that there is a payoff in improved progress of the method as measured by the relative error in the objective function. Included in the tests are a number of real-world traffic networks, some large electrical networks, a water distribution network, and linearly constrained problems of the Colville study.
Conditions are given for which RSD converges after a finite number of major cycles, and variations of RSD which have potential for real-world applications are developed. These include a quadratic approximation of the master problem and an extension to include the case of unbounded subproblems.
This research was supported in part by NSF Grants ECE-8420830 and ECS-8516365.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
I. Balberg and N. Binnebaum, “Computer study of the percolation threshold in a two-dimensional anisotropic system of conducting sticks,” PHYSICAL REVIEW B 28 (1983) 3799–3812.
I. Balberg, N. Binnebaum and C.H. Anderson, “Critical behavior of the two-dimensional sticks system,” Physical Review Letters 51 (1983) 1605–1608.
M.S. Bazaraa and C.M. Shetty, Nonlinear Programming (John Wiley and Sons, NY, 1979).
P. Beck, L. Lasdon and M. Engquist, “A reduced gradient algorithm for nonlinear network problems,” ACM Transaction on Mathematical Software 9 (1983) 57–70.
D.P. Bertsekas, “Algorithms for nonlinear multicommodity network flow problems,” in: Benseussan and Lions, eds., International Symposium on Systems Optimization and Analysis (Springer-Verlag, NY, 1979) pp. 210–224.
D.P. Bertsekas, “Projected Newton methods for optimization problems with simple constraints,” SIAM Journal of Control and Optimization 20 (1982) 221–246.
G. Bradley, G. Brown, G. Graves, “Design and implementation of large scale primal transshipment algorithms,” Management Science 24 (1977) 1–35.
D.G. Cantor and M. Gerla, “Optimal routing in a packet-switched computer network,” IEEE Transaction on Computers C-23 (1974) 1062–1069.
M. Collins, L. Cooper, R. Helgason, J. Kennington and L. LeBlanc, “Solving the pipe network analysis problem using optimization techniques,” Management Science 24 (1978) 747–760.
A.R. Colville, “A comparative study on nonlinear programming codes,” Technical Report No. 320-2949, IBM-Data Processing Division, New York Scientific Center (New York, NY, 1968).
L. Cooper and J. Kennington, “Steady state analysis of nonlinear resistive electrical networks using optimization techniques,” Technical Report, IEOR 77012, Southern methodist University (Dallas, Texas, 1977).
R.S. Dembo and J.G. Klincewicz, “A scaled reduced gradient algorithm for network flow problems with convex separable costs,” Mathematical Programming Study 15 (1981) 124–147.
R.S. Dembo and U. Tulowitzki, “Computing equilibria on large multicommodity networks; an application of truncated quadratic programming algorithms,” SOM working Paper Series B #65, School of Organization and Management, Yale University (New Haven, Connecticut, 1983).
M. Frank and P. Wolfe, “An algorithm for quadratic programming,” Naval Research Logistics Quarterly 3 (1956) 95–110.
A.M. Geoffrion, “Elements of large-scale mathematical programming,” Management Science 16 (1970) 652–691.
P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, “User’s guide for SOL/NPSOL: A Fortran package for nonlinear programming,” Report SOL 83-12, Department of Operations Research, Stanford University (California, 1983).
M.D. Grigoriadis and T. Hsu, “RNET: The Rutgers minimum cost network flow subroutine,” SIGMAP Bulletin (1979) 17–18.
J. Guélat, “Algorithmes pour le probleme d’affectation du traffic d’equilibre avec demandes fixes: Comparasons,” Publication 299, Centre de Recherche sur les Transports, Universite de Montreal (Montreal, 1983).
D.W. Hearn, “The gap function of a convex program,” Operations Research Letters 1 (1982) 67–71.
D.W. Hearn, S. Lawphongpanich and J.A. Ventura, “Finiteness in restricted simplicial decomposition,” Operations Research Letters 4 (1985) 125–130.
M. Held, P. Wolfe and H. Crowder, “Validation of subgradient optimization,” Mathematical Programming 6 (1974) 62–88.
D.M. Himmelblau, Applied Nonlinear Programming (McGraw-Hill, New York, 1972).
C.A. Holloway, “An extension of the Frank-Wolfe method of feasible directions,” Mathematical Programming 6 (1974) 14–27.
P.V. Kamesam and R.R. Meyer, “Multipoint methods for nonlinear networks,” Computer Sciences Technical Report #468, Computer Sciences Department, University of Wisconsin (Madison, Wisconsin, 1982).
J.L. Kennington, private communication (1984).
J.L. Kennington and R.V. Helgason, Algorithms for Network Programming (John Wiley and Sons, New York, 1980).
J.G. klincewicz, “A Newton method for convex separable network flow problems,” Networks 13 (1983). 427–442.
S. Lawphongpanich and D.W. Hearn, “Restricted simplicial decomposition with application to the traffic assignment problem,” Research Report No. 83-8, University of Florida (Gainesville, Florida, 1983).
E.S. Levitin and B.T. Polyak, “Constrained minimization problems,” USSR Computational mathematics and Mathematical Physics 6 (1966) 1–50.
S. Nguyen, “A unified approach to equilibrium methods for traffic assignment,” in: M.A. Florian, ed., Traffic Equilibrium Methods (Springer-Verlag, New York, 1976), pp. 148–182.
S. Nguyen and C. Dupuis, “An efficient method for computing traffic equilibria in a network with asymmetric transportation costs,” Transportation Science 18 (1984) 185–202.
S. Nguyen and L. James, “TRAFFIC—An equilbrium traffic assignment program,” Report 17, Centre de Recherche sur les Transport, Universite de Montreal (Montreal, 1975).
R.T. Rockafellar, Convex analysis (Princeton University Press, NJ, 1970).
K. Schittkowski, “NLPQL: A FORTRAN subroutine for solving constrained nonlinear programming problems,” Report, Institut für Informatik, Universität Stuttgart (Stuttgart, Germany, 1984).
P.A. Steenbrink, Optimization of Transport Networks (John Wiley and Sons, NY, 1974).
M.M. Syslo, N. Deo and J.S. Kowalik, Discrete Optimization Algorithms with Pascal Programs (Prentice-Hall, NJ, 1983).
J.A. Ventura and D.W. Hearn, “Computing the effective resistance in a system of conducting sticks,” Research Report No. 84-43, University of Florida (Gainesville, Florida, 1984).
B. Von Hohenbalken, “A finite algorithm to maximize certain pseudoconcave functions on polytopes,” Mathematical Programming 8 (1975) 189–206.
B. Von Hohenbalken, “Simplicial decomposition in nonlinear programming algorithms,” Mathematical Programming 13 (1977) 49–68.
P. Wolfe, “Convergence theory in nonlinear programming,” in: J. Abadie, ed., Integer and Nonlinear Programming (North-Holland, New York, 1970) pp. 1–36.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1987 The Mathematical Programming Society, Inc.
About this chapter
Cite this chapter
Hearn, D.W., Lawphongpanich, S., Ventura, J. (1987). Restricted simplicial decomposition: Computation and extensions. In: Hoffman, K.L., Jackson, R.H.F., Telgen, J. (eds) Computation Mathematical Programming. Mathematical Programming Studies, vol 31. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0121181
Download citation
DOI: https://doi.org/10.1007/BFb0121181
Received:
Revised:
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00932-7
Online ISBN: 978-3-642-00933-4
eBook Packages: Springer Book Archive