Некоторые решатели MIP имеют возможность возвращать более одного решения. Эта функция управляется несколькими настройками, и если они установлены правильно, решающая программа должна возвратить все возможные способы оптимальной установки целочисленных переменных. В качестве примера приведем очень простую целочисленную программу, которая имеет 7 возможных решений, но только 3 оптимальных:
var X{1..3} binary;
minimize obj: sum{j in 1..3} X[j];
subject to con: sum{j in 1..3} j * X[j] >= 1;
CPLEX
На примере CPLEX запросим все оптимальные решения, задавая следующие параметры:
option solver cplex; option cplex_options 'poolstub=allopt populate=2 populatelim=1000 poolintensity=4 poolagap=0'; solve;
CPLEX сообщает: «Записано 3 решения из пула решений в файлы allopt1.sol ... allopt3.sol». После завершения CPLEX можно читать эти файлы с помощью следующего цикла:
for {n in 1..obj.npool} {
solution ("allopt" & n & ".sol");
display X;}
Gurobi
То же самое можно сделать в gurobi, используя следующие настройки:
option solver gurobi; option gurobi_options 'ams_stub=allopt ams_mode=2 ams_epsabs=0.5'; solve;
Опции ams_stub, ams_mode, ams_limit, ams_eps и ams_epsabs управляют записью нескольких решений Gurobi. Указание ams_stub включает эту функцию и дает имя файлам *.sol, которые будут записаны с помощью различных решений. Другие варианты влияют на количество и тип сообщаемых решений.
Например, если указано ams_stub = test и имеется 3 альтернативных решения, они будут называться test1.sol, test2.sol и test3.sol. Затем эти решения считываются в AMPL с помощью таких команд, как solution test1.sol;. Чтобы команда solution работала правильно, модель и данные должны быть настроены точно так же, как и при выполнении solve.
Можно написать цикл, которым будет проверяться, существуют ли файлы *.sol. Ниже приведен пример в операционной системе Windows, где ams_stub = poolgurobi, а amsLimit - это параметр AMPL, который был установлен равным значению ams_limit (в строке gurobi_options):
for {i in 0..amsLimit} {
shell ("if not exist poolgurobi" & i & ".sol exit 3");
if shell_exitcode = 3 then break;
else {
solution ("poolgurobi" & i & ".sol");
display Total_Cost;}}
Суффикс .npool
Интерфейс AMPL-Gurobi был обновлен в сборке от 20180601 для более удобной обработки пула решений MIP. Теперь количество сохраненных решений указывается в суффиксе .npool, и можно прочитать все решения в цикле, например:
for {i in 1..Total_Cost.npool} {
solution ("gurobipool" & i & ".sol");
display Total_Cost;}
(Total_Cost в этом примере следует заменить имя целевой функции или текущей проблемы, а вместо оператора display можно поместить любые операторы обработки, которые необходимы) Полная информация представлена ниже.
Ниже представлено описание параметров AMPL, которые отвечают за работу с альтернативными решениями:
Относительный допуск ams_eps для сообщения об альтернативных решениях MIP (по умолчанию = no limit)
Абсолютный допуск ams_epsabs для сообщения об альтернативных решениях MIP (по умолчанию = no limit)
ams_limit ограничение количества записанных альтернативных решений MIP. no limit, если ams_limit = 0 (по умолчанию)
Режим поиска ams_mode для решений MIP, когда ams_stub указан, чтобы запросить поиск нескольких альтернативных решений:
0 = игнорировать ams_stub; искать только одно оптимальное решение
1 = постараться найти дополнительные решения
2 = искать лучшие решения "ams_limit" (по умолчанию).
Заглушка ams_stub для альтернативных решений MIP, записанная в файлы с именами, полученными путем добавления «1.sol», «2.sol» и т. д. к ams_stub. На количество таких файлов влияют четыре ключевых параметра:
ams_mode указывает, сколько усилий нужно затратить;
ams_limit представляет максимальное количество записываемых файлов. Без ограничений, если ams_limit = 0 (по умолчанию);
ams_eps представляет относительную терпимость к значениям целевой функции альтернативных решений.
ams_epsabs задает значение абсолютной терпимости к тому, насколько хуже может быть значение альтернативного решения целевой функции.
Количество записанных альтернативных файлов решений MIP возвращается с суффиксом .npool для целевой функции и проблемы.
.poolgap - синоним для ams_eps;
.poolgapabs синоним для ams_epsabs;
.poolsearchmode синоним для ams_mode;
.poolsolutions синоним для ams_limit;
.poolstub синоним для ams_stub;
Печать результатов решения в файл
Рассмотрим пример, когда модель производит расчет для разных файлов данных в цикле for. Для каждой итерации цикла for мы хотим распечатать следующие данные в текстовый файл:
- Количество исследуемых ветвей и граничных узлов;
- Разрыв оптимальности в случаях, когда решающая программа не завершает работу за отведенное время;
- Разрыв релаксации линейного программирования.
Рассмотрим вариант записи для решателя CPLEX:
- После решения CPLEX сообщает о количестве исследованных узлов в коротком сообщении:
CPLEX 20.1.0.0: optimal integer solution; objective 235625 308 MIP simplex iterations 50 branch-and-bound nodes
Это сообщение также сохраняется во встроенном параметре solve_message. Можно использовать следующее выражение для извлечения количества узлов из сообщения решения:
num0(substr(solve_message,match(solve_message,"s\n")+2))
- Сообщим CPLEX, что нужно вернуть значения разрыва оптимальности, установив:
option cplex_options 'return_mipgap = 3';
(или, если ранее уже был задан cplex_options, нужно добавить к ней return_mipgap= 3). Это позволит получить значения разрыва оптимальности MIP в выражениях <obj>.relmipgap и <obj>.absmipgap - где <obj> - фактическое имя целевой функции.
- Затем необходимо решить модель заново, добавив значение nodelim = 0 к указанной выше строке cplex_options, чтобы получить значения разрыва в конце обработки корневого узла.
Запись в файл значений нескольких решений
Другой пример описывает ситуацию, когда у нас имеется набор из N файлов *.run, (amp1.run, amp2.run, ... ampN.run). Каждый из них читает один и тот же файл *.mod, но используют разные наборы данных. Нам необходимо написать сценарий, который автоматически выполняет все эти N файлов *.run и сохраняет оптимальное значение целевой функции (MTCH) для каждого из этих файлов.
param n := 50;
param res {1..n};
for {i in 1..n} {commands ("amp" & i & ".run");
let res[i] := MTCH; }
Внутри каждого файла amp1.run, amp2.run и т. д. необходимо указать соответствующие команды для указания новых данных и повторного решения.
Еще один пример в тему:
param nruns := 5; #number of iterations
param optvalue {1..nruns};
var var1;
var var2;
for {k in 1..nruns} {
reset
data var1;
reset
data var2;
solve;
display var1 > solution.txt;
display var2 > solution.txt;}
В качестве альтернативы добавлению операторов печати можно рассмотреть возможность использования функции AMPL, которая позволяет выполнять пошаговое выполнение файла по одному оператору за раз, используя операторы display или print для отображения значений параметров по мере продвижения.
