Topic: Problema di ottimizzazione  (Letto 46 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline loziobrown

  • python unicellularis
  • *
  • Post: 2
  • Punti reputazione: 0
    • Mostra profilo
Problema di ottimizzazione
« il: Aprile 09, 2019, 11:19 »
Ciao a tutti,
ho un fastidioso problema di ottimizzazione e non so con che approccio affrontarlo:
ho n individui ed ogni individuo può avere disponibili k tipi di attivazione, ogni attivazione contribuisce in maniera diversa su m sottostanti. es:

individuo tipo_attivazione    Mele      Pere       Ananas
1                              A                      2             0                4
1                              B                      2             3                1
2                              A                      2             0                5
2                              B                      2             4                1
2                              C                      2             5                 0
3                              A                      2             0                4
4                              B                      4             6                2
4                              C                      2            10               0
4                              A                      4             0                8


devo cercare una combinazione individuo| tipo_attivazione che mi porti il più vicino possibile ad avere la somma di mele/somma totale =0.3, somma di pere/somma totale =0.4,somma di ananas/somma totale =0.3.

che tipo di approccio utilizzereste?

Grazie in anticipo.

edit. ogni individuo può avere solo un tipo_attivazione nella soluzione finale
« Ultima modifica: Aprile 09, 2019, 14:13 da loziobrown »

Offline bebo

  • python erectus
  • ***
  • Post: 195
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re:Problema di ottimizzazione
« Risposta #1 il: Aprile 09, 2019, 11:51 »
A naso sembra un problema di programmazione intera. Quanto ne sai in merito?

Offline loziobrown

  • python unicellularis
  • *
  • Post: 2
  • Punti reputazione: 0
    • Mostra profilo
Re:Problema di ottimizzazione
« Risposta #2 il: Aprile 09, 2019, 12:32 »
sinceramente poco, conosci qualche problema simile risolto con questa metodologia? il mio problema è sopratutto dover gestire il diverso contributo dei tipi di frutta per ogni tipo di attivazione.

Offline bebo

  • python erectus
  • ***
  • Post: 195
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re:Problema di ottimizzazione
« Risposta #3 il: Aprile 09, 2019, 14:30 »
Hai gia' dato un'occhiata su wikipedia? https://en.wikipedia.org/wiki/Integer_programming
Il tuo sembra un classico problema di IP. Per risolverlo in pratica ti serve un solver.
Uno dei metodi artigianali e' rimuovere i vincoli di interezza, risolvere come fosse un problema di linear programming, e poi cercare l'insieme di soluzioni intere/miste che soddisfino le condizioni iniziali. Ovviamente pero' questa strada non e' definitiva (non sarebbe un problema NP altrimenti ;) ) e puo' portare facilmente a risultati MOLTO sbagliati.

Qui https://stackoverflow.com/questions/26305704/python-mixed-integer-linear-programming dicono che pulp e' un'interfaccia in python per modellare questi tipi di problemi, e a cui si possono attaccare diversi risolutori: io ho usato solo xpress, che e' commerciale, ma li' dicono che ce ne sono anche un paio di open source.

PS: ho trovato anche questo articolo, con un paio di esempi classici, e in cui spiega anche come usare cvxpy.
« Ultima modifica: Aprile 09, 2019, 14:32 da bebo »