Thủ tục Điều Chỉnh Độ Dốc Động và Giải Phóng Lagrange với Phương Pháp Tiệm Cận Bài Toán Phụ

Journal of Global Optimization - Tập 35 - Trang 121-130 - 2006
Siriphong Lawphongpanich1
1Department of Industrial and Systems Engineering, University of Florida, Gainesville, USA

Tóm tắt

Thủ tục điều chỉnh độ dốc động (DSSP) là một thuật toán heuristic hiệu quả cung cấp các giải pháp tốt cho bài toán vận chuyển với chi phí cố định hoặc bài toán dòng mạng. Tuy nhiên, thủ tục này có động lực đồ họa và dường như không liên quan đến các kỹ thuật tối ưu hóa khác. Trong bài báo này, chúng tôi xây dựng bài toán chi phí cố định dưới dạng một chương trình toán học với các ràng buộc bổ sung (MPCC) và cho thấy rằng DSSP tương đương với việc giải MPCC bằng cách sử dụng sự thư giãn Lagrange với tiệm cận bài toán phụ.

Từ khóa

#thủ tục điều chỉnh độ dốc động #vận chuyển chi phí cố định #chương trình toán học với ràng buộc bổ sung #thư giãn Lagrange

Tài liệu tham khảo

F. Al-Khayyal J.E. Falk (1983) ArticleTitleJointly constrained biconvex programming Mathematics of Operations Research 8 273–286 C. Audet P. Hansen B. Jaumard G. Savard (1999) ArticleTitleA symmetrical linear maxmin approach to disjoint bilinear programming Mathematical Programming 85 573–592 Occurrence Handle10.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 problems Naval Research Logistics Quarterly 8 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 polyhedron Naval Research Logistics Quarterly 32 165–177 A.V. Cabot S.S. Erenguc (1984) ArticleTitleSome branch-and-bound procedure for fixed-cost transportation problems Naval Research Logistics Quarterly 31 145–154 M. Diaby (1991) ArticleTitleSuccessive linear approximation procedure for generalized fixed-charge transportation problem Journal of Operational Research Society 42 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 algorithm Mathematical Programming 12 173–194 Occurrence Handle10.1007/BF01593787 J. Gauvin (1977) ArticleTitleA necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming. Mathematical Programming 12 136–138 Occurrence Handle10.1007/BF01593777 D.B. Khang O. Fujiwara (1991) ArticleTitleApproximate solution of capacitated fixed-charge minimum cost network flow problems Networks 21 689–704 D. Kim P.M. Pardalos (1999) ArticleTitleA solution approach to the fixed charge network flow problem using a dynamic slope scaling procedure Operations Research Letters 24 195–203 Occurrence Handle10.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 problems Networks 35 216–222 Occurrence Handle10.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 problems Journal of Global Optimization 17 225–234 Occurrence Handle10.1023/A:1026502220076 H. Konno (1976) ArticleTitleA cutting plane algorithm for solving bilinear programming Mathematical Programming 11 14–27 Occurrence Handle10.1007/BF01580367 H. Kuhn W. Baumol (1962) ArticleTitleAn approximate algorithm for the fixed charge transportation problem Naval Research Logistics Quarterly 9 1–15 B.W. Lamar C.A. Wallace (1997) ArticleTitleRevised-modified penalties for fixed charge transportation problems Management Science 43 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 points Operations Research 16 268–279 U.S. Palekar M.H. Karwan S. Zionts (1990) ArticleTitleA branch-and-bound method for fixed charge transportation problem Management Science 36 1092–1105 Occurrence Handle10.1287/mnsc.36.9.1092 T.V. Thieu (1988) ArticleTitleA note on the solution of bilinear programming problems by reduction to concave minimization Mathematical Programming 41 249–260 Occurrence Handle10.1007/BF01580766 H. Vaish C.M. Shetty (1977) ArticleTitleA cutting plane algorithm for the bilinear programming problem Naval Research Logistics Quarterly 24 83–94