1

我正在尝试使用 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。

4

1 回答 1

1

您获得分数解决方案的事实表明您正在解决松弛问题而不是 MIP 问题。例如，如果您使用不支持 MIP 的求解器（例如 MINOS），则可能会发生这种情况，通常它会给您这样的警告：

MINOS 5.51: ignoring integrality of 5 variables

你得到相同的解决方案，因为约束Exclude只适用于二元解决方案。如果您使用诸如 CPLEX 或 Gurobi 之类的 MIP 求解器，您应该得到不同的二元解。

于 2015-10-25T16:50:28.750 回答