Solving an integer linear program: why are solvers

问题:

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

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

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;

And then tried to solve it:

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?

回答1:

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.

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.

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.

回答2:

You could also have a look at SCIP 3.1.0 and especially its extended precision arithmetic features. Using GMP the LP solution can be computed up to a very high accuracy.