I problemi di programmazione lineare intera sorgono quando si cerca di risolvere sistemi lineari specificando che tutte le variabili incognite devono essere intere o numeri interi. I sistemi lineari sono insiemi di equazioni che descrivono una situazione per la quale il programmatore sta tentando di trovare una soluzione. Di solito consistono in un’equazione che deve essere massimizzata o minimizzata e una o più equazioni restrittive che pongono limiti alle variabili incognite. Perché il sistema sia lineare, ogni restrizione deve essere un’equazione lineare; cioè, non deve contenere istanze della variabile sconosciuta con esponenti maggiori di uno.
I sistemi lineari regolari possono essere risolti facilmente utilizzando un computer. Il programma può identificare una soluzione trovando la derivata e ponendola uguale a zero. Può quindi verificare che il punto è un massimo o un minimo controllando il suo immediato intorno sulla funzione. Finché la derivata è definita in ogni punto lungo la funzione, il computer ha solo un numero limitato di possibili soluzioni da verificare.
La programmazione lineare diventa programmazione lineare intera con l’aggiunta della restrizione intera. Ciò significa che il problema rimane lo stesso, ma la risposta deve consistere in valori interi per i valori incogniti: devono essere numeri interi. A volte, questo significa che la soluzione sarà subottimale rispetto al caso in cui sono ammesse le frazioni; riflette, tuttavia, il mondo reale, in cui gli elementi spesso si presentano in unità discrete e indivisibili. Ciò rende la programmazione lineare intera importante per le applicazioni aziendali, poiché le aziende vogliono massimizzare i profitti il più possibile ma non possono scegliere di vendere una frazione di un prodotto.
Una volta che le restrizioni sugli interi sono in atto, il problema di risolvere il sistema lineare è NP-completo. Ciò significa che il tempo necessario a un computer per risolvere il sistema è indeterminato. Con le restrizioni sui numeri interi, i computer non possono utilizzare lo strumento della derivata perché non vi è alcuna garanzia che il punto zero della derivata cadrà su un numero intero. La soluzione sarà l’intero con il valore più alto o più basso tra tutti gli interi, quindi il computer dovrebbe controllarli tutti, un processo che potrebbe richiedere un tempo infinito.
I programmatori hanno sviluppato euristiche, o metodi di risoluzione dei problemi, per affrontare la complessità di questi problemi. Un metodo per risolvere problemi di programmazione lineare intera è l’algoritmo branch and bound, in cui il computer risolve una serie di problemi relativi a quello originale per restringere l’intervallo di valori disponibile a una soluzione. Per problemi complessi, tuttavia, ciò può richiedere molto tempo.