Calcola il gap di ottimalità relativa nel problema MIP GAMS

Aug 16 2020

Voglio calcolare il gap di ottimalità relativo di un problema MIP e voglio anche interrompere le esecuzioni in un determinato momento di esecuzione. questo metodo:

F(1)    
abs(mymodel.objest - mymodel.objval)/max(abs(mymodel.objest),abs(mymodel.objval)) 

non è coerente con il gap che GAMS calcola nel log. GAMS utilizza il "Miglior numero intero" per trovare il divario e non il valore obiettivo attuale. quale è corretto? e Come posso salvare l'attuale "Best Integer" in un parametro (come .objval).

e infine il calcolo dell'ottimalità relativa Gap in un algoritmo di benders è giusto in questo modo?

rgap = (upperBound - lowerBound)/(1 + abs(upperBound));

Cosa calcola GAMS utilizzando la "Soluzione MIP"

MIP Solution:   3334501534.000555    (1625 iterations, 0 nodes)
Final Solve:      56330158.829040    (2561 iterations)

Best possible:    48915652.476336
Absolute gap:   3285585881.524219
Relative gap:            0.985330

F(1) gap calcolato utilizzando mymodel.objval (mymodel.objval restituisce "Final Solve"), quindi il gap calcolato è %13 e il valore mymodel.objval è 5.633016E+7 (il gap calcolato da GAMS è %98). quindi ho bisogno di salvare "Soluzione MIP" in un parametro per esportarlo in un file excel.

Risposte

1 Lutz Aug 17 2020 at 14:16

Esistono diverse formule per calcolare il relativo gap di ottimalità. Dipende dal risolutore che usi, quale viene applicato. Alcune informazioni su questo possono essere trovate nella descrizione dell'opzione GAMS optCR . Il manuale del risolutore del risolutore che usi potrebbe avere maggiori dettagli sulla formula effettivamente applicata.

EDIT dopo che la domanda è stata aggiornata:

Come hai scritto mymodel.objvalrestituisce il Final Solvevalore. Se invece vuoi vedere il MIP Solutionvalore (poiché il collegamento Cplex lo fa internamente), puoi disattivare la soluzione finale. Tuttavia, se Final Solvee MIP Solutionsono molto diversi come nel tuo esempio, questo è spesso un'indicazione per qualche problema (di solito sono (quasi) identici). Spesso, questo indica un modello scarsamente ridimensionato. Forse potresti migliorare la situazione restringendo le tolleranze Cplex (vedi opzioni Cplex epopt, eprhs, epint) e attivando un ridimensionamento aggressivo (opzione Cplex scaind 2). Attivazione mipkappastats(https://www.gams.com/latest/docs/S_CPLEX.html#CPLEXmipkappastats) e quality(https://www.gams.com/latest/docs/S_CPLEX.html#CPLEXquality) potrebbe darti maggiori informazioni. DataCheck=2(https://www.gams.com/latest/docs/S_CPLEX.html#CPLEXdatacheck) potrebbe mostrare alcuni problemi.