Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

Rilassamenti: Knapsack, Packing, Multicovering

In questo lavoro dopo aver introdotto i rilassamenti, si effettua un confronto fra alcuni di essi rispetto ai problemi di programmazione lineare intera. Presentiamo tre algoritmi greedy euristiche per il "Knapsack Problem"=(KP), per il "Set Packing Problem"=(SPP) e per il "Multicovering Problem"=(MCP). Presentiamo infine un algoritmo branch & bound per il (MCP) basato su euristica primale, decomposizione lagrangiana, duale debole e rilassamento surrogato. Il "Set Covering Problem"=(SCP) è un caso particolare di (MCP). Si conclude con alcuni risultati sperimentali su problemi generati casualmente.

Mostra/Nascondi contenuto.
Dipartimento di Informatica, Pisa, 1993 - 3 - Sommario. In questo lavoro dopo aver introdotto i rilassamenti, si effettua un confronto fra alcuni di essi rispetto ai problemi di programmazione lineare intera. Presentiamo tre algoritmi greedy euristiche per il "Knapsack Problem"=(KP), per il "Set Packing Problem"=(SPP) e per il "Multicovering Problem"=(MCP). Presentiamo infine un algoritmo branch & bound per il (MCP) basato su euristica primale, decomposizione lagrangiana, duale debole e rilassamento surrogato. Il "Set Covering Problem"=(SCP) è un caso particolare di (MCP). Si conclude con alcuni risultati sperimentali su problemi generati casualmente. PAROLE CHIAVI: decomposizione lagrangiana, duale debole, rilassamento surrogato. Abstract. This paper start whit an illustration of relaxation techniques, the comparision between them is applied for the resolution of linear integer programming problem. We present a greedy heuristics algorithms for the "Knapsack Problem"=(KP), for the "Set Packing Problem"=(SPP) and for the "Multicovering Problem"=(MCP). After we present a branch & bound algorithm for the (MCP) based of primal heuristic, lagrangean decomposition, weak dual and surrogate relaxation. The "Set Covering Problem"=(SCP) is a particular case of (MCP). Following some computational result for randomly generated problem.

Tesi di Laurea

Facoltà: Scienze dell'informazione

Autore: Gianni Irace Contatta »

Composta da 39 pagine.

 

Questa tesi ha raggiunto 299 click dal 13/04/2011.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.