Решение целочисленной линейной программы: почему решатели, претендующие на разрешимый экземпляр, недопустимы?

Question

Я пытаюсь решить проблемы с целым программированием. Я пытался как использовать SCIP и LPSolve

Например, учитывая окончательные значения A и B, я хочу, чтобы решить для Вала в следующих C# код:

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 не будет. Вы можете увеличить это значение, но вы рискуете получить недопустимые результаты.

Вы столкнулись с leaky abstrction. Ваша проблема технически входит в сферу программирования с смешанным целым, но решатели MIP не предназначены для ее решения. Смешанное целочисленное программирование - проблема NP-Hard. Невозможно иметь решателя, который работает быстро и надежно на всех входах. Решатели MIP стараются хорошо работать над проблемами, которые возникают из различных областей, таких как оптимизация портфеля, планирование цепочки поставок и сетевые потоки. Они не предназначены для решения проблем криптологии.

Answer 2

Вы также можете ознакомиться с SCIP 3.1.0 и особенно с его арифметическими функциями с высокой точностью. Используя GMP, решение LP можно вычислить с очень высокой точностью.