оптимизация — ускорить код CPLEX C ++
Это результат внедрения моей самой первой модели в CPLEX C ++, и я очень удивлен, насколько медленным и плохим является качество. Я верю, что большей части этого можно избежать с помощью лучшей формулировки. Может кто-нибудь помочь мне улучшить код, пожалуйста? Подсказки, идеи, мысли … все ценится!
Речь идет о планировании экзаменов в течение 5 дней, каждый из которых имеет 2 временных интервала. Мой ввод — это количество экзаменов (первое число в первом ряду) и конфликтующих пар экзаменов (второе число в первом ряду), где я также знаю количество студентов, сдающих оба экзамена (в следующих строках -> экзамен1 экзамен2 # студенты, сдающие оба экзамена)
Код, который вы можете найти Вот и экземпляр Вот.
Ограничения, которые я включаю:
- каждый экзамен назначается ровно один раз
- противоречивые экзамены не могут быть запланированы на тот же период
- оштрафовать, если в тот же день назначены конфликтующие экзамены
- штрафовать, если противоречивые экзамены запланированы на последовательные дни
- штрафовать, если конфликтующие экзамены запланированы на смежные периоды в течение ночи
У меня такое ощущение, что что-то не так в формулировке, потому что я не могу себе представить, что ценность объективной ценности настолько высока. Кто-нибудь видит недостаток? Я застрял.
Проблема может быть в цикле, где я пытаюсь выяснить, нарушено ли мягкое ограничение или нет. Там я зацикливаюсь на дни, но, вероятно, я все время случайно перезаписываю свои переменные. У кого-нибудь есть идеи, как определить двоичную переменную, указывающую, нарушается ли мягкое ограничение в какой-либо день (и, конечно, это может произойти только один раз, но, скорее всего, это не в конце).
Решение
Вместо того, чтобы отлаживать код C ++, я просто заново реализовал модель, используя язык моделирования (я считаю, что это более быстрый и приятный способ провести вечер воскресенья).
(Примечание: обновлено после исправления ошибки). Вот мое решение с общим штрафом 751:
Вы должны быть в состоянии вставить это в свой код и проверить результаты.
Примечание: на старом ноутбуке потребовалось около 900 секунд, чтобы доказать оптимальность с Cplex. Если вы хотите просто хорошее решение, вы можете остановиться немного раньше:
(Синяя линия является целью, а красная линия — наилучшей из возможных границ). Чтобы добиться хорошей производительности, я немного помог Cplex с настройкой приоритетов ветвления и использованием некоторых опций, предложенных при настройке.
Другие решения
Других решений пока нет …