Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật toán Tỉ lệ Affine cho Lập trình Tuyến tính Hai mục tiêu
Journal of the Operations Research Society of China - Trang 1-15 - 2023
Tóm tắt
Đối với bài toán lập trình tuyến tính hai mục tiêu, chúng tôi phát triển một thuật toán tỉ lệ affine với hướng tối thiểu-tối đa và chứng minh tính hội tụ của nó để tìm ra giải pháp hiệu quả. Chúng tôi triển khai thuật toán này cho một số vấn đề nhỏ trong tài liệu.
Từ khóa
#lập trình tuyến tính #thuật toán tỉ lệ affine #hai mục tiêu #tính hội tụTài liệu tham khảo
Clímaco, J.N., Antunes, C.H., Alves, M.J.G.: Programação Linear Multiobjectivo. Coimbra University Press, Coimbra (2003)
Bornstein, C.T., Maculan, N., Pascoal, M., Pinto, L.L.: Multiobjective combinatorial optimization problems with a cost and several bottleneck objective functions: an algorithm with reoptimization. Comput. Oper. Res. 39(9), 1969–1976 (2012)
Arbel, A., Oren, S.S.: Generating interior search directions for multiobjective linear programming. J. Multi-Criteria Decis. Anal. 2(2), 73–86 (1993)
Arbel, A., Oren, S.S.: Using approximate gradients in developing an interactive interior primal-dual multiobjective linear programming algorithm. Eur. J. Oper. Res. 89(1), 202–211 (1996)
Aghezzaf, B., Ouaderhman, T.: An interactive interior point algorithm for multiobjective linear programming problems. Oper. Res. Lett. 29(4), 163–170 (2001)
Fonseca, M., Figueira, J.R., Resende, M.G.C.: Solving scalarized multiobjective network flow problems using an interior point method. Int. Trans. Oper. Res. 17(5), 607–636 (2010)
Nyiam, P.B., Salhi, A.: On the simplex, interior-point and objective space approaches to multiobjective linear programming. J. Algorithms Comput. Technol. 15(1), 1–20 (2021)
Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum 22(4), 425–460 (2000)
Miettinen, K., Mäkelä, M.M.: On scalarizing functions in multiobjective optimization. OR Spektrum 24(2), 193–213 (2002)
Ehrgott, M., Puerto, J., Rodriguez-Chia, A.M.: Primal-dual simplex method for multiobjective linear programming. J. Optim. Theory Appl. 134(3), 483–497 (2007)
Ehrgott, M., Gandibleux, X.: Bound sets for biobjective combinatorial optimization problems. Comput. Oper. Res. 34(9), 2674–2694 (2007)
Fernández, J., Tóth, B.: Obtaining an outer approximation of the efficient set of nonlinear biobjective problems. J. Glob. Optim. 38(2), 315–331 (2007)
Martin, B., Goldsztejn, A., Granvilliers, L., Jermann, C.: Constraint propagation using dominance in interval branch & bound for nonlinear biobjective optimization. Eur. J. Oper. Res. 260(3), 934–948 (2017)
Cooper, K., Hunter, S.R., Nagaraj, K.: Biobjective simulation optimization on integer lattices using the epsilon-constraint method in a retrospective approximation framework. INFORMS J. Comput. 32(4), 1080–1100 (2020)
Dikin, I.: Iterative solution of problems of linear and quadratic programming. Dokl. Akad. Nauk SSSR 174(4), 747–748 (1967)
Barnes, E.R.: A variation on Karmarkar’s algorithm for solving linear programming problems. Math. Program. 36, 174–182 (1986)
Gonzaga, C.: Path-following methods for linear programming. SIAM Rev. 34(2), 167–224 (1992)
Menezes, M.A.F.: Algoritmos de pontos interiores para programação linear combinando fase 1 e fase 2. Master's thesis, Federal University of Rio de Janeir, Brazil (1991)
Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I. Springer, Heidelberg (1993)
Saigal, R.: Linear Programming: A Modern Integrated Analysis. Springer, New York (1995)
Miettinen, K.: Nonlinear Multiobjective Optimization. Springer, New York (1998)
Ermol’ev, Y.M., Tuniev, A.D.: Random Fejér and quasi-Fejér sequences, Theory of Optimal Solutions—Akademiya Nauk Ukrainskoĭ SSR Kiev vol. 2, pp. 76–83 (1968); translated in: American Mathematical Society Selected Translations in Mathematical Statistics and Probability vol. 13, pp. 143–148 (1973)
Combettes, P.L.: Quasi-Fejérian analysis of some optimization algorithms. Stud. Comput. Math. 8, 115–152 (2001)
Dikin, I.: On the convergence of an iterative process. Upr. Sist. 12, 54–60 (1974). (in Russian)
Drummond, L.M.G., Svaiter, B.F.: A steepest descent method for vector optimization. J. Comput. Appl. Math. 175(2), 395–414 (2005)
Arbel, A.: Fundamentals of interior multiple objective linear programming algorithms. In: Gal, T., Stewart, T.J., Hanne, T. (eds.) Multicriteria Decision Making, pp. 367–396. Springer, Boston, MA (1999)