Knapsack problem

[giuliad88]

Ciao a tutti!
Secondo è corretto risolvere l'algoritmo dello zaino con il metodo del simplesso? In particolare, poiché devo portarlo su excel, vorrei utilizzare il risolutore.
Che ne pensate?

[Intermat]

Il simplesso risolve solo problemi di PL e non di PLI. Se il problema è di PL non ci sono problemi per l'uso del simplesso. Se invece hai il classico Knapsack Binario o Intero allora non va bene perchè dovresti rilassare il problema prima di usare il simplesso. In questo ultimo caso dovresti usare il metodo di Branch and Bound per ottenere una soluzione intera ammissibile e ottima (all'interno di ogni sottoproblema rilassato potresti usare il simplesso). Per risolvere un problema di Knapsack binario (con un vincolo in volume o peso) puoi usare la programmazione dinamica. Ti ricordo che il problema di Knapsack binario ha complessità pseudo-polinomiale ovvero è dell'ordine di $O(nb)$ cioè dipende anche dalla dimensione del vettore $b$.[nota]in un problema del tipo $max{cx: Ax<=b; x in ZZ^m}$[/nota]

[giuliad88]

Io ho degli oggetti aventi un peso pi, una utilità ui e una variabile decisionale xi.
Deve massimizzare il prodotto tra ui e xi tenendo in conto che il peso totale non deve superare un peso max e che xi può assumere solo valori 0 e 1.
Questo come si risolve?

[Intermat]

"giuliad88":Io ho degli oggetti aventi un peso pi, una utilità ui e una variabile decisionale xi.
Deve massimizzare il prodotto tra ui e xi tenendo in conto che il peso totale non deve superare un peso max e che xi può assumere solo valori 0 e 1.
Questo come si risolve?

E' uno Knapsack Binario. Lo puoi risolvere con il branch and bound. Praticamente risolvi il problema rilassato di PL con il simplesso. A quel punto applichi il branch and bound. Ogni sottoproblema che ti si forma lo risolvi, una volta rilassato, con il simplesso. Quando otterrai una soluzione intera e tutti gli altri sotto-problemi chiusi avrai trovato l'ottimo.
Oppure più semplicemente puoi risolverlo applicando la programmazione dinamica per knapsack.

Praticamente lo puoi risolvere sia con il branch and bound sia con la programmazione dinamica...li hai studiati questi algoritmi?

[giuliad88]

Si, il mio problema è mettere il tutto su excel. Excel propone uno strumento per risolvere problemi di PL che si chiama risolutore e utilizza il simplesso. Ora, poichè ho trovato esempi in cui vengono risolti con il risolutore problemi di PLI mi chiedevo se rilassasse il problema in automatico... Ma forse non è il forum adatto per questa domanda

[Intermat]

Mi dispiace ma su excel oltre alle cose basilari non ti saprei dire.

[giuliad88]

When a Solver model includes integer, binary or alldifferent constraints, it is called an integer programming problem. Integer constraints make a model non-convex, and finding the optimal solution to an integer programming problem is equivalent to solving a global optimization problem. Such problems may require far more computing time than the same problem without the integer constraints. When the Simplex LP or GRG Nonlinear Solving methods are used, Solver uses a Branch & Bound method for the integer constraints. The Evolutionary Solving method uses its own methods for such problems. -Dal sito dell'azienda che produce il risolutore per Microsoft Excel.

[Intermat]

Quindi praticamente il solutore è in grado di applicare il metodo di branch and bound. Allora si, ti può risolvere il problema dello knapsack binario. Fermo restando che ha complessità pseudopolinomiale...quindi per risolverlo in tempi accettabili deve avere dimensioni medio-piccole.