解决整数线性规划问题：为什么求解器声称可解实例是不可行的？

Question

我正尝试解决整数规划问题。我已经尝试使用SCIP和LPSolve

例如，给定A和B的最终值，我想解决以下C#代码中的valA：

Int32 a = 0, b = 0;
a = a*-6 + b + 0x74FA - valA;
b = b/3 + a + 0x81BE - valA;
a = a*-6 + b + 0x74FA - valA;
b = b/3 + a + 0x81BE - valA;
// a == -86561, b == -32299

我将其实现为lp格式的整数规划（截断除法会引起一些复杂性）：

min: ;
+valA >= 0;
+valA < 92;
remAA_sign >= 0;
remAA_sign <= 1;
remAA <= 2;
remAA >= -2;
remAA +2 remAA_sign >= 0;
remAA +2 remAA_sign <= 2;
remAA [phone] remAA_range >= -2147483648;
remAA [phone] remAA_range <= 2147483647;
remAA [phone] remAA_range [phone] remAA_sign >= 0;
remAA [phone] remAA_range [phone] remAA_sign <= 2147483648;
-1 remAA [phone] remAA_range +3 remAA_mul3 = 0;
remAB_sign >= 0;
remAB_sign <= 1;
remAB <= 2;
remAB >= -2;
remAB +2 remAB_sign >= 0;
remAB +2 remAB_sign <= 2;
remAB [phone] remAB_range >= -2147483648;
remAB [phone] remAB_range <= 2147483647;
remAB [phone] remAB_range [phone] remAB_sign >= 0;
remAB [phone] remAB_range [phone] remAB_sign <= 2147483648;
[phone] remAA +1 offA -2 valA +1 offB -1 remAB [phone] remAB_range +3 remAB_mul3 = 0;
a = -86561;
b = -32299;
offA = 29946;
offB = 33214;
-4 offA +3 valA [phone] remAA +1 offB [phone] Fa - a = 0;
[phone] remAA -1431655769 offA -1431655764 valA -1431655763 offB [phone] remAB [phone] Fb - b = 0;
int valA;
int remAA;
int remAA_range;
int remAA_sign;
int remAA_mul3;
int remAB;
int remAB_range;
int remAB_sign;
int remAB_mul3;
int Fa;
int Fb;
int offA;
int offB;
int a;
int b;

然后试图解决它：

The model is INFEASIBLE

但是我知道有一个可行的解决方案，因为我知道一种有效的变量赋值方法。 添加以下条件会导致找到一个解决方案:

a = -86561;
b = -32299;
offA = 29946;
offB = 33214;
valA = 3;
remAA = 0;
remAA_range = 0;
remAA_sign = 0;
remAA_mul3 = 0;
remAB = 1;
remAB_range = 0;
remAB_sign = 0;
remAB_mul3 = -21051;
Fa = 0;
Fb = 21054;

两个不同的求解器声称这个可行问题是不可行的。我是否违反了某些未写下的条件？发生了什么？有没有实际解决问题的求解器？

- Craig Gidney

---

如果您构建了模型，请导出.lp文件并将其发送给我，我将通过CPLEX运行它。它具有良好的冲突（不可行性）信息。我的电子邮件地址是我的用户名@gmail.com。我想您也可以将其放在Pastebin或类似的网站上。 - user327301

@raoul 我已经通过电子邮件发送了我在 SCIP 中使用的 lp-cplex 文件。 - Craig Gidney

我使用CPLEX解决了这个问题，而且是可行的。最优解的目标函数值为零。这与LP松弛相同，其基础矩阵的条件数（kappa）为3.4。在额外的约束条件下，目标函数仍然相同；条件数为4.6。我不确定CPLEX在处理这个特定问题时与SCIP有何不同。您能否使用neos-server.org解决您的模型并使用CPLEX？ - user327301

我下载了cplex的试用版，它确实可以解决问题。不幸的是，在我想要解决的实际困难问题上，我超出了有效范围。我认为它们并不适用于模运算。 - Craig Gidney

什么东西不是为模运算而设计的？ - user327301

MIP求解器。原则上，它们可以识别像x + someNewInt*2^32 = y这样的方程，将其视为等价于x = y (mod 2^32)，从而避免处理可能非常巨大的someNewInt值。但在实践中，它们并不这样做，因此someNewInt超过了内部限制，导致求解器失败。 - Craig Gidney

Answer 1

MIP求解器使用浮点数据。对于像您的问题这样存在数据幅度范围很大的情况，这会导致舍入误差。任何线性规划(LP)求解器都必须对这些数据执行操作，这可能会放大问题。在您的问题等某些情况下，这可能会使求解器得出问题不可行的结论，而实际上却是可行的。当您固定变量时，求解器执行的浮点运算就会更少。

商业求解器例如Gurobi或 cplex通常能够更好地处理像您一样数值复杂的数据。Gurobi有一个参数 QuadPrecision ，可与高精度浮点数一起使用。大多数求解器都有一个参数，可以使其更好地处理数值困难的数据。例如LPSolve有一个参数 epsint ，它将使其放宽对整数的定义。该参数的默认值为10e-7，因此0.9999999将被视为整数，但0.9999998则不会。您可以增加该值，但风险是可能会收到无法接受的结果。

您遇到了漏洞的抽象问题。您的问题从技术上属于混合整数规划范畴，但MIP求解器并非为解决该问题而设计。混合整数规划是一个NP难问题。没有一种求解器能够快速、可靠地处理所有输入。MIP求解器尝试处理来自不同领域的问题，例如投资组合优化、供应链规划和网络流。它们并非为解决密码学问题而设计。

- David Nehme

Answer 2

您也可以看一下 SCIP 3.1.0 版本，特别是它的扩展精度算术功能。使用 GMP，线性规划解决方案可以计算到非常高的精度。

- mattmilten