Nguyễn Thị Cẩm Tiên * , Nguyễn Thanh Toàn , Thái Đức Duy Mai Đình Lộc

* Tác giả liên hệ (tienb1900378@student.ctu.edu.vn)

Abstract

In this paper, the combinatorial optimization problem with the objective function being a multiplication of several classical functions is concerned. Firstly, an equivalent master problem is constructed and then the corresponding multicriteria optimization version which plays an important role in finding an optimal solution to the original problem is shown. Based on the solution existence property to the original problem which is also an extremely supporting and efficient solution of the multicriteria optimization problem, a generic algorithm for the problem is given. The case with the multiplication of exactly two functions is also discussed. Finally, a linear time algorithm for solving the multiplicative 1-median location problem on a tree is proposed.

Keywords: Multiplicative optimization, Multicriteria optimization, 1-median location, Nondominating set

Tóm tắt

Trong bài báo này, bài toán tối ưu tổ hợp trong đó hàm mục tiêu là tích của một số hàm cổ điển được quan tâm. Trước tiên, một bài toán tương đương được xây dựng và sau đó chỉ ra rằng bài toán tối ưu đa mục tiêu tương ứng đóng một vai trò quan trọng trong việc tìm ra lời giải tối ưu cho bài toán ban đầu. Dựa trên tính chất tồn tại nghiệm tối ưu của bài toán ban đầu cũng là một nghiệm bổ trợ hữu hiệu của bài toán tối ưu đa mục tiêu, một thuật toán tổng quát cho bài toán được đưa ra. Trường hợp hàm nhân tính với chính xác hai hàm số cũng được đề cập. Cuối bài báo này, một thuật toán chạy trong thời gian tuyến tính để giải bài toán 1-median trên cây với hàm nhân tính được đề xuất.

Từ khóa: Tối ưu nhân tính, Tối ưu đa mục tiêu, Vị trí 1-median, Tập không bị trội

Article Details

Tài liệu tham khảo

Aneja, Y. P., Aggarwal, V. A., & Nair, K. P. K. (1984). On a class of quadratic programs. European Journal of Operational Research, 18(1), 62-70.

Averbakh, I., & Berman, O. (2000). Minmax regret median location on a network under uncertainty. INFORMS Journal on Computing, 12(2), 104-110.

Dorneich, M. C., & Sahinidis, N. V. (1995). Global optimization algorithms for chip layout and compaction. Engineering Optimization+ A35, 25(2), 131-154.

Drezner, Z., & Hamacher, H. (2002). Facility location: applications and theory Springer Verlag.

Ehrgott, M. (2005). Multicriteria optimization. Springer-Verlag, Berlin, Heidelberg.

Goldman, A. J. (1971). Optimal center location in simple networks. Transportation science, 5(2), 539-560.

Hamacher, H. W., Labbé, M., & Nickel, S. (1999). Multicriteria network location problems with sum objectives. Networks: An International Journal, 33(2), 79-92.

Kariv, O., & Hakimi, S. L. (1979). An algorithmic approach to network location problems, II. The p-medians, SIAM Journal on Applied Mathematics 37(3), 536-560.

Konno, H., & Kuno, T. (1990). Generalized linear multiplicative and fractional programming. Annals of Operations Research, 25(1), 147-161.

Konno, H., & Kuno, T. (1992). Linear multiplicative programming. Mathematical Programming, 56(1), 51-64.

Konno, H., & Kuno, T. (1995). Multiplicative programming problems. In: Horst R., & Pardalos P.M. (eds). Handbook of Global Optimization. Nonconvex Optimization and Its Applications (Vol. 2). Springer, Boston.

Konno, H., Yajima, Y., & Matsui, T. (1991). Parametric simplex algorithms for solving a special class of nonconvex minimization problems. Journal of Global Optimization, 1(1), 65-81.

Kuno, T. (1996). A practical alogorithm for minimizing a rank-two saddle function on a polytope. Journal of the Operations Research Society of Japan, 39(1), 63-76.

Maranas, C. D., Androulakis, I. P., Floudas, C. A., Berger, A. J., & Mulvey, J. M. (1997). Solving long-term financial planning problems via global optimization. Journal of Economic Dynamics and Control, 21(8-9), 1405-1425.

Nguyen, K. T., & Hung, N. T. (2020). The inverse connected p-median problem on block graphs under various cost functions. Annals of Operations Research, 292(1), 97-112.

Nickel, S., & Puerto, J. (2005). Location Theory: A Unified Approach, Springer. New York.

Puerto, J., Ricca, F., & Scozzari, A. (2018). Extensive facility location problems on networks: an updated review. Top, 26(2), 187-226.

Punnen, A. (2001). Combinatorial optimization with multiplicative objective function. International Journal of Operations and Quantitative Management, 7(3), 205-209.

Thoai, N. V. (1991). A global optimization approach for solving the convex multiplicative programming problem. Journal of Global Optimization, 1(4), 341-357.

Tuy, H. (1991). Polyhedral annexaton, dualization and dimension reduction technique in global optimization. Journal of Global Optimization, 1(3), 229-244.

Tuy, H., & Tam, B. T. (1992). An efficient solution method for rank two quasiconcave minimization problems. Optimization, 24(1-2), 43-56.

Watanabe, H. (1996). Bond portfolio optimization problems and their applications to index tracking: a partial optimization approach. Journal of the Operations Research Society of Japan, 39(3), 295-306