12

我正在尝试解决整数规划问题。我已经尝试过使用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;

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

4

2 回答 2

16

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

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

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

于 2013-04-14T20:54:54.537 回答
0

您还可以查看 SCIP 3.1.0，尤其是它的扩展精度算术功能。使用 GMP 可以以非常高的精度计算 LP 解。

于 2014-03-28T14:12:15.537 回答