• Ottimizzazione di numeri interi

I problemi di ottimizzazione lineare che richiedono che alcune variabili siano numeri interi sono chiamati Programmi di numeri interi misti (MIP).

Queste variabili possono presentarsi in due modi:

  • Variabili interi che rappresentano il numero di articoli, come auto o televisori, e il problema consiste nel decidere quanti pezzi di ciascun articolo produrre per massimizzare il profitto.
    In genere, questi problemi possono essere risolti come problemi di ottimizzazione lineari standard, con l'ulteriore requisito che le variabili devono essere numeri interi. La sezione successiva mostra un esempio di questo tipo di problema.

  • Variabili booleane che rappresentano decisioni con valori 0-1.
    Considera come esempio un problema che comporta l'assegnazione dei lavoratori alle attività (vedi Assegnazione). Per configurare questo tipo di problema, puoi definire variabili booleane xi,j uguali a 1 se il worker i è assegnato all'attività j e 0 negli altri casi.

Per una buona introduzione all'ottimizzazione dei numeri interi, ti consigliamo il libro di ricette per modelli di Mosek.

Strumenti

Google offre diversi modi per risolvere i problemi MIP:

  • MPSolver (Risolutore): un wrapper per diversi risolutori MIP di terze parti, che utilizzano tecniche di ramo e associazione standard.
  • Risolutore CP-SAT: un risolutore di programmazione di vincoli che utilizza metodi SAT (sufficienza).
  • Risolutore CP originale: un risolutore di programmazione di vincoli.

Quale risolutore devo usare?

Non esiste una regola rigida per decidere se utilizzare un risolutore MIP o un risolutore CP-SAT. Come guida approssimativa:

  • I risolutori MIP sono più adatti per problemi che possono essere configurati come LP standard, ma con variabili numeriche di numero intero arbitrarie, come nel primo esempio riportato sopra.
  • Il risolutore CP-SAT è più adatto a problemi in cui la maggior parte delle variabili sono booleane, come nel secondo esempio sopra.

Per i valori MIP tipici che hanno variabili sia numeriche sia booleane, spesso non c'è una chiara differenza di velocità tra i due risolutori, quindi la tua scelta può dipendere dalla tua preferenza personale.

Per esempi che utilizzano i risolutori MIP e CP-SAT, consulta Risolvere un problema di assegnazione e le altre sezioni di assegnazione.

Un altro modo per risolvere problemi di programmazione con numeri interi consiste nell'utilizzare un risolutore di flusso di rete.
Per un esempio, vedi L'assegnazione come problema del flusso di costo minimo.
Per un problema che può essere impostato come flusso di rete, il risolutore del flusso di costo minimo può essere più veloce dei risolutori MIP o CP-SAT. Tuttavia, non tutte le MIP possono essere impostate in questo modo.