Movatterモバイル変換


[0]ホーム

URL:


Skip to main content
Springer Nature Link
Log in

Dynamic Slope Scaling Procedure and Lagrangian Relaxation with Subproblem Approximation

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

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

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. F. Al-Khayyal J.E. Falk (1983)ArticleTitleJointly constrained biconvex programmingMathematics of Operations Research8 273–286

    Google Scholar 

  2. C. Audet P. Hansen B. Jaumard G. Savard (1999)ArticleTitleA symmetrical linear maxmin approach to disjoint bilinear programmingMathematical Programming85 573–592OccurrenceHandle10.1007/s101070050072

    Article  Google Scholar 

  3. 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.

  4. M.L. Balinski (1961)ArticleTitleFixed cost transportation problemsNaval Research Logistics Quarterly8 41–54

    Google Scholar 

  5. M.S. Bazaraa H.D. Sherali C.M. Shetty (1993) Nonlinear Programming: Theory and Algorithm Wiley New York

    Google Scholar 

  6. H.P. Benson (1985)ArticleTitleA finite algorithm for concave minimization over a polyhedronNaval Research Logistics Quarterly32 165–177

    Google Scholar 

  7. A.V. Cabot S.S. Erenguc (1984)ArticleTitleSome branch-and-bound procedure for fixed-cost transportation problemsNaval Research Logistics Quarterly31 145–154

    Google Scholar 

  8. M. Diaby (1991)ArticleTitleSuccessive linear approximation procedure for generalized fixed-charge transportation problemJournal of Operational Research Society42 991–1001

    Google Scholar 

  9. 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.

  10. 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.

  11. Fletcher, R. and Leyffer, S. (2002), Numerical experience with solving MPECs as NLPs, Numerical Analysis Report NA/210, Department of Mathematics, University of Dundee.

  12. G. Gallo A. Ulkucu (1977)ArticleTitleBilinear programming: an exact algorithmMathematical Programming12 173–194OccurrenceHandle10.1007/BF01593787

    Article  Google Scholar 

  13. J. Gauvin (1977)ArticleTitleA necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming.Mathematical Programming12 136–138OccurrenceHandle10.1007/BF01593777

    Article  Google Scholar 

  14. D.B. Khang O. Fujiwara (1991)ArticleTitleApproximate solution of capacitated fixed-charge minimum cost network flow problemsNetworks21 689–704

    Google Scholar 

  15. 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

    Article  Google Scholar 

  16. 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

    Article  Google Scholar 

  17. 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

    Article  Google Scholar 

  18. H. Konno (1976)ArticleTitleA cutting plane algorithm for solving bilinear programmingMathematical Programming11 14–27OccurrenceHandle10.1007/BF01580367

    Article  Google Scholar 

  19. H. Kuhn W. Baumol (1962)ArticleTitleAn approximate algorithm for the fixed charge transportation problemNaval Research Logistics Quarterly9 1–15

    Google Scholar 

  20. B.W. Lamar C.A. Wallace (1997)ArticleTitleRevised-modified penalties for fixed charge transportation problemsManagement Science43 1431–1436

    Google Scholar 

  21. Leyffer, S. (2000), MacMPEC: AMPL Collection of MPECs, http://www-unix.mcs.anl.gov/~leyffer/MacMPEC/.

  22. Z.-Q. Luo J.-S. Pang D. Ralph (1997) Mathematical Programs with Equilibrium Constraints Cambridge University Press Cambridge

    Google Scholar 

  23. K.G. Murty (1968)ArticleTitleSolving the fixed charge problem by ranking the extreme pointsOperations Research16 268–279

    Google Scholar 

  24. 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

    Article  Google Scholar 

  25. T.V. Thieu (1988)ArticleTitleA note on the solution of bilinear programming problems by reduction to concave minimizationMathematical Programming41 249–260OccurrenceHandle10.1007/BF01580766

    Article  Google Scholar 

  26. H. Vaish C.M. Shetty (1977)ArticleTitleA cutting plane algorithm for the bilinear programming problemNaval Research Logistics Quarterly24 83–94

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 32611-6596, USA

    Siriphong Lawphongpanich

Authors
  1. Siriphong Lawphongpanich

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toSiriphong Lawphongpanich.

Rights and permissions

About this article

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement


[8]ページ先頭

©2009-2025 Movatter.jp