问题 求解整数线性程序:为什么求解可解的实例的求解器是不可行的?


我正在尝试解决整数编程问题。我试过两种用途 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 +4294967296 remAA_range >= -2147483648;
remAA +4294967296 remAA_range <= 2147483647;
remAA +4294967296 remAA_range +2147483648 remAA_sign >= 0;
remAA +4294967296 remAA_range +2147483648 remAA_sign <= 2147483648;
-1 remAA +4294967296 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 +4294967296 remAB_range >= -2147483648;
remAB +4294967296 remAB_range <= 2147483647;
remAB +4294967296 remAB_range +2147483648 remAB_sign >= 0;
remAB +4294967296 remAB_range +2147483648 remAB_sign <= 2147483648;
+1431655765 remAA +1 offA -2 valA +1 offB -1 remAB +4294967296 remAB_range +3 remAB_mul3 = 0;
a = -86561;
b = -32299;
offA = 29946;
offB = 33214;
-4 offA +3 valA +1431655765 remAA +1 offB +4294967296 Fa - a = 0;
+477218588 remAA -1431655769 offA -1431655764 valA -1431655763 offB +1431655765 remAB +4294967296 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;

两个不同的求解者声称这个可行的问题是不可行的。我是否违反了一些不成文的条件?这是怎么回事?是否有解决方案实际解决问题?


1268
2018-04-14 16:37


起源

如果您构建模型,导出.lp文件并将其发送给我,我将通过CPLEX运行它。它具有良好的冲突(不可行性)信息。我的电子邮件地址是我在gmail dot com上的用户名。我想你也可以把它放在Pastebin或类似的东西上。 - raoulcousins
@raoul我已经通过电子邮件发送了我用scip的lp-cplex文件。 - Craig Gidney
我用CPLEX解决了它,这是可行的。最优解具有零目标函数值。这与LP弛豫相同,其具有条件数(kapp)为3.4的基础矩阵。在额外的约束下,目标函数是相同的;条件数为4.6。对于这个特定问题,我不确定CPLEX在SCIP下做了哪些与SCIP不同的事情。你能用neos-server.org解决你的模型并使用CPLEX吗? - raoulcousins
我抓住了cplex的试用版,它确实解决了它。不幸的是,我超出了我想要解决的实际难题的有效范围。我不认为它们是为模数运算而设计的。 - Craig Gidney
MIP求解器。原则上,他们可以将x + someNewInt * 2 ^ 32 = y等方程式识别为等于x = y(mod 2 ^ 32),从而避免处理someNewInt可能非常大的值。实际上它们没有,因此一些新的超出内部限制并导致求解器失败。 - Craig Gidney


答案:


MIP求解器使用浮点数据。对于像你这样的问题,数据量的变化很大,这会导致舍入错误。任何LP解算器都必须对此数据执行操作以放大问题。在某些情况下,例如你的问题,这可以使解算器得出结论,当问题不可行时,问题是不可行的。修复变量时,解算器会执行较少的浮点运算。

商业解决方案解决者喜欢 Gurobi 或者cplex通常可以更好地处理像你这样的数字困难数据。 Gurobi有一个参数 QuadPrecision 适用于更高精度的浮点数。大多数求解器都有一个参数,可以使数值困难的数据使求解器工作得更好。例如,LPSolve有一个参数 epsint 这将使它放松它认为整数。参数的默认值为10e-7,因此0.9999999将被视为整数,但0.9999998将不是。您可以使此值更大,但您可能会收到不可接受的结果。

你正在经历一个 泄漏吸收。您的问题在技术上属于混合整数规划的范围,但MIP求解器并非旨在解决它。混合整数规划是NP-Hard问题。在所有输入上都不可能有一个快速可靠地工作的求解器。 MIP求解器可以很好地解决来自组合优化,供应链计划和网络流程等不同领域的问题。它们不是为解决密码学问题而设计的。


14
2018-04-14 20:54





您还可以查看SCIP 3.1.0,特别是其扩展的精度算术功能。使用GMP可以高精度地计算LP解决方案。


0
2018-03-28 14:12