Моделирование труднорешаемых задач — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(→‎Что делать?.)
Строка 40: Строка 40:
 
** Потом статья с объяснением.
 
** Потом статья с объяснением.
  
−
==== Решения есть . ====
+
==== Что вы получите . ====
−
* Win-Win!
+
* Навыки моделирования
−
* Бизнес-аналитикам, алгоритмистам, прожект и продукт-менеджерам.
+
** в PYOMO, сразу см. [https://software.sandia.gov/downloads/pub/pyomo/Pyomo-Workshop-Summer-2018.pdf воркшоп]
−
* Воркфлоу «взятия задачи» аналогичен блоку «[[Практикуемся_В_Алгоритмах]]»
+
** в PYSAT
−
** Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в [[Lab17]].
+
** Jupyter Notebooks
 +
→ Бизнес-аналитик-алгоритмист! (нарасхват!)
  
 +
==== С чем работаем . ====
 +
* Настоящие классические задачи в одном месте (ГД+ВК+…)
 +
** [[Open Classic Hard Problems]]
 +
*** Не пугайтесь, вам достаточно изучить одну задачу… но можно и все.
 +
**** Не «книга, толщиной защищающая от прочтения»
 +
* Там (см. беджики-ссылки)
 +
** Постановки
 +
** Наброски ноутбуков для всех задач в [[Lab17]]
 +
** Частично готовая модель
 +
**** тестовые данные (генератор)
 +
**** визуализация
 +
**** сведение к ЦЛП через Pyomo
 +
**** сведение с 3SAT к задаче
 +
**** вероятностное тестирование
 +
**** видео с разьяснениями
  
−
* Надо решить 2 задачи
+
==== Начать с простого . ====
−
** Если красиво и понятно оформлено — бонусные очки (если задача окажется сложной — тоже).
+
* [[Hardprob/Maximum Set Packing]]
 +
* [[Hardprob/Minimum Set Covering]]
 +
* [[Hardprob/Maximum Cut]]
 +
* [[Hardprob/Maximum Set Splitting]]
  
−
* Выбирайте задачи из [[Open Classic Hard Problems]], переходите к редактированию по «Беру…» → 
 
−
* Зарезервированные задачи просто помечаются в том же списке, для простоты.
 
  
 +
==== Ваш квест . ====
 +
* Pyomo-сведение к ЦЛП → {{has-pyomo-model}}, {{has-testdata-and-visualization}}
 +
* 3SAT-сведение к задаче → {{has-npc-reduction}}
 +
* Вероятностное тестирование → {{add-random-fuzzing-tests}}
 +
* Можно
 +
** все для одной задачи,
 +
** можно для разных (исправление ошибки или улучшение — ОК)
  
−
* Как поотлаживаться локально через VSCode — потом
+
==== Как с этим работаем . ====
−
** отладить установку зависимостей.
+
* Выбирайте задачи из [[Open Classic Hard Problems]], переходите к редактированию по «Беру…» → 
−
 
+
** Зарезервированные задачи просто помечаются в том же списке, для простоты.
−
* Параллельно можно смотреть [https://software.sandia.gov/downloads/pub/pyomo/Pyomo-Workshop-Summer-2018.pdf воркшоп по Pyomo]
+
** Воркфлоу «взятия задачи» аналогичен блоку «[[Практикуемся_В_Алгоритмах]]»
−
** Там будет видео в каждом питон-ноутбуке.
+
** Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в [[Lab17]].
−
* Оформляем свои ноутбуки в папке «[https://discopal-lab.0x1.tv/projects/3b41be68-a970-4f60-9138-1aa73f8ee1fa/files/advalg-2022-homeworks/?session=default advalg-2022-homeworks]»
+
* Всего должно хватать в нашем [[Lab17]]
 +
* Как поотлаживаться локально через VSCode — потом.

Версия 12:34, 24 апреля 2023

S5-ispras-preview.png
Slide Show
Заголовок

Моделирование труднорешаемых задач
Автор
Стас Фомин
Нижний колонтитул
Моделирование труднорешаемых задач
Дополнительный нижний колонтитул

Стас Фомин, 15:10, 11 апреля 2024

Проблема текущих подходов.

Моделирование труднорешаемых задач 2023-04-24 14-45-02 image0.png

Проблема текущих подходов к преподаванию вычислительной сложности и труднорешаемых задач:

  • «ненужная заумь для ботанов»
  • «всякой фигни как матло у нас нет, у нас проектный подход»© (день открытых дверей МФТИ).
  • множество книг, слайдов, видео и т.п. — но все как правило перепев «ГД», на досках или одноразовых веселых видео.
    • но не «живые модели»!

Результат .

  • Нет навыков проверяемых доказательств
  • Не получаются навыки работы с труднорешаемыми задачами.
    • Мучать «эвристики» и «нейросети» не приходя в сознание.
      • «Какая у вас задача» — ну мы тут «GAN» сети пробовали, вот теперь трансформеры… — Задача то какая?


Что делать?.

  • Научится формализованно формулировать
    • ЦЛП
    • 3SAT
  • Использовать решатели
    • ЦЛП (cbc, coin, SCIP, CPLEX, GUROBI, COPT, MIPT…)
    • SAT (см. SAT-Races [1]).

Тогда можно .

  • Часто решить задачу для реальных данных сходу
    • Или покрутить постановку чтобы задача решалась (релаксация бизнес-ограничений).
  • Начать тестировать
    • Алгоритмы полиномиальные в среднем
    • Приближенные алгоритмы с гарантией точности
    • Вероятностные алгоритмы
    • Эвристики
  • Доказать труднорешаемость
    • Конструктивное сведение кодом, тестирование
    • Потом статья с объяснением.

Что вы получите .

  • Навыки моделирования

→ Бизнес-аналитик-алгоритмист! (нарасхват!)

С чем работаем .

  • Настоящие классические задачи в одном месте (ГД+ВК+…)
    • Open Classic Hard Problems
      • Не пугайтесь, вам достаточно изучить одну задачу… но можно и все.
        • Не «книга, толщиной защищающая от прочтения»
  • Там (см. беджики-ссылки)
    • Постановки
    • Наброски ноутбуков для всех задач в Lab17
    • Частично готовая модель
        • тестовые данные (генератор)
        • визуализация
        • сведение к ЦЛП через Pyomo
        • сведение с 3SAT к задаче
        • вероятностное тестирование
        • видео с разьяснениями

Начать с простого .


Ваш квест .

  • Pyomo-сведение к ЦЛП → PyomoLogo.png — есть Pyomo-формулировка для ЦЛП., Data-vis-logo.png — есть тестовые данные и визуализация.
  • 3SAT-сведение к задаче → Npc-reduction-python-logo.png — есть сведение на Python NP-полной задачи к данной.
  • Вероятностное тестирование → Yes-you-can-icon.png Можно доработать — сделать Вероятностное тестирование NPC-сведения!
  • Можно
    • все для одной задачи,
    • можно для разных (исправление ошибки или улучшение — ОК)

Как с этим работаем .

  • Выбирайте задачи из Open Classic Hard Problems, переходите к редактированию по «Беру…» →
    • Зарезервированные задачи просто помечаются в том же списке, для простоты.
    • Воркфлоу «взятия задачи» аналогичен блоку «Практикуемся_В_Алгоритмах»
    • Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в Lab17.
  • Всего должно хватать в нашем Lab17
  • Как поотлаживаться локально через VSCode — потом.
Источник — «https://discopal.ispras.ru/index.php?title=Моделирование_труднорешаемых_задач&oldid=25460»