Abstract
This paper presents the use of surrogate constraints and Lagrange multipliers to generate advanced starting solutions to constrained network problems. The surrogate constraint approach is used to generate a singly constrained network problem which is solved using the algorithm of Glover, Karney, Klingman and Russell [13]. In addition, we test the use of the Lagrangian function to generate advanced starting solutions. In the Lagrangian approach, the subproblems are capacitated network problems which can be solved using very efficient algorithms.
The surrogate constraint approach is implemented using the multiplier update procedure of Held, Wolfe and Crowder [16]. The procedure is modified to include a search in a single direction to prevent periodic regression of the solution. We also introduce a reoptimization procedure which allows the solution from thekth subproblem to be used as the starting point for the next surrogate problem for which it is infeasible once the new surrogate constraint is adjoined.
The algorithms are tested under a variety of conditions including: large-scale problems, number and structure of the non-network constraints, and the density of the non-network constraint coefficients.
The testing clearly demonstrates that both the surrogate constraint and Langrange multipliers generate advanced starting solutions which greatly improve the computational effort required to generate an optimal solution to the constrained network problem. The testing demonstrates that the extra effort required to solve the singly constrained network subproblems of the surrogate constraints approach yields an improved advanced starting point as compared to the Lagrangian approach. It is further demonstrated that both of the relaxation approaches are much more computationally efficient than solving the problem from the beginning with a linear programming algorithm.
Similar content being viewed by others
References
A.I. Ali, R. Helgason, J. Kennington and H. Lall, Primal-simplex network codes: State-of-the-art implementation technology, Networks 8(1978)315.
R.S. Barr, K. Farhangian and J. Kennington, Networks with side constraints: An LU factorization update, Ann. Soc. Logistics Engineers 1(1986)66.
R.S. Barr, F. Glover and D. Klingman, An improved version of the out-of-kilter method and a comparative study of computer codes, Math. Progr. 7(1974)60.
M.S. Bazaraa and J.J. Goode, A survey of various tactics for generating Lagrangian multipliers in the context of Lagrangian duality, Eur. J. Oper. Res. 3(1979)322.
S. Chen and R. Saigal, A primal algorithm for solving a capacitated network flow problem with additional linear constraints, Networks 7(1977)59.
M.E. Dyer, Calculating surrogate constraints, Math. Progr. 19(1980)255.
M.L. Fisher, An application oriented guide to Lagrangian relaxation, Interfaces 15(1985)10.
B. Gavish and H. Pirkul, Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. Math. Progr. 31(1985)78.
A.M. Geoffrion, Duality in nonlinear programming: A simplified applications-oriented development, in:Perspectives on Optimization, ed. A.M. Geoffrion (Addison-Wesley, Reading, Massachusetts, 1972).
A.M. Geoffrion, Lagrangian relaxation for integer programming, Math. Progr. Study 2 (1974) 82.
F. Glover, A multiphase dual algorithm for the zero-one integer programming problem, Oper. Res. 13(1965)879.
F. Glover, Surrogate constraint duality in mathematical programming, Oper. Res. 23 (1975) 434.
F. Glover, D. Karney, D. Klingman and R. Russell, Solving singly constrained transshipment problems, Trans. Sci. 12(1978)277.
F. Glover and D. Klingman, The simplex SON algorithm for LP/embedded network problems, Math. Progr. Study 15(1981)148.
H.J. Greenberg and W.P. Pierskalla, Surrogate mathematical programming, Oper. Res. 18 (1970)1138.
M. Held, P. Wolfe and P. Crowder, Validation of subgradient optimization, Math. Progr. 6(1974)62.
IBM Mathematical Programming System Extended/370, Program 5740-XM3 (IBM Corporation, White Plains, New York, 1979).
E. Johnson, Networks and basic solutions, Oper. Res. 14(1966)191.
M.H. Karwan and R.L. Rardin, Surrogate dual multiplier search procedures in integer programming, Oper. Res. 32(1984)52.
D. Klingman, A. Napier and J. Stutz, NETGEN: A program for generating large-scale capacitated assignment, transportation, and minimum cost network problems, Management Science 20(1974)814.
D.G. Luenberger,Introduction to Linear and Nonlinear Programming (Addison-Wesley, Reading, Massachusetts, 1973).
J. Sikorski, Quasi-subgradient algorithms for calculating surrogate constraints, in:Analysis and Algorithms of Optimization Problems, Lecture Notes on Control and Information Sciences, Vol. 82 (Springer-Verlag, Berlin, 1986).
V. Srinivasan and G.L. Thompson, Benefit-cost analysis of coding techniques for the primal transportation algorithm, J. Assoc. Computing Machinery 20(1973)194.
M.A. Venkataramanan, Constrained network algorithms: Theoretical and computational aspects, Ph.D. Thesis, Texas A&M University (May 1987).
W. Zangwill,Nonlinear Programming: A Unified Approach (Prentice-Hall, Englewood Cliffs, New Jersey, 1969).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Venkataramanan, M.A., Dinkel, J.J. & Mote, J. A surrogate and Lagrangian approach to constrained network problems. Ann Oper Res 20, 283–302 (1989). https://doi.org/10.1007/BF02216933
Issue Date:
DOI: https://doi.org/10.1007/BF02216933