Funzione oggettiva e soddisfazione dei vincoli su un insieme di elementi multi-attributi

Question

Sto cercando un approccio per risolvere un problema che consiste nel massimizzare una funzione obiettiva su un insieme di elementi discreti, rispettando al contempo un insieme di vincoli.

Per illustrare il mio punto, cercherò di trovare un esempio.

Una borsa contiene diversi elementi con i seguenti attributi:

• Valore (int)
• Dimensione (int)
• Materiale (enum)
• Origine (enum)

Ad esempio, possiamo immaginare una borsa composta dai seguenti elementi:

value     size     material    origin
    4        1         wood        FR
    4        2        stone        US
    3        3         gold        JP
    2        2         wood        FR
  ...      ...          ...       ...

L'obiettivo è massimizzare il valore totale, rispettando allo stesso tempo un insieme di vincoli. Un set di vincoli di esempio sarebbe:

total size < 80
between 20 and 35 items in total
at least five elements with origin FR
at least two elements with material wood OR at least two elements with material stone
strictly less elements with material gold than elements of material stone
no more than 5 elements with size > 10

Di seguito sono riportati alcuni approcci a cui ho pensato e il motivo per cui non posso usarli direttamente:

• (Intero) Programmazione lineare: qui non abbiamo a che fare con l'intero spazio degli interi, ma solo con i valori trovati nella borsa (e legati alle altre proprietà per ciascun articolo)
• Soddisfazione del vincolo stocastico: sarebbe facile trovare stocasticamente una selezione di oggetti che rispettano i vincoli, ma qui non stiamo cercando qualunque soluzione, invece stiamo cercando il Soluzione che produce il valore totale più alto, che avrebbe bisogno di noi per elencare esauriente tutte le possibili soluzioni soddisfacenti prima di scegliere quella con il più alto valore (che può essere un approccio molto inefficiente)
• Smt Solver: penso che potrebbe essere la strada da percorrere, ma finora non riesco a vedere come modellare il legame tra i vincoli, la funzione obiettivo e la borsa di elementi

Riesci a pensare a un approccio per risolvere questo tipo di problemi?