Lösung eines ganzzahligen linearen Programms: Warum sind Solver, die eine lösbare Instanz beanspruchen, undurchführbar?

Question

Ich versuche, ganzzahlige Programmierprobleme zu lösen. Ich habe versucht, sowohl die Verwendung SCIP und LPSolve

Zum Beispiel der letzten Werte von A und B gegeben, mag ich für Vala in dem folgenden C# -Code lösen:

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 

, die ich als diese ganzen Zahl umgesetzt Programm in lp-Format (das Kürzen Teilung verursacht einige Komplikationen):

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; 

Und dann versucht, es zu lösen:

The model is INFEASIBLE 

Allerdings weiß ich, dass es eine machbare Lösung gibt, weil ich eine variable Zuweisung kenne, die funktioniert. Hinzufügen die folgenden Bedingungen verursacht eine Lösung gefunden werden:

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; 

Zwei verschiedene Solver behauptet haben dies möglich Problem nicht machbar ist. Verletze ich einen ungeschriebenen Zustand? Was ist los? Gibt es Löser, die das Problem tatsächlich lösen?

Answer 1

MIP-Löser arbeiten mit Fließkommadaten. Bei Problemen wie Ihrer, die große Schwankungen in der Größe der Daten haben, führt dies zu Rundungsfehlern. Jeder LP-Solver muss Operationen an diesen Daten durchführen, die das Problem verstärken können. In einigen Fällen wie Ihrem Problem kann dies dazu führen, dass der Solver zu dem Schluss kommt, dass das Problem nicht machbar ist, wenn dies nicht der Fall ist. Wenn Sie Variablen fixieren, führt der Solver weniger Fließkommaoperationen aus.

Die kommerziellen Löser Löser wie Gurobi oder cplex arbeiten in der Regel besser mit numerischen Daten wie Ihre arbeiten. Gurobi hat einen Parameter QuadPrecision, der mit Gleitkommazahlen höherer Genauigkeit arbeitet. Die meisten Löser haben einen Parameter, der den Löser mit numerisch schwierigen Daten besser arbeiten lässt. Zum Beispiel hat LPSolve einen Parameter epsint, der es entsperren wird, was es als Ganzzahl betrachtet. Der Standardwert für den Parameter ist 10e-7, also würde 0,999999 als eine ganze Zahl betrachtet werden, aber 0,999998 wäre dies nicht. Sie können diesen Wert vergrößern, aber Sie riskieren unakzeptable Ergebnisse.

Sie haben eine leaky abstrction. Ihr Problem ist technisch im Bereich der Mixed-Integer-Programmierung, aber MIP-Löser sind nicht dafür ausgelegt, es zu lösen. Mixed Integer Programming ist ein NP-Hard-Problem. Es ist unmöglich, einen Solver zu haben, der schnell und zuverlässig an allen Eingängen arbeitet. MIP-Solver versuchen gut mit Problemen umzugehen, die aus verschiedenen Bereichen wie Portfoliooptimierung, Supply-Chain-Planung und Netzwerkflüsse stammen. Sie sind nicht dafür ausgelegt, kryptologische Probleme zu lösen.

Answer 2

Sie könnten auch SCIP 3.1.0 und speziell die arithmetischen Funktionen für erweiterte Genauigkeit ansehen. Unter Verwendung von GMP kann die LP-Lösung mit einer sehr hohen Genauigkeit berechnet werden.