163Accesses
7Citations
Abstract
The dynamic slope scaling procedure (DSSP) is an efficient heuristic algorithm that provides good solutions to the fixed-charge transportation or network flow problem. However, the procedure is graphically motivated and appears unrelated to other optimization techniques. In this paper, we formulate the fixed-charge problem as a mathematical program with complementarity constraints (MPCC) and show that DSSP is equivalent to solving MPCC using Lagrangian relaxation with subproblem approximation.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
References
F. Al-Khayyal J.E. Falk (1983)ArticleTitleJointly constrained biconvex programmingMathematics of Operations Research8 273–286
C. Audet P. Hansen B. Jaumard G. Savard (1999)ArticleTitleA symmetrical linear maxmin approach to disjoint bilinear programmingMathematical Programming85 573–592OccurrenceHandle10.1007/s101070050072
Bai, L., Hearn, D.W. and Lawphongpanich, S. (2003), A heuristic method for the minimum toll booth problem, Technical Report, Industrial & Systems Engineering Department, University of Florida, Gainesville, Florida.
M.L. Balinski (1961)ArticleTitleFixed cost transportation problemsNaval Research Logistics Quarterly8 41–54
M.S. Bazaraa H.D. Sherali C.M. Shetty (1993) Nonlinear Programming: Theory and Algorithm Wiley New York
H.P. Benson (1985)ArticleTitleA finite algorithm for concave minimization over a polyhedronNaval Research Logistics Quarterly32 165–177
A.V. Cabot S.S. Erenguc (1984)ArticleTitleSome branch-and-bound procedure for fixed-cost transportation problemsNaval Research Logistics Quarterly31 145–154
M. Diaby (1991)ArticleTitleSuccessive linear approximation procedure for generalized fixed-charge transportation problemJournal of Operational Research Society42 991–1001
Eksioglu, S.D., Pardalos, P.M. and Romeijn, H.E. (2002), A dynamic slope scaling procedure for the fixed-charge cost multi-commodity network flow problem, in: P.M. Pardalos and V.K. Tsitsiringos (eds.),Financial Engineering, E-Commerce and Supply Chain, Kluwer Academic Publishers, pp. 247–270.
Fletcher, R., Leyffer, S., Ralph, D. and Scholtes, S. (2002), Local convergence of SQP methods for mathematical programs with equilibrium constraints, Numerical Analysis Report NA/209, Department of Mathematics, University of Dundee.
Fletcher, R. and Leyffer, S. (2002), Numerical experience with solving MPECs as NLPs, Numerical Analysis Report NA/210, Department of Mathematics, University of Dundee.
G. Gallo A. Ulkucu (1977)ArticleTitleBilinear programming: an exact algorithmMathematical Programming12 173–194OccurrenceHandle10.1007/BF01593787
J. Gauvin (1977)ArticleTitleA necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming.Mathematical Programming12 136–138OccurrenceHandle10.1007/BF01593777
D.B. Khang O. Fujiwara (1991)ArticleTitleApproximate solution of capacitated fixed-charge minimum cost network flow problemsNetworks21 689–704
D. Kim P.M. Pardalos (1999)ArticleTitleA solution approach to the fixed charge network flow problem using a dynamic slope scaling procedureOperations Research Letters24 195–203OccurrenceHandle10.1016/S0167-6377(99)00004-8
D. Kim P.M. Pardalos (2000a)ArticleTitleDynamic slope scaling and trust interval techniques for solving concave piecewise linear network flow problemsNetworks35 216–222OccurrenceHandle10.1002/(SICI)1097-0037(200005)35:3<216::AID-NET5>3.0.CO;2-E
D. Kim P.M. Pardalos (2000b)ArticleTitleA dynamic domain contraction algorithm for nonconvex piecewise linear network flow problemsJournal of Global Optimization17 225–234OccurrenceHandle10.1023/A:1026502220076
H. Konno (1976)ArticleTitleA cutting plane algorithm for solving bilinear programmingMathematical Programming11 14–27OccurrenceHandle10.1007/BF01580367
H. Kuhn W. Baumol (1962)ArticleTitleAn approximate algorithm for the fixed charge transportation problemNaval Research Logistics Quarterly9 1–15
B.W. Lamar C.A. Wallace (1997)ArticleTitleRevised-modified penalties for fixed charge transportation problemsManagement Science43 1431–1436
Leyffer, S. (2000), MacMPEC: AMPL Collection of MPECs, http://www-unix.mcs.anl.gov/~leyffer/MacMPEC/.
Z.-Q. Luo J.-S. Pang D. Ralph (1997) Mathematical Programs with Equilibrium Constraints Cambridge University Press Cambridge
K.G. Murty (1968)ArticleTitleSolving the fixed charge problem by ranking the extreme pointsOperations Research16 268–279
U.S. Palekar M.H. Karwan S. Zionts (1990)ArticleTitleA branch-and-bound method for fixed charge transportation problemManagement Science36 1092–1105OccurrenceHandle10.1287/mnsc.36.9.1092
T.V. Thieu (1988)ArticleTitleA note on the solution of bilinear programming problems by reduction to concave minimizationMathematical Programming41 249–260OccurrenceHandle10.1007/BF01580766
H. Vaish C.M. Shetty (1977)ArticleTitleA cutting plane algorithm for the bilinear programming problemNaval Research Logistics Quarterly24 83–94
Author information
Authors and Affiliations
Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 32611-6596, USA
Siriphong Lawphongpanich
- Siriphong Lawphongpanich
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toSiriphong Lawphongpanich.
Rights and permissions
About this article
Cite this article
Lawphongpanich, S. Dynamic Slope Scaling Procedure and Lagrangian Relaxation with Subproblem Approximation.J Glob Optim35, 121–130 (2006). https://doi.org/10.1007/s10898-005-1383-5
Received:
Accepted:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative