Perfect packing
Qualcuno conosce qualche testo o articolo che tratta la questione del perfect packing?
Soprattutto per generare istanze con poche soluzioni ottime equivalenti.
Grazie.
Soprattutto per generare istanze con poche soluzioni ottime equivalenti.
Grazie.
Risposte
"GreenLink":
Qualcuno conosce qualche testo o articolo che tratta la questione del perfect packing?
Soprattutto per generare istanze con poche soluzioni ottime equivalenti.
Grazie.
provato con google scholar
se parli di istanze vuol dire che è uno di quei problemi NP (e famiglia), ma che non conosco. Cmq devi utilizzare qualche tecnica particolare per trovare una soluzione?
Si avevo visto questi articoli ma non mi sembra che venga trattato l'aspetto di avere poche soluzioni ottime.
Mi spiego meglio.
Io sto cercando delle istanze in cui il bin packing abbia poche soluzione ottime. Per questo motivo ho pensato al perfect packing, cioè se ho delle istanze in cui le domande dei prodotti non lasciano spazi dei vuoti nei bin teoricamente dovrei eliminare dei motivi per cui il numero di soluzioni aumenta. Il perfect packing non basta per assicurare che ci siano poche soluzioni ottime, perchè appena ci sono più gruppi di domande in bin diversi che hanno stessa somma allora si generano più soluzioni con lo stesso valore. Quest'ultima è una condizione che si verifica molto facilmente se le domande sono abbastanza ravvicinate, che è quello che ad esempio accade se si considera il teorema del perfect packing.
Comunque se non conosci il perfect packing ma ti vengono in mente dei modi per genereare istanze di bin packing con poche soluzioni ottime mi sei comunque molto d'aiuto!
Mi spiego meglio.
Io sto cercando delle istanze in cui il bin packing abbia poche soluzione ottime. Per questo motivo ho pensato al perfect packing, cioè se ho delle istanze in cui le domande dei prodotti non lasciano spazi dei vuoti nei bin teoricamente dovrei eliminare dei motivi per cui il numero di soluzioni aumenta. Il perfect packing non basta per assicurare che ci siano poche soluzioni ottime, perchè appena ci sono più gruppi di domande in bin diversi che hanno stessa somma allora si generano più soluzioni con lo stesso valore. Quest'ultima è una condizione che si verifica molto facilmente se le domande sono abbastanza ravvicinate, che è quello che ad esempio accade se si considera il teorema del perfect packing.
Comunque se non conosci il perfect packing ma ti vengono in mente dei modi per genereare istanze di bin packing con poche soluzioni ottime mi sei comunque molto d'aiuto!
Un altro sito utile a riguardo è Mendeley. Oppure puoi cercare su siti di publisher specifici o attraverso le biblioteche (il catalogo unico).
forse è questione di terminologia, ma non mi è chiaro cosa tu intenda con:
intendi soluzioni quasi-ottime oppure distanti dall'ottimo per un $\rho$ (o alle volte $\epsilon$) fissato a piacimento (cioè generate da un algoritmo approssimato).
Solo per chiarire
@vict:
interessante questo Mendeley non lo conoscevo; mi tornerà di sicuro utile. grazie
"GreenLink":
poche soluzioni ottime
intendi soluzioni quasi-ottime oppure distanti dall'ottimo per un $\rho$ (o alle volte $\epsilon$) fissato a piacimento (cioè generate da un algoritmo approssimato).
Solo per chiarire
@vict:
interessante questo Mendeley non lo conoscevo; mi tornerà di sicuro utile. grazie
Intendo soluzioni ammissibili per il problema la cui valutazione nella funzione obiettivo è esattamente il valore di ottimo del problema.
"GreenLink":
Intendo soluzioni ammissibili per il problema la cui valutazione nella funzione obiettivo è esattamente il valore di ottimo del problema.
mi pare accettabile.
comprendo che instanziando il bin packing a quel problema trovi delle soluzioni ottime, ma penso ti sia accorto e sappia che non è detto sia la soluzione ottima del bin packing ma solo del perfect pecking (che possono collidere ma anche no).
se il tuo scopo è affrontare il bin packing, puoi utilizzare una strategia/tecnica chiamata di "ricerca locale". Produce delle soluzioni ammissibili vicine all'ottimo (non è detto), per le scelte strategiche che si fanno per trovare tale soluzione.
Puoi utilizzare i risultati del problema istanziato del perfect packing per cercare soluzioni del problema più generale del bin packing. All'incirca funzione che tu produci soluzioni con il perfect packing, ma queste le consideri soluzioni quasi-ottime, come dei punti cartesiani del problema del bin-packing, di volta in volta valuti se sia soluzione del problema generale o meno.
Le mie sono solo dissertazioni notturne, ma secondo me è un approccio plausibile. La ricerca locale (se non la conosci) è una meravigliosa tecnica algoritmica adattabile ad una miriade di casi, ma bisognerebbe valutare che cosa davvero ti è stato chiesto di fare e trovare.
PS: secondo me in letteratua se cerchi "local search" "bin packing" trovi dei risultati
Mi spiego meglio.
Il mio obiettivo è costruire delle istanze in cui il bin packing abbia poche (preferibimente 1) soluzioni ottime. Per far questo un'idea è quella di considerare istanze in cui il packing sia perfetto, cioè la somma delle dimensioni degli oggetti in un bin occupa completamente la capacità dei bin. Infatti se la soluzione di un problema di bin packing è anche di perfect packing, non ci potranno sicuramente essere soluzioni ottime del problema che non riempono completamente tutti i bin.
Il problema è che anche se un istanza ammette perfect packing poi non è detto che non ci siano tanti impaccamenti perfetti possibili per quella istanza.
Contare le soluzioni ottime di bin packing non è il mio problema.
Il mio obiettivo è costruire delle istanze in cui il bin packing abbia poche (preferibimente 1) soluzioni ottime. Per far questo un'idea è quella di considerare istanze in cui il packing sia perfetto, cioè la somma delle dimensioni degli oggetti in un bin occupa completamente la capacità dei bin. Infatti se la soluzione di un problema di bin packing è anche di perfect packing, non ci potranno sicuramente essere soluzioni ottime del problema che non riempono completamente tutti i bin.
Il problema è che anche se un istanza ammette perfect packing poi non è detto che non ci siano tanti impaccamenti perfetti possibili per quella istanza.
Contare le soluzioni ottime di bin packing non è il mio problema.
"GreenLink":
Mi spiego meglio.
Il mio obiettivo è costruire delle istanze in cui il bin packing abbia poche (preferibimente 1) soluzioni ottime. Per far questo un'idea è quella di considerare istanze in cui il packing sia perfetto, cioè la somma delle dimensioni degli oggetti in un bin occupa completamente la capacità dei bin. Infatti se la soluzione di un problema di bin packing è anche di perfect packing, non ci potranno sicuramente essere soluzioni ottime del problema che non riempono completamente tutti i bin.
Il problema è che anche se un istanza ammette perfect packing poi non è detto che non ci siano tanti impaccamenti perfetti possibili per quella istanza.
ooh, ok ora è chiaro cosa cerchi di fare. Direi che la ricerca locale sarebbe adatta a questo scopo.
Il problema è che anche se un istanza ammette perfect packing poi non è detto che non ci siano tanti impaccamenti perfetti possibili per quella istanza.
Direi che in questo caso, o cambi riduzione del problema, visto che devi esser certo della soluzione sia ottima (o più soluzioni) o cerchi qualche altra proprietà più forte che ti garantisca l'unicità od altro della tua soluzione.
cmq controllo se trovo qualcosa quando ho un attimo, non garantisco.
Grazie.
Che cosa intendi per riduzione del problema?
Che cosa intendi per riduzione del problema?
"GreenLink":
Grazie.
Che cosa intendi per riduzione del problema?
riduzione di un problema in un altro simile od equivalente. Ha diversi significati a seconda del contesto, ed in questo caso è un po' un "abuso di linguaggio". Ma intendevo che dovresti cambiare istanza del problema del bin packing se questa (perfect packing) non ti garantisce certe proprietà che cerchi.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo