如何使用PuLP找到下一个最佳（次优）解决方案？

Question

我使用PuLP创建了一个目标和约束，它提供了最佳解决方案（最大化），这很棒。

但是，对我来说，了解下面几个不是绝对最好的解决方案对我很有帮助。基本上，我想做以下......

1. 解决LP并获得最大客观价值（我做了这个）
2. 使用此最大值作为约束来限制未来解决方案中的目标值
3. 重复过程多次，每次降低最大目标值

解决之后，我尝试添加一个使用不等式中的客观方程的约束（限制目标的最大值），但是我得到了这个错误：

UserWarning：覆盖先前设定的目标。

此外，新解决方案的目标是“无”。我已经读过，当你意外地创建一个没有不等式的约束时，这个错误经常会出现。我的约束肯定有不平等。

有没有更好的方法来做我不知道的事情？

new_model = pulp.LpProblem("NBA stats optimizer", LpMaximize)

# create binary lpVariables for every pairing
pfs = [LpVariable("pf{}".format(i+1), cat="Binary") for i in range(len(pf_pairs))]
sfs = [LpVariable("sf{}".format(i+1), cat="Binary") for i in range(len(sf_pairs))]
pgs = [LpVariable("pg{}".format(i+1), cat="Binary") for i in range(len(pg_pairs))]
sgs = [LpVariable("sg{}".format(i+1), cat="Binary") for i in range(len(sg_pairs))]
cs = [LpVariable("c{}".format(i+1), cat="Binary") for i in range(len(c_singles))]

# add objective
new_model += sum(x1 * pts1 for x1,pts1 in zip(pfs, [row[0] for row in pf_pairs])) \
             + sum(x2 * pts2 for x2,pts2 in zip(sfs, [row[0] for row in sf_pairs])) \
             + sum(x3 * pts3 for x3,pts3 in zip(pgs, [row[0] for row in pg_pairs])) \
             + sum(x4 * pts4 for x4,pts4 in zip(sgs, [row[0] for row in sg_pairs])) \
             + sum(x5 * pts5 for x5,pts5 in zip(cs, [row[0] for row in c_singles]))

# create a constraint that each set of pairings has only 1 group at a time
new_model += lpSum([pfs[i] for i in range(len(pf_pairs))]) == 1, "pfLimit"
new_model += lpSum([sfs[i] for i in range(len(sf_pairs))]) == 1, "sfLimit"
new_model += lpSum([pgs[i] for i in range(len(pg_pairs))]) == 1, "pgLimit"
new_model += lpSum([sgs[i] for i in range(len(sg_pairs))]) == 1, "sgLimit"
new_model += lpSum([cs[i] for i in range(len(c_singles))]) == 1, "cLimit"

status = new_model.solve()

new_model += (sum(x1 * pts1 for x1,pts1 in zip(pfs, [row[0] for row in pf_pairs])) \
              + sum(x2 * pts2 for x2,pts2 in zip(sfs, [row[0] for row in sf_pairs])) \
              + sum(x3 * pts3 for x3,pts3 in zip(pgs, [row[0] for row in pg_pairs])) \
              + sum(x4 * pts4 for x4,pts4 in zip(sgs, [row[0] for row in sg_pairs])) \
              + sum(x5 * pts5 for x5,pts5 in zip(cs, [row[0] for row in c_singles]))) \
              < float(value(new_model.objective))

status = new_model.solve()

Answer 1

我收到警告的原因是因为我的新约束是一个没有等号的不等式。

我不得不将“<”更改为“<=”。

改变这一件事摆脱了警告。

但是，添加“<=”不等式意味着我的约束不会限制每次迭代的目标值。 （它可以一遍又一遍地返回相同的目标值。）我接下来在不等式右侧的约束中添加了一个小的减量...

<= float（value（new_model.objective）） - 0.01

但是，@ sascha的评论很好，添加“ - 0.01”会强制解算器跳过两个具有相同目标值的不同解决方案。

所以，我想出了一个不同的方法。我不允许创建当前解决方案的相同五个配对在另一个解决方案中一起出现。这样，解决方案就不会重复。在每次迭代之后，我总结了五个配对的二进制变量值。 （这些二进制变量表明当前解决方案中是否存在此配对。）我不希望所有五个再次出现在一起（这将是一个重复的解决方案），因此我创建一个约束以确保它们的总和小于五。值为5表示所有这些都再次出现。新约束采用以下形式：

new_model + = pfs [cur_pf_group] + sfs [cur_sf_group] + pgs [cur_pg_group] + sgs [cur_sg_group] + cs [cur_c_group] <= 4.9

这里4.9优于5，因为我们只需要总和为4或更少。在这里使用5将再次允许相同的解决方案。