Несколько решений с 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, вы должны получить различные бинарные решения.

Другие вопросы по тегам