求解整数线性程序:为什么求解器声称不存在可求解的实例?

问题描述

我正在尝试解决整数编程问题.我已经尝试使用 SCIP 和 LPSolve

I'm trying to solve integer programming problems. I've tried both use SCIP and LPSolve

例如，给定A和B的最终值，我想在以下C#代码中求解valA:

For example, given the final values of A and B, I want to solve for valA in the following C# code:

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格式实现为该整数程序(截断除法会带来一些麻烦):

Which I implemented as this integer program in lp format (the truncating division causes a few complications):

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

但是，我知道有一个可行的解决方案，因为我知道一个有效的变量分配. 添加以下条件将导致找到解决方案:

However, I know that there is a feasible solution because I know a variable assignment that works. Adding the following conditions causes a solution to be found:

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;

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

Two different solvers have claimed this feasible problem is infeasible. Am I violating some unwritten condition? What's going on? Are there solvers that actually solve the problem?

推荐答案

MIP求解器可处理浮点数据.对于诸如您这样的问题，这些问题的数据大小存在很大差异，这会导致舍入误差.任何LP解算器都必须对此数据执行可能会放大问题的操作.在某些情况下(例如您的问题)，这可以使求解器得出结论，认为问题不可行时是不可行的.修复变量后，求解程序将执行较少的浮点运算.

MIP solvers work with floating-point data. For problems such as yours that have wide variations in the magnitude in the data, this leads to round-off errors. Any LP solver will have to perform operations on this data that can amplify the problem. In some cases like your problem, this can make the solver conclude that the problem is infeasible when it isn't. When you fix variables, the solver does fewer floating point operations.

诸如 Gurobi 或cplex的商业求解器求解器通常在处理像您这样的数字难度较大的数据方面做得更好. Gurobi具有参数 QuadPrecision ，该参数可用于更高精度的浮点数.大多数求解器都有一个参数，可以使求解器更好地处理数值困难的数据.例如，LPSolve具有参数 epsint ，它将使它放宽它认为是整数的内容.该参数的默认值为10e-7，因此0.9999999被认为是整数，而0.9999998则不是.您可以将该值设置得更大一些，但是却有可能收到无法接受的结果.

The commercial solvers solvers like Gurobi or cplex generally do a better job of working with numerically difficult data like yours. Gurobi has a parameter QuadPrecision that works with higher-precision floating point numbers. Most solvers have a parameter that will make the solver work better with numerically-difficult data. For example LPSolve has a parameter epsint that will make it relax what the it considers an integer. The default for the parameter is 10e-7, so 0.9999999 would be considered to be an integer, but 0.9999998 would not be. You can make this value larger, but you risk receiving unacceptable results.

您遇到的是泄漏抽象.从技术上来说，您的问题在混合整数编程的范围内，但MIP求解器并非旨在解决该问题.混合整数编程是一个NP-Hard问题.不可能有一个在所有输入上都能快速可靠地工作的求解器. MIP解决方案尝试很好地解决来自不同领域的问题，例如投资组合优化，供应链计划和网络流量.它们并非旨在解决密码问题.

You are experiencing a leaky abstrction. Your problem is technically in the scope of Mixed-Integer Programming, but MIP solvers are not designed to solve it. Mixed Integer Programming is an NP-Hard problem. It is impossible to have a solver that works quickly and reliably on all inputs. MIP solvers try to work well on problems that come from diverse areas like portfolio optimization, supply chain planning, and network flows. They aren't designed to solve cryptology problems.

这篇关于求解整数线性程序:为什么求解器声称不存在可求解的实例?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！