Abstract
A conditional linear fully combinatorial minimization problem on permutations is analyzed. The methods of branching, pruning, and estimating in the branch and bound method are proposed for this problem. An illustrative example of applying the method to the problem is presented. The property of the proposed estimation of the admissible subset, which increases the efficiency of branching and pruning, is proved.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
I. V. Sergienko, Mathematical Models and Methods to Solve Discrete Optimization Problems [in Russian], Naukova Dumka, Kyiv (1988).
I. V. Sergienko and M. F. Kaspshitskaya, Models and Methods for Computer Solution of Combinatorial Optimization Problems [in Russian], Naukova Dumka, Kyiv (1981).
I. V. Sergienko and V. P. Shilo, Discrete Optimization Problems: Challenges, Methods, Solutions, Analysis [in Russian], Naukova Dumka, Kyiv (2003).
Yu. G. Stoyan and O. O. Iemets, Theory and Methods of Euclidean Combinatorial Optimization [in Ukrainian], Inst. Syst. Doslidzh. Osvity, Kyiv (1993).
Yu. G. Stoyan, O. O. Iemets, and Ye. M. Yemets, Optimization of Polyarrangements: Theory and Methods [in Ukrainian], PUSKU, Poltava (2005).
O. A. Iemets, Euclidean Combinatorial Sets and Optimization on them. Advances in Mathematical Programming [in Russian], UMK VO, Kyiv (1992).
O. O. Iemets and O. V. Roskladka, Optimization Problems on Polycombinatorial Sets: Properties and Solution [in Ukrainian], PUSKU, Poltava (2006).
O. A. Iemets and L. N. Kolechkina, Combinatorial Optimization Problems with Linear Fractional Objective Functions [in Russian], Naukova Dumka, Kyiv (2005).
O. A. Iemets and T. N. Barbolina, Combinatorial Optimization on Arrangements [in Russian], Naukova Dumka, Kyiv (2008).
O. A. Iemets and N. G. Romanova, Optimization on Polypermutations [in Russian], Naukova Dumka, Kyiv (2010).
O. O. Iemets and T. O. Parfionova, “Transportation problems on permutations: Properties of estimates in the branch and bound method,” Cybern. Syst. Analysis, 46, No. 6, 953–959 (2010).
O. O. Iemets and T. A. Parfionova, “Estimating admissible solution sets of a transportation problems on permutations solved by the branch and bound method,” Naukovi Visti NYUU KPI, No. 1, 21–28 (2010).
O. O. Iemets and T. O. Parfionova, “An approximate method to solve combinatorial transportantion problems,” Radioelektronika i Informatika, No. 2, 39–41 (2006).
O. Iemets, N. Romanova, and O. Roskladka, “Properties of some combinatorial optimization problems on permutations and methods of their solution,” Visnyk Lviv. Univ., Ser. Prikl. Matem. Inform., Issue 5, 13–15 (2002).
O. A. Iemets, N. G. Romanova, and T. V. Chilikina, “Optimization on vertex Euclidean combinatorial sets,” Mat. Model., No. 2 (10), 39–41 (2003).
O. A. Iemets and N. G. Romanova, “A combined method to solve linear combinatorial optimization problems on vertex Euclidean combinatorial sets,” Dinamich Sistemy (Interdiscipl. Sci. Collect. of Papers.), Issue 17, 166–170 (2004).
Yu. M. Ermoliev, I. I. Lyashko, V. S. Mikhalevich, and V. I. Tyuptya, Mathematical Methods of Operations Research: A Handbook for High Schools [in Russian], Vyshcha Shkola (1979).
I. N. Lyashenko, E. A. Karagodova, N. V. Chernikova, and N. Z. Shor, Linear and Nonlinear Programming [in Russian], Vyshcha Shkola, Kyiv (1975).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Kibernetika i Sistemnyi Analiz, No. 2, March–April, 2013, pp. 121–138.
Rights and permissions
About this article
Cite this article
Iemets, O.O., Yemets, Y.M., Parfionova, T.A. et al. Solving Linear Conditional Completely Combinatorial Optimization Problems on Permutations by the Branch and Bound Method. Cybern Syst Anal 49, 264–278 (2013). https://doi.org/10.1007/s10559-013-9508-1
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10559-013-9508-1