L’idea: trovare numeri che rispettino tutti i vincoli contemporaneamente. Con x≥1, y≥0 e x+y≤3, la coppia x=2, y=1 funziona: verifica una disequazione alla volta.
Ogni vincolo delimita una regione; una soluzione è un punto nella loro intersezione. Sono ammessi anche valori frazionari: x=1,5 e y=0,5 è un’altra soluzione. In INTEGER PROGRAMMING, invece, le variabili devono essere intere.
Con coefficienti razionali codificati in binario, decidere se esiste una soluzione richiede tempo polinomiale nella lunghezza dell’input. Algoritmi come il metodo dell’ellissoide garantiscono questo limite; il simplesso può richiedere tempo esponenziale nel caso peggiore.
Complemento e collegamenti
Nessun complemento associato.
- MAX FLOW è un caso di programmazione lineare
- soluzioni reali: in P; soluzioni intere: NP-completo
INTEGER PROGRAMMING è NP-completo