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

Question

我使用 PuLP 创建了一个 objective 和约束，它给出了最优解（最大化），这很棒。

但是，了解接下来的几个并非绝对最佳的解决方案对我很有用。本质上，我想执行以下操作...

求解 LP 并获得最大 objective 值（我这样做了）
在未来的解决方案中使用这个最大值作为约束来限制objective值
重复过程多次，每次降低最大objective值

求解后，我尝试在不等式中添加使用 objective 方程的约束（限制 objective 的最大值），但出现此错误：

UserWarning: Overwriting previously set objective.

此外，新解决方案的 objective 为 "None"。我读到当您不小心创建了一个没有不等式的约束时，经常会出现这个错误。我的约束肯定有不等式。

有没有我不知道的更好的方法？

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

我收到警告的原因是因为我的新约束是不带等号的不等式。

I had to change "<" to "<=".

改变这一点就摆脱了警告。

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

<= float(value(new_model.objective)) - 0.01

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

所以，我想出了一个不同的方法。我不允许创建当前解决方案的相同五个配对出现在另一个解决方案中。这样，解决方案就不会重复。每次迭代后，我将五对的二元变量值相加。（这些二元变量表示该配对是否存在于当前解中。）我不希望所有五个再次一起出现（这将是一个重复的解），所以我创建了一个约束以确保它们的总和小于五。值为 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 将再次允许相同的解决方案。

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

How to find next best (suboptimal) solutions using PuLP?

python

linear-programming

pulp