首页 文章

求解整数线性程序：为什么求解可解的实例的求解器是不可行的？

提问于
浏览 次
11

我'm trying to solve integer programming problems. I' ve试过两个都使用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

但是，我知道有一个可行的解决方案，因为我知道一个有效的变量赋值 . Adding 以下条件导致找到解决方案：

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;

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

mathematical-optimization cplex gurobi integer-programming scip

2 回答

  • 15

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

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

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

    回复于
  • 0

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

    回复于

相关问题