求解整数线性规划问题：为什么求解声称可解决的情况下是不可行的？(Solving an integer

我试图解决整数规划问题。 我都试过使用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;

两种不同的求解器都声称这是可行的问题是不可行的。 我是不是违反某些不成文的条件？ 这是怎么回事？ 是否有解决者，实际上解决这个问题？

Answer 1:

MIP求解浮点数据的工作。 对于诸如具有在数据幅度较大变化你的问题，这会导致舍入误差。 任何LP求解器将不得不对这个数据，可以放大问题进行操作。 在某些情况下，像你的问题，这可以使求解得出结论，问题是不可行时，它不是。 当你修复变量求解做更少的浮点运算。

商业求解求解像Gurobi或CPLEX一般做像你这样数字很难数据的工作做得更好。 Gurobi有一个参数QuadPrecision ，具有较高精度浮点数的作品。 大多数求解器有一个参数，这将使求解器工作，数控机床，很难数据好。 例如LPSolve有一个参数epsint ，这将使它放松一下它认为一个整数。 该参数默认为10E-7，所以0.9999999会被认为是一个整数，但0.9999998不会。 您可以将此值较大，但风险接受不能接受的结果。

您遇到漏水abstrction 。 你的问题是技术上的混合整数规划的范围，但MIP求解器没有被设计来解决这个问题。 混合整数规划是一个NP-Hard问题。 这是不可能有快速，可靠地适用于所有输入的求解。 MIP求解尝试对来自像投资组合优化，供应链规划，以及网络流量不同领域的问题很好地工作。 它们不是设计来解决密码学的问题。

Answer 2:

你也可以看看SCIP 3.1.0，特别是它的扩展精度运算功能。 使用GMP的LP解决方案可以计算到非常高的精度。

文章来源: Solving an integer linear program: why are solvers claiming a solvable instance is infeasible?