Abstract
The paper proposes an exact method to solve an optimization problem on arrangements with a linear-fractional objective function and additional linear constraints. The efficiency of the solution algorithm is analyzed by means of numerical experiments.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Yu. G. Stoyan and O. O. Yemets’, Theory and Methods of Euclidean Combinatory Optimization [in Ukrainain], ISDO, Kyiv (1993).
O. O. Yemets’ and L. M. Kolechkina, “Optimization problem on permutations with a fractional-linear objective function: properties of the set of feasible solutions,” Ukr. Mat. Zh., 52, No. 12, 1630–1640 (2000).
O. O. Yemets’, O. V. Roskladka, and S. I. Nedobachii, “A nonreducible system of constraints for a general polyhedron of arrangements,” Ukr. Mat. Zh., 55, No. 1, 3–11 (2003).
O. A. Yemets and O. A. Chernenko, “A nonreducible system of constraints of a combinatorial polyhedron in a linear-fractional optimization problem on arrangements,” Cybern. Syst. Analysis, Vol. 41, No. 2, 246–254 (2005).
O. O. Chernenko, “Analysis of the set of feasible solutions for an optimization problem for a fractional-linear function on a Euclidean combinatorial set of arrangements,” in: Proc. 10th Acad. M. Kravchuk Intern. Sci. Conf. (May 13–15, 2004, Kyiv) [in Ukrainian], Kyiv (2004), p. 548.
O. A. Yemets and T. N. Barbolina, “Solution of Euclidean combinatorial optimization problems by the method of construction of a lexicographic equivalence,” Cybern. Syst. Analysis, Vol. 40, No. 5, 726–734 (2004).
O. A. Yemets and L. N. Kolechkina, “Solution of optimization problem with fractional-linear objective functions and additional linear constraints on permutations,” Cybern. Syst. Analysis, Vol. 40, No. 3, 329–339 (2004).
O. A. Emets and T. N. Barbolina, “Solving linear optimization problems on arrangements by the truncation method,” Cybern. Syst. Analysis, Vol. 39, No. 6, 726–734 (2003).
A. A. Korbut and Yu. Yu. Finkel’shtein, Discrete Programming [in Russian], Nauka, Moscow (1969).
Yu. Yu. Chervak, “Method of lexicographic search of solutions for discrete problems of convex programming,” Ukr. Mat. Zh., 26, No. 2, 269–272 (1974).
A. A. Kolokolov and T. V. Levanova, “Algorithms of decomposition and enumeration of L-classes for the solution of some problems of arrangement,” Vestn. Omsk. Univ., Issue 1, 21–23 (1996).
G. V. Reklaitis, A. Ravindran, and K. M. Ragsdell, Optimization: Methods and Applications, John Wiley and Sons, NY (1983).
B. N. Pshenichnyi, E. I. Nenakhov, and V. N. Kuz’menko, “Mixed method for solving the general convex programming problem,” Cybern. Syst. Analysis, Vol. 34, No. 4, 577–587 (1998).
Author information
Authors and Affiliations
Additional information
__________
Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 79–85, September–October 2006.
Rights and permissions
About this article
Cite this article
Yemets, O.A., Barbolina, T.N. & Chernenko, O.A. Solving optimization problems with linear-fractional objective functions and additional constraints on arrangements. Cybern Syst Anal 42, 680–685 (2006). https://doi.org/10.1007/s10559-006-0106-3
Received:
Issue Date:
DOI: https://doi.org/10.1007/s10559-006-0106-3