0-1 Zaino con vincoli di partizionamento

Question

Ho un problema che sulla superficie assomiglia allo 0-1 zaino. Ho un insieme di possibili "candidati" che possono essere scelti (o meno), ogni candidato ha un "peso" (costo) e un potenziale "valore". Se questo fosse l'intero problema, userei un approccio DP e avremmo finito. Ma ecco la curva: ci sono "vincoli di partizionamento" sui possibili candidati che possono essere nella soluzione finale.

Quello che voglio dire è che lo spazio candidato è diviso in classi di equivalenza discrete. Per il mio problema particolare ci sono circa 300 candidati e 12 possibili classi di equivalenza. Ci sono "regole d'affari" che dicono che posso solo dire 3 candidati dalla classe C1 e 6 candidati da C2, ecc.

Questo vincolo suggerisce un approccio di tipo di ricerca di grafi con tecniche di branch-and-bound o alcune altra forma di potatura, tuttavia sono un po 'perplesso su come iniziare poiché ho solo familiarità con la soluzione DP di 0-1 Zaino. Quali tecniche/approcci potrebbero essere adatti a questo problema? Ho anche pensato di utilizzare una libreria di programmazione dei vincoli, ma non sono sicuro che sarebbe in grado di trovare una soluzione?

Answer 1

È possibile provare un risolutore di programmazione lineare intero, in cui è presente una variabile binaria per la scelta di ciascun candidato. I vincoli sono facilmente espressi come disuguaglianze lineari. Con 300 variabili, un risolutore non dovrebbe avere molti problemi a risolverlo.

Il modo più semplice sarebbe probabilmente quello di scrivere il problema in un formato di testo come lo CPLEX LP format e quindi utilizzare un risolutore come Coin CBC o GLPK.