Несколько решений с AMPL
Я пытаюсь использовать AMPL для моделирования проблемы, и я хочу иметь возможность увидеть альтернативы или несколько "оптимальных или почти оптимальных" решений.
Я читаю на этом сайте: http://orinanobworld.blogspot.com/2011/02/finding-multiple-solutions-in-binary.html
Я пытался приспособить этот тип вещи к моей собственной модели
и попытался реализовать что-то вроде следующего:
set RECORDS; # items available to choose from
var Picked {RECORDS} binary; # the variables that were set to 1 for "picked"
#other conditions and model constraints....
# we now create some structure to record multiple solutions
param want := 5; # number of solutions we want
param nfound default 0; # number of solutions found
set ALTS {1..100} in {RECORDS}; # records which items were packed (and where) in each solution
# we add constraints to the previous model to exclude solutions we've already seen
s.t. Exclude {s in 1..nfound}:
sum {i in ALTS[s]} (1 - Picked[i]) + sum {j in {RECORDS} diff ALTS[s]} Picked[j] >= 1;
# solve until either the problem becomes infeasible or the right number of solutions have been found
for {s in 1..want} {
solve; # solve the model
if solve_result = 'infeasible' then break; # if the model has become infeasible, give up
#packed is getting the value of players that are in a lineup that have a "1" (>.5)
let ALTS[s] := {i in RECORDS : Picked[i] > 0.5};
let nfound := s; # bump the counter for solutions found
display s;
display ALTS[s];
}
Когда я запускаю свою модель, используя этот код, она дает мне 5 точно таких же решений. Что я делаю неправильно? В качестве отдельной проблемы, это также похоже на Picked
также получает некоторые недвоичные значения, установленные в нем (например, 0,7235), хотя я думал, что установка его в двоичное значение ограничит его значением 1 или 0.
1 ответ
Тот факт, что вы получаете дробное решение, предполагает, что вы решаете проблему релаксации, а не проблемы MIP. Это может произойти, например, если вы используете солвер, который не поддерживает MIP, такой как MINOS, и обычно он выдает следующее предупреждение:
MINOS 5.51: ignoring integrality of 5 variables
И вы получаете идентичные решения, потому что ограничение Exclude
работает только для бинарных решений. Если вы используете MIP-решатель, такой как CPLEX или Gurobi, вы должны получить различные бинарные решения.