05.13.16 (Computer techniques, mathematical modelling, and mathematical methods with an application to scientific researches)
Keywords:
operations research; mathematical programming; discrete programming; integer programming; lagre-scale problems; branch and bound algorithms of discrete programming; decomposition methods; approximation methods and heuristics.
Subject:
Is developed a decomposition approach to solving a travelling salesman problem of the large-scale. The approach allows reducing solution of the large-scale problem to solving of subtasks essentially of smaller dimension and creation of solution of the initial task from solutions of subtasks. The combined algorithm of branches and bounds applied for solution of subtasks in the decomposition approach is developed. Are conducted research of the multicriteria problems of discrete programming and computing experiment on solution of the classical problems with two and three criteria. The research on parameterisation of the large-scale discrete programming problems is fulfilled.
Biography
Graduated from Faculty of Mathematics and Physics of I. I. Mechnikov Odessa State University in 1960 (department of theory of functions and difference equations). Postgraduate studies, Computer Center Russian Academy of Sciences, Moscow (1964–1967). Ph.D. thesis was defended in 1967. D.Sci. thesis was defended in 1990. A list of my works contains more than 95 titles.
Is elected in 2000 in Corresponding Member of the Russian academy Natural sciences.
Main publications:
Sigal I. Kh. Dekompozitsionnyi podkhod k resheniyu zadachi kommivoyazhera bolshoi razmernosti i nekotorye ego prilozheniya // Izvestiya AN SSSR. Tekhnicheskaya kibernetika, 1990, 6, 143–155.
Sigal I. Kh. Algoritmy dlya resheniya bikriterialnoi zadachi kommivoyazhera bolshoi razmernosti // ZhVM i MF, 1994, 34(1), 44–57.
Melamed I. I., Sigal I. Kh. Vychislitelnoe issledovanie lineinoi svertki kriteriev v mnogokriterialnom diskretnom programmirovanii // Doklady RAN, 1995, 345(4), 463–466.
Sigal I. Kh. Parametrizatsiya i issledovanie nekotorykh zadach diskretnogo programmirovaniya bolshoi razmernosti // Izvestiya RAN. Teoriya i sistemy upravleniya, 2001, 2, 60–69.
Sigal I. Kh., Ivanova A. P. Vvedenie v prikladnoe diskretnoe programmirovanie. M. Fizmatlit. 2002.
D. I. Kogan, I. Kh. Sigal, “Accounting for the time characteristics of a class of scheduling problems for moving processor”, Avtomat. i Telemekh., 2015, no. 12, 121–134; Autom. Remote Control, 76:12 (2015), 2190–2200
Bo Tian, M. A. Posypkin, I. Kh. Sigal, “Load balancing in solving problems based on estimates of the computational complexity of subproblems”, Informatsionnye Tekhnologii i Vychslitel'nye Sistemy, 2015, no. 1, 10–18
2010
3.
R. M. Kolpakov, M. A. Posypkin, I. Kh. Sigal, “On a lower bound on the computational complexity of a parallel implementation of the branch-and-bound method”, Avtomat. i Telemekh., 2010, no. 10, 156–166; Autom. Remote Control, 71:10 (2010), 2152–2161
M. A. Posypkin, I. Kh. Sigal, “Application of parallel heuristic algorithms for speeding up parallel implementations of the branch-and-bound method”, Zh. Vychisl. Mat. Mat. Fiz., 47:9 (2007), 1524–1537; Comput. Math. Math. Phys., 47:9 (2007), 1464–1476
M. A. Posypkin, I. Kh. Sigal, “Speedup estimates for some variants of the parallel implementations of the branch-and-bound method”, Zh. Vychisl. Mat. Mat. Fiz., 46:12 (2006), 2289–2304; Comput. Math. Math. Phys., 46:12 (2006), 2187–2202
I. I. Melamed, I. Kh. Sigal, N. Yu. Vladimirova, “Study of the linear parametrization of criteria in the bicriteria knapsack problem”, Zh. Vychisl. Mat. Mat. Fiz., 39:5 (1999), 753–758; Comput. Math. Math. Phys., 39:5 (1999), 721–726
I. I. Melamed, I. Kh. Sigal, “Numerical analysis of tricriteria tree and assignment problems”, Zh. Vychisl. Mat. Mat. Fiz., 38:10 (1998), 1780–1787; Comput. Math. Math. Phys., 38:10 (1998), 1707–1714
I. I. Melamed, I. Kh. Sigal, “Analysis of Branch-and-Bound Parameters of Solutions in the Symmetric Traveling Salesman Problem”, Avtomat. i Telemekh., 1997, no. 10, 186–192; Autom. Remote Control, 58:10 (1997), 1706–1711
I. I. Melamed, I. Kh. Sigal, “The linear convolution of criteria in the bicriteria traveling salesman problem”, Zh. Vychisl. Mat. Mat. Fiz., 37:8 (1997), 933–936; Comput. Math. Math. Phys., 37:8 (1997), 902–905
I. I. Melamed, I. Kh. Sigal, “A computational investigation of linear parametrization of criteria in multicriteria discrete programming”, Zh. Vychisl. Mat. Mat. Fiz., 36:10 (1996), 23–25; Comput. Math. Math. Phys., 36:10 (1996), 1341–1343
I. I. Melamed, I. Kh. Sigal, “Computational stability of a linear convolution of criteria in
multicriterial discrete programming”, Dokl. Akad. Nauk, 345:4 (1995), 463–466
I. I. Melamed, I. Kh. Sigal, “Investigation of a linear convolution of criteria in multicriterial discrete programming”, Zh. Vychisl. Mat. Mat. Fiz., 35:8 (1995), 1260–1270; Comput. Math. Math. Phys., 35:8 (1995), 1009–1017
I. I. Melamed, S. I. Sergeev, I. Kh. Sigal, “The traveling salesman problem. Approximate algorithms”, Avtomat. i Telemekh., 1989, no. 11, 3–26; Autom. Remote Control, 50:11 (1989), 1459–1479
I. I. Melamed, S. I. Sergeev, I. Kh. Sigal, “The traveling salesman's problem. Exact methods”, Avtomat. i Telemekh., 1989, no. 10, 3–29; Autom. Remote Control, 50:10 (1989), 1303–1324
I. I. Melamed, S. I. Sergeev, I. Kh. Sigal, “The traveling salesman problem. Issues in theory”, Avtomat. i Telemekh., 1989, no. 9, 3–33; Autom. Remote Control, 50:9 (1989), 1147–1173
I. Kh. Sigal, “A sequence for using algorithms for the approximate solution in the hybrid algorithm for solving the travelling salesman problem”, Zh. Vychisl. Mat. Mat. Fiz., 29:11 (1989), 1714–1721; U.S.S.R. Comput. Math. Math. Phys., 29:6 (1989), 80–84
I. Kh. Sigal, “An algorithm for the approximate solution of a large-scale travelling salesman problem in a plane”, Zh. Vychisl. Mat. Mat. Fiz., 28:8 (1988), 1268–1272; U.S.S.R. Comput. Math. Math. Phys., 28:4 (1988), 205–208
E. N. Gordeev, V. K. Leont'ev, I. Kh. Sigal, “Computing algorithms for determination of the radius of stability in choice problems”, Zh. Vychisl. Mat. Mat. Fiz., 23:4 (1983), 973–979; U.S.S.R. Comput. Math. Math. Phys., 23:4 (1983), 128–132
I. Kh. Sigal, V. A. Chebakov, “A method of matrix analysis and its application to a problem in the theory of graphs”, Zh. Vychisl. Mat. Mat. Fiz., 5:1 (1965), 148–150; U.S.S.R. Comput. Math. Math. Phys., 5:1 (1965), 213–216