Rozwiązywanie liniowego programu typu integer: dlaczego solwery twierdzą, że niemożliwe do rozwiązania wystąpienie?

Question

Próbuję rozwiązać problemy z programowaniem całkowitym. Próbowałem zarówno wykorzystanie SCIP i LPSolve

Na przykład, biorąc pod uwagę ostateczne wartości A i B, chcę rozwiązać przez Vala w następujący kod 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 

Które I wdrożone jako tej liczby całkowitej Program w formacie lP (podział powoduje skracanie kilka komplikacji):

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; 

a następnie próbował go rozwiązać:

The model is INFEASIBLE 

Jednak wiem, że istnieje wykonalne rozwiązanie, ponieważ znam przypisanie zmiennych, które działa. Dodawanie następujących warunków powoduje rozwiązanie można znaleźć:

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; 

Dwa różne rozwiązują twierdzili to wykonalne problemem jest niewykonalne. Czy naruszam jakiś niepisany warunek? Co się dzieje? Czy istnieją rozwiązania, które faktycznie rozwiązują problem?

Answer 1

Rozwiązania MIP działają z danymi zmiennoprzecinkowymi. W przypadku problemów takich jak Twoje, które mają duże różnice w wielkości danych, prowadzi to do błędów zaokrąglania. Każdy solver LP będzie musiał wykonać operacje na tych danych, które mogą wzmocnić problem. W niektórych przypadkach, takich jak twój problem, może to sprawić, że solver dojdzie do wniosku, że problem jest niewykonalny, gdy tak nie jest. Kiedy naprawisz zmienne, solver wykonuje mniej operacji zmiennoprzecinkowych.

Solverzy zajmujący się solverami komercyjnymi, takimi jak Gurobi lub cplex, generalnie lepiej pracują z danymi trudnymi liczbowo, takimi jak twoja. Gurobi ma parametr QuadPrecision, który działa z liczbami zmiennoprzecinkowymi o wyższej precyzji. Większość solverów ma parametr, który sprawi, że solwer będzie działał lepiej z danymi trudnymi liczbowo. Na przykład LPSolve ma parametr epsint, który sprawi, że rozluźni się to, co uważa za liczbę całkowitą. Wartością domyślną dla parametru jest 10e-7, więc 0,9999999 będzie uznawane za liczbę całkowitą, ale 0,9999998 nie będzie. Możesz zwiększyć tę wartość, ale ryzykujesz otrzymaniem niedopuszczalnych wyników.

Masz numer leaky abstrction. Twój problem jest technicznie w zakresie programowania mieszanego, ale rozwiązania MIP nie są zaprojektowane, aby go rozwiązać. Programowanie mieszane Integer jest problemem NP-Hard. Nie można mieć solwera, który działa szybko i niezawodnie na wszystkich wejściach. Rozwiązania MIP starają się dobrze pracować nad problemami pochodzącymi z różnych obszarów, takich jak optymalizacja portfela, planowanie łańcucha dostaw i przepływy sieciowe. Nie są przeznaczone do rozwiązywania problemów kryptologicznych.

Answer 2

Można również rzucić okiem na SCIP 3.1.0, a zwłaszcza na jego rozszerzone funkcje arytmetyczne. Za pomocą GMP rozwiązanie LP można obliczyć z bardzo dużą dokładnością.