Hardprob/Maximum Directed Cut — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
---- | ---- | ||
{{hard-problem-on-lab17|{{PAGENAME}}}} | {{hard-problem-on-lab17|{{PAGENAME}}}} | ||
| − | + | {{has-testdata-and-visualization}} | |
| − | + | {{has-pyomo-model}} | |
<!-- * {{has-npc-reduction}} --> | <!-- * {{has-npc-reduction}} --> | ||
<!-- * {{add-random-fuzzing-tests}} --> | <!-- * {{add-random-fuzzing-tests}} --> | ||
Версия 06:24, 17 апреля 2023
- Направленный граф .
- Найти разбиение V на непересекающиеся множества и .
- Максимизировать размер разреза, т.е. число дуг, которые стартуют в , и заказчиваются в .
Код в «maximum-directed-cut.ipynb» на гитлаб или
живьем в лабе
— есть тестовые данные и визуализация.
— есть Pyomo-формулировка для ЦЛП.