mathematical-optimization - 求解整数线性规划 : why are solvers claiming a solvable instance is infeasible?

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 +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;

两个不同的求解器声称这个可行的问题是不可行的。我是否违反了一些不成文的条件？这是怎么回事？有真正解决问题的求解器吗？

Answer 1

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

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

您遇到了 leaky abstrction .您的问题在技术上属于混合整数规划的范围，但 MIP 求解器并非旨在解决它。混合整数规划是一个 NP-Hard 问题。不可能有一个在所有输入上都能快速可靠地工作的求解器。 MIP 求解器试图很好地解决来自不同领域的问题，例如组合优化、供应链规划和网络流。它们并非旨在解决密码学问题。