?
Алгоритм ветвей и границ для задачи о формировании производственных ячеек
Программные продукты, системы и алгоритмы. 2017. № 4. С. 1-10.
Уткина И. Е., Бацын М. В.
Задача о формировании производственных ячеек является NP-трудной задачей оптимизации ячеечных производственных систем. Из-за большой вычислительной сложности представленной задачи, было создано множество эвристических алгоритмов, но малое количество точных. В этой статье мы предлагаем метод ветвей и границ, который находит точное решение для текущей задачи, используя групповую эффективность в качестве целевой функции. Для линеаризации этой целевой функции мы используем метод Динкельбаха. Наш алгоритм находит оптимальные решения для 24 из 35 известных тестовых данных из литературы, а для оставшихся находит хорошее решение, близкое к известному. Различие от лучшего известного решения всегда меньше 1.5% в значении целевой функции.
Приоритетные направления:
компьютерно-математическое
Язык:
русский
Irina E. Utkina, Mikhail V. Batsyn, Ekaterina K. Batsyna, International Journal of Production Research 2018 Vol. 56 No. 9 P. 3262-3273
Добавлено: 11 марта 2018 г.
Irina Utkina, Mikhail Batsyn, Ekaterina Batsyna, , in : Discrete Optimization and Operations Research/9th International Conference, DOOR 2016, Vladivostok, Russia, September 19-23, 2016, Proceedings. : Springer, 2016. P. 244-255.
Добавлено: 3 октября 2018 г.
Игнатов Д. И., Khvorykh G. V., Khrunin A. V. и др., / Springer. Series LNCS "Lecture Notes in Computer Science". 2020.
Отсутствующие генотипы могут повлиять на эффективность подходов машинного обучения к выявлению генетических вариантов риска распространенных заболеваний и признаков. Проблема возникает, когда генотипические данные собираются в разных экспериментах с разными ДНК-микрочипами, каждый из которых характеризуется своим набором неустановленных (отсутствующих) генотипов. Это может помешать машинному классификатору правильно назначать классы. Чтобы решить эту проблему, мы использовали хорошо изученные ...
Добавлено: 10 ноября 2020 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И. и др., Современные информационные технологии и ИТ-образование 2016 Т. 12 № 3-2 С. 131-137
На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности.
<img /> ...
Добавлено: 5 октября 2017 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И. и др., Автоматизация. Cовременные технологии 2016 № 10 С. 22-29
Рассмотрено новое обобщённое представление для классов индивидуальных задач коммивояжёра - матрица номеров порядка, предназначенное для выделения классов задач, обладающих близкой сложностью. Полученный результат направлен на решение задачи прогнозирования сложности для индивидуальных задач коммивояжёра. Сформулированы две гипотезы относительно мощности предложенного обобщения. Приведены метод получения матрицы номеров порядка и ряд предварительных экспериментальных результатов, не противоречащих одной из ...
Добавлено: 5 октября 2017 г.
M. : Higher School of Economics Publishing House, 2011
Concept discovery is a Knowledge Discovery in Databases (KDD) research field that uses human-centered techniques such as Formal Concept Analysis (FCA), Biclustering, Triclustering, Conceptual Graphs etc. for gaining insight into the underlying conceptual structure of the data. Traditional machine learning techniques are mainly focusing on structured data whereas most data available resides in unstructured, often ...
Добавлено: 3 декабря 2012 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И., Automation and Remote Control 2019 Vol. 80 No. 11 P. 2054-2067
Добавлено: 24 ноября 2019 г.
Mikhail Batsyn, Ilya Bychkov, Boris Goldengorin и др., Springer Proceedings in Mathematics & Statistics 2012 Vol. 32 P. 11-50
В данной работе мы представляем новый подход, основанный на понятии паттерна, в рамках модели линейной задачи о назначениях, целью которого является разработка эвристики для задачи комбинаторной оптимизации (ЗКО). Мы предполагаем, что ЗКО имеет аддитивную (разделяемую) целевую функцию и структура допустимого (оптимального) решения ЗКО задается набором ячеек (позиций) во входном файле. Мы определяем паттерн как набор ...
Добавлено: 9 октября 2012 г.
Игнатов А. Д., Посыпкин М. А., Communications in Computer and Information Science 2018 P. 511-522
Добавлено: 18 октября 2019 г.
Игнатов А. Д., Andrei Gorchakov, Open Computer Science 2020 Vol. 10 No. 1 P. 112-116
Добавлено: 11 июня 2020 г.
Приведены результаты сравнительного статистического анализа времени решения несимметричной задачи коммивояжера (NTSP) методом ветвей и границ (без предвычисления тура) и комбинированным методом. Комбинированный метод состоит из приближенного алгоритма Lin- Kernighan-Helsgaun, используемого для вычисления начального тура, и метода ветвей и границ. Показано, что использование приближенного решения, найденного с помощью алгоритма Lin-Kernighan-Helsgaun, позволяет существенно уменьшить время поиска точного ...
Добавлено: 10 ноября 2019 г.
Головешкин В. А., Жукова Г. Н., Ульянов М. В. и др., Системы компьютерной математики и их приложения 2017 № 18 С. 136-138
В докладе рассматривается статистическая зависимость числа
порожденных вершин дерева решений и физического времени работы
программной реализации метода ветвей и границ для задачи
коммивояжера (TSP). На основе результатов вычислительного
эксперимента получено приближенное соотношение между числом
порожденных вершин (сложность индивидуальной TSP) и физическим
временем. Предлагается использовать это эмпирическое соотношение
для прогнозирования времени работы программы, решающей TSP с
числом «городов» больше 40. ...
Добавлено: 22 марта 2020 г.
Ilya Bychkov, Mikhail Batsyn, Computers & Operations Research 2018 No. 91 P. 112-120
Добавлено: 6 декабря 2017 г.
Игнатов Д. И., Пульманс Й., Захарчук В. В., , in : CDUD'11 – Concept Discovery in Unstructured Data Workshop co-located with the 13th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing (RSFDGrC-2011), June 2011, Moscow, Russia. Issue 757.: M. : Higher School of Economics Publishing House, 2011. P. 122-126.
In this paper we propose two new algorithms based on biclustering analysis, which can be used at the basis of a recommender system for educational orientation of Russian School graduates. The first algorithm was designed to help students make a choice between different university faculties when some of their preferences are known. The second algorithm ...
Добавлено: 3 декабря 2012 г.
Evgeny Maslov, Mikhail Batsyn, Panos M. Pardalos, Journal of Global Optimization 2014 Vol. 59 No. 1 P. 1-21
In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed ...
Добавлено: 24 мая 2013 г.
Для практически значимых оптимизационных задач в области экономики и логистики, а также в ряде технических приложений возникает необходимость решения задачи коммивояжера (traveling salesman problem, TSP). Достаточно часто особенности этих задач приводят к задаче коммивояжера в асимметричной постановке (asymmetric traveling salesman problem, ATSP). Более того, в некоторых практических применениях желательно получение точного решения. Одним из известных ...
Добавлено: 11 декабря 2018 г.
Абрашкин А. А., Journal of Physics A: Mathematical and Theoretical 2022 Vol. 55 No. 41 Article 415701
Добавлено: 13 октября 2022 г.
Игнатов Д. И., Каминская А. Ю., Konstantinova N. и др., , in : Proceedings of The 2014 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, WI-IAT 2014, 11-14 August 2014 Warsaw, Poland. : Los Alamitos, Washington, Tokyo : IEEE Computer Society, 2014. P. 327-335.
...
Добавлено: 9 июня 2014 г.
Игнатов Д. И., Ivanova P., Zamaletdinova A. и др., , in : Supplementary Proceedings ICFCA 2019 Conference and Workshops. Vol. 2378.: CEUR Workshop Proceedings, 2019. P. 28-32.
Добавлено: 31 октября 2019 г.
Batsyn M.V., Kalyagin V.A., Tulyakov D. N., / Институт прикладной математики им. М.В. Келдыша Российской академии наук. 2015. No. 91.
Задача Структурного Сопоставления Протеинов (ЗССП) заключается в поиске наилучшего сопоставления двух протеинов, заданных их первичными структурами. В задаче определяется наиболее близкая подструктура у двух протеинов. Эта задача полиномиально сводится к Задаче о Максимальной Клике (ЗМК) в графе сопоставления. В данной работе представлен эффективный алгоритм для ЗССП, основанный на нашем алгоритме ILS&MCS (Batsyn et al., 2014) ...
Добавлено: 24 октября 2016 г.
Many efficient exact branch and bound maximum clique solvers use approximate coloring to compute an upper bound on the clique number for every subproblem. This technique reasonably promises tight bounds on average, but never tighter than the chromatic number of the graph.
Li and Quan, 2010, AAAI Conference, p. 128–133 describe a way to compute even ...
Добавлено: 24 августа 2015 г.
Фомичев М. И., Информационные технологии моделирования и управления 2018 Т. 109 № 1 С. 47-54
В современном мире промедление в секунду, или даже долю секунды, может стоить миллионы рублей. Заинтересованному лицу важно получить точный ответ на вопрос в кратчайшие сроки. Но, к сожалению, даже при ны- нешних вычислительных мощностях, многие задачи не могут быть решены точно за приемлемое время. ...
Добавлено: 22 марта 2020 г.
Игнатов Д. И., Каминская А. Ю., Malioukov A. и др., , in : Proceedings of International Conference on Conceptual Structures 2014. Vol. 8577: Graph-Based Representation and Reasoning.: Springer, 2014. P. 287-292.
Добавлено: 9 июня 2014 г.
Irina Utkina, Mikhail Batsyn, , in : Models, Algorithms and Technologies for Network Analysis, Springer Proceedings in Mathematics & Statistics. Vol. 156.: Switzerland : Springer, 2016. P. 115-124.
Добавлено: 23 октября 2018 г.