Дискретная оптимизация: большое количество оптимальных решений
TL; версия DR: есть ли способ справиться с проблемами оптимизации, когда существует большое количество оптимальных решений (решений, которые находят наилучшее объективное значение)? То есть найти оптимальное решение довольно быстро (но, очевидно, сильно зависит от размера проблемы), но существует множество таких решений, так что решатель бесконечно работает, пытаясь найти лучшее решение (бесконечно, потому что он находит другие возможные решения, но с объективным значением, равным текущему лучшему).
Не TL; версия DR: для университетского проекта мне нужно реализовать планировщик, который должен выводить расписание для каждой университетской программы за год обучения. Мне предоставлены некоторые данные, и по этому вопросу я просто буду придерживаться общего, но не столь редкого примера.
Во многих разделах у вас есть обязательные курсы и дополнительные курсы. Иногда эти факультативные курсы делятся на модули, и студент должен выбрать один из этих модулей. Часто им приходится выбирать два модуля, но некоторые комбинации возникают чаще, чем другие. Очевидно, что если вы посчитаете количество курсов (обязательных + необязательных) без учета разделения на модули, у вас будет больше курсов, чем временных интервалов, в которых они должны быть запланированы. Моя модель довольно проста. У меня есть ограничения, утверждающие, что каждый курс должен быть запланирован на один и только один интервал времени (период 2 часа), и что профессор не должен давать два курса одновременно. Это жесткие ограничения. Дело в том, что в идеальном мире я должен добавить жесткие ограничения, утверждающие, что студент не может иметь два курса одновременно. Но поскольку у меня недостаточно данных и что каждая комбинация модулей возможна, нет смысла создавать по одному обязательному студенту на каждую комбинацию + модуль 1 + модуль 2 и применять жесткие ограничения для каждого из этих студентов, поскольку в основном это идентично иметь одного студента (обязательный + все дополнительные) и пытаться соответствовать жестким ограничениям - которые потерпят неудачу.
Вот почему я решил перенести эти жесткие ограничения в задачу оптимизации. Я просто определяю свою целевую функцию, сводя к минимуму для каждого студента количество курсов, которые он / она проходит, которые запланированы одновременно.
Если я использую эту простую модель только с одним студентом (22 курса) и 20 временными интервалами, у меня должно быть объективное значение 4 (так как 2 временных интервала включают каждые 2 курса). Но, используя Gurobi, расслабленная цель равна 0 (так как вы можете иметь долю курсов в пределах временного интервала). Следовательно, когда решатель достигает решения с затратами 4, он не может непосредственно доказать оптимальность. Настоящая проблема заключается в том, что для этого простого случая существует огромное количество оптимальных решений (22! Возможно...). Поэтому, чтобы доказать оптимальность, он будет проходить через все другие решения (которые имеют ту же цель), отчаянно пытаясь найти решение с меньшим зазором между релаксированной целью (0) и текущей (4). Очевидно, такого решения не существует...
У вас есть идеи о том, как я могу решить эту проблему? Я подумал о том, чтобы проанализировать существующую базу данных и попытаться выяснить, какие комбинации модулей с большой вероятностью могут произойти, чтобы я мог отменить жесткие ограничения, но это кажется опасным (возможно, я выберу комбинацию, которая приводит к конфликту, поэтому не могу найти какой-либо решение или пропуск действительной комбинации). Текущее решение, которое я использую, устанавливает временной порог, чтобы остановить оптимизацию...