Risoluzione di un programma lineare intero: perché i risolutori che sostengono un'istanza risolvibile non sono fattibili?

Question

Sto provando a risolvere i problemi di programmazione intera. Ho provato sia per uso SCIP e LPSolve

Per esempio, dati i valori finali di A e B, voglio risolvere per vala nel seguente codice 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 

che ho implementato come questo intero programma in formato lp (divisione troncando provoca alcune complicazioni):

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; 

E poi cercato di risolverlo:

The model is INFEASIBLE 

Tuttavia, so che esiste una soluzione fattibile perché conosco un compito variabile che funziona. Aggiungendo le seguenti condizioni provoca una soluzione da trovare:

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; 

Due diversi risolutori hanno sostenuto questo problema fattibile è fattibile. Sto violando alcune condizioni non scritte? Cosa sta succedendo? Ci sono dei risolutori che risolvono effettivamente il problema?

Answer 1

I risolutori MIP funzionano con dati in virgola mobile. Per problemi come il tuo che hanno ampie variazioni nella grandezza dei dati, questo porta a errori di arrotondamento. Qualsiasi solutore LP dovrà eseguire operazioni su questi dati che possono amplificare il problema. In alcuni casi, come il tuo problema, questo può far concludere al risolutore che il problema non è fattibile quando non lo è. Quando si risolvono le variabili, il risolutore esegue un numero inferiore di operazioni in virgola mobile.

I risolutori di risolutori commerciali come Gurobi o cplex generalmente eseguono un lavoro migliore con dati numericamente difficili come il vostro. Gurobi ha un parametro QuadPrecision che funziona con numeri in virgola mobile di alta precisione. La maggior parte dei solutori ha un parametro che farà funzionare meglio il risolutore con dati numericamente difficili. Ad esempio LPSolve ha un parametro epsint che lo renderà in grado di rilassare ciò che considera un numero intero. Il valore predefinito per il parametro è 10e-7, quindi 0.9999999 sarebbe considerato come un numero intero, ma 0.9999998 non lo sarebbe. Puoi aumentare questo valore, ma rischi di ricevere risultati inaccettabili.

Si sta verificando un leaky abstrction. Il tuo problema è tecnicamente nell'ambito della programmazione di interi misti, ma i solutori MIP non sono progettati per risolverlo. La programmazione di interi misti è un problema NP-Hard. È impossibile avere un risolutore che funzioni in modo rapido e affidabile su tutti gli input. I solutori MIP cercano di lavorare bene su problemi che provengono da aree diverse come l'ottimizzazione del portafoglio, la pianificazione della supply chain e i flussi di rete. Non sono progettati per risolvere i problemi di crittologia.

Answer 2

Si potrebbe anche dare un'occhiata a SCIP 3.1.0 e in particolare alle sue funzioni aritmetiche di precisione estesa. Usando GMP la soluzione LP può essere calcolata con una precisione molto elevata.