Прикладная комбинаторная оптимизация (ПКО) (исследовательский курс)

План Доклада
Краткая биография докладчика
Цель доклада
Чемпионат мира по Задаче Коммивояжера (ЗК)
С Кем мы соревнуемся по ЗК, 1-3
Один из исследовательских проектов: Оптимизация прерываемых расписаний на одной машине
Единственность и Устойчивость оптимального решения Задачи Комбинаторной Оптимизации (Минимальное Остовное Дерево - вопрос, Задача о Назначении)
Литература к Проектам

Краткая биография
Борис Гольденгорин – изобретатель и автор:
Корректирующих алгоритмов (ДАН СССР, 1983);
Алгоритмов, основанных на допусках (2002);
Теории и практике примения допусков для решения труднорешаемых задач комбинаторной оптимизации.
Автор более 30 работ, опубликованных в журналах Q2 и Q1. https://www.amazon.com/Boris-Goldengorin/e/B00AR073TE

Цель Доклада
Целью доклада является приглашение студентов и сотрудников на спецкурс Прикладная Комбинаторная Оптимизация (ПКО), в рамках которого будут предложены индивидуальные и/или групповые (в группе не более 3 участников) проекты, результаты которых будут рекомендованы к публикации в рейтинговых международных журналах Q2 или Q1, смотрите публикацию моего студента Эхсана Ахмади https://www.scimagojr.com/journalsearch.php?q=18136&tip=sid.

Чемпионата мира по Задаче Коммивояжера (ЗК) n=6880
Одним из примеров является оптимальное решение, найденное студентами Герольд Ягер и Дирк Рихтер, Университет Халле – Саале Виттенберг (Германия) за 5327 секунд и опубликованное 24 мая 2006 года для эталонного теста Задачи Коммивояжера (ЗК). Этот мировой рекорд был подтвержден почти через 11 лет, 16 апреля 2017 года группой американских математиков, занимающихся только ЗК более 30 лет ЗК их программным обеспечением Concorde на основе CPLEX решателя за 2,2 дня или 190 080 секунд; см http://www.math.uwaterloo.ca/tsp/vlsi/xsc6880.log.html

С Кем мы соревнуемся по ЗК, 1
1995
D. Applegate, R. Bixby, V. Chvátal, and W. Cook, "Finding cuts in the TSP (A preliminary report)", DIMACS Technical Report 95-05, March.
A detailed description of several separation algorithms for combs and clique trees. These algorithms were used by the authors to solve a series of TSPLIB test instances, including pcb3038, fnl4461, and pla7392. Certificates of the optimality of these three large instances were made available on the internet by the authors.

С Кем мы соревнуемся по ЗК, 2; по деньгам
$340,000 (Canadian), NSERC Discovery Grant (awarded also NSERC Accelerator Supplement), 2014–2019,
$209,280, Office of Naval Research, 2013–2015
$1,035,427, Office of Naval Research, 2001–2012,
$945,809, Office of Naval Research (Basic Research Challenge), 2008–2012, with S. Ahmed, A. Nemirovski (Principal Investigator), and A. Shapiro.
$341,319, National Science Foundation, 2007–2011,
$375,000, National Science Foundation, 2003–2006,
$176,388 Subcontract, Office of Naval Research, 2002–2004,
Итого с 2002 по 2019 за 18 лет $3,423,223
Всего с 1996 по 2019 за 25 лет $6,457,545
В среднем $258,301.8 в год
$143,000, Texas Higher Education Coordinating Board, 2000–2001,
$83,000, Texas Higher Education Coordinating Board, 2000–2001,
$39,278, Office of Naval Research, 1999,
$100,000 (Cash Gift) and
$750,000 (Computing Equipment), Compaq Corporation, 1999–2000,
$169,125,Texas Higher Education Coordinating Board, 1998–1999,
$1,000,000, W.M. Keck Foundation, 1997,
$93,000, Office of Naval Rese ;3,034arch, 1997–2000,
$221,919 Intel Corporation, 1997–1999,
$435,000 Digital Equipment Corporation, 1996
Итого с 1996 по 2001 за 7 лет $3,034,322

С Кем мы соревнуемся по ЗК, 3; по публикациям
Books
In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton University Press, 2012.
The Traveling Salesman Problem: A Computational Study, with David L. Applegate, Robert E. Bixby, and Vaˇsek Chv´atal, Princeton University Press, 2006.
3. Combinatorial Optimization, with William Cunningham, William Pulleyblank, and Alexander Schrijver, John Wiley and Sons, New York, 1998.

Один из исследовательских проектов: Оптимизация прерываемых расписаний на одной машине
В докладе рассматривается семейство задач оптимизации прерываемых расписаний на одной машине с произвольными сроками появления и исполнения, выполнения, приоритетами (весами), конечным числом заданий (работ) и произвольными целевыми функциями.
На примере одной из задач рассматривается метод решения исходной задачи оптимизации прерываемых расписаний на одной машине. Метод основан на предвычислениях исходных данных моделируемой задачи, сведенной к решению Линейной Задачи о Назначении (ЛЗН) с дополнительными ограничениями. На стадии моделирования исходное семейство задач оптимизации расписаний существенно расширяется за счет применения понятия шаблона в ЛЗН. На следующем шаге применяется метод ветвей и границ, который основан на теориях допусков и корректирующих алгоритмов.

Литература к проектам
M. L. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, 2016.
B. Goldengorin, D Krushinsky. Linear Assignment Problems in Combinatorial Optimization. Optimization Methods and Applications. Springer Optimization and Its Applications, Vol. 130, 2017, 183—216.
M. Batsyn, B. Goldengorin, P. Pardalos, & P. Sukhov. Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time. Optimization Methods & Software, 2014, 29(5), 955–963.
M. Batsyn, B. Goldengorin, P. Sukhov, P. M. Pardalos. Lower and Upper Bounds for the Preemptive Single Machine Scheduling Problem with Equal Processing Times. Springer Proceedings in Mathematics & Statistics, 2013, 59, 11--30.
R. Germs, B.Goldengorin, M. Turkensteen. Lower tolerance-based Branch and Bound algorithms for the ATSP. Computers and Operations Research, 2012, 39(2), 291--298.