线性规划的变体？

Question

我正在尝试找到解决以下问题的现有算法：

也就是说，假设我们有 3 个变量，x、y、z（都必须是整数）。我想找到必须匹配某些约束的所有变量的值，例如 x+y<4、x<=50、z>x 等

此外，还有额外的 POSSIBLE 约束，如 y>=20 等（与之前相同）。 objective 函数（我有兴趣最大化它的值）是在最优解中满足的额外约束的数量（“必须”约束 + 所有值都是整数的事实，是一个需求。没有它，就没有有效的解决方案。

Answer 1

如果使用 OR-Tools，因为模型是完整的，我会推荐使用 CP-SAT，因为它提供了一个很好的指标约束 API。

API 将是：

b = model.NewBoolVar('indicator variable')
model.Add(x + 2 * y >= 5).OnlyEnforceIf(b)

...

model.Maximize(sum(indicator_variables))

为了获得最佳性能，我建议使用并行机制。

solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True
solver.parameters.num_search_workers = 8  # or more on a bigger computer
status = solver.Solve(model)

线性规划的变体？

Variation on linear programming?

python

algorithm

linear-programming

or-tools