linear-programming - 为已知解决方案添加约束会导致越界异常

Question

我有一个线性优化目标来最大化 EE+FF，其中 EE 和 FF 每个都包含一些 C 和 D。

使用我编写的代码，我可以让求解器找到:

EE_quantity: 0, FF_quantity: 7

...但我知道还有另一种解决方案:

EE_quantity: 1, FF_quantity: 6

为了验证其他有效解决方案的用户输入，我为 EE 和 FF 添加了约束。所以我在下面的代码中添加了 EE_quantity == 0, FF_quantity == 7，这是一个可运行的例子:

SolverContext c2 = SolverContext.GetContext();
Model m2 = c2.CreateModel();
p.elements = elements_multilevel_productmix();

Decision C_quantity = new Decision(Domain.IntegerNonnegative, "C_quantity"); 
Decision D_quantity = new Decision(Domain.IntegerNonnegative, "D_quantity");
Decision EE_quantity = new Decision(Domain.IntegerNonnegative, "EE_quantity");
Decision FF_quantity = new Decision(Domain.IntegerNonnegative, "FF_quantity");
m2.AddDecisions(C_quantity, D_quantity, EE_quantity, FF_quantity);

m2.AddConstraints("production",
    6 * C_quantity + 4 * D_quantity <= 100,
    1 * C_quantity + 2 * D_quantity <= 200,
    2 * EE_quantity + 1 * FF_quantity <= C_quantity,
    1 * EE_quantity + 2 * FF_quantity <= D_quantity,
    EE_quantity == 0,
    FF_quantity == 7
);
m2.AddGoal("fixed_EE_FF", GoalKind.Maximize, "EE_quantity + FF_quantity");

Solution sol = c2.Solve(new SimplexDirective());             
foreach (var item in sol.Decisions)
{
    System.Diagnostics.Debug.WriteLine(
        item.Name + ": " + item.GetDouble().ToString()
    );
}

看来 Solver Foundation 真的不喜欢这种特定的组合。使用 EE_quantity == 1, FF_quantity == 6 没问题，仅使用 EE_quantity == 0 或 FF_quantity == 7 也一样。但是同时使用两者，并且其中之一为零，会引发异常:

Index was outside the bounds of the array.

引擎盖下发生了什么？我如何指定我想为特定问题找到“所有”解决方案？

Answer 1

(注意:不会发布新的 Solver Foundation 版本 - 它基本上已被 Microsoft 放弃。)

堆栈跟踪表明这是单纯形求解器预求解例程中的错误。遗憾的是，SimplexDirective 无法禁用预求解(与InteriorPointDirective 不同)。因此解决这个问题的方法是不同地指定固定变量。

删除设置 EE_quantity 和 FF_quantity 的最后两个约束，而是在创建 Decision 对象时将上限和下限分别设置为 0 和 7。这等同于您想表达的内容，但似乎避免了 MSF 错误:

Decision EE_quantity = new Decision(Domain.IntegerRange(0, 0), "EE_quantity");
Decision FF_quantity = new Decision(Domain.IntegerRange(7, 7), "FF_quantity");

与许多混合整数求解器一样，MSF 单纯形求解器仅返回最优解。如果您希望 MSF 返回所有解决方案，请更改为约束规划求解器 (ConstraintProgrammingDirective)。如果您查看 Solution.GetNext() 的文档，您应该知道如何执行此操作。

当然，CP 求解器不能保证立即生成全局最优解。但如果您迭代解决方案的时间足够长，您就会到达那里。