Newsgroup: it.comp.programmare
Titolo: Integer linear programming solver in C

Ciao,
 
stavo cercando un algoritmo in C che mi faccia una ottimizzazione di questo tipo:
Maximize p = x+y+z subject to x+y+z <= 2, 3x+y >= 4 
con soluzione ottima con numeri interi
 
In rete ho trovato qualcosa ma solo su numeri reali, avete qualche indicazione da darmi?
 
Grazie

 Grazie


Questo tool funziona e tra le tante cose riesco a fargli fare quello che mi serve, il problema è che dovrei portare questo algoritmo su una board e avrei problemi a traferire le librerie e tutto quanto, quindi vorrei trovare un algoritmo nudo e crudo in c, su singolo file, che faccia tutto..
Purtroppo per ora ho solo trovato progetti grossi tipo lp solve..

 grossi tipo lp solve..
 
in concetto di "board" e' relativo, tanto per citare 3 classi differenti
di board:
un arduino
un cortex M3/4
un arm da "tablet" ?
 
perche' sono certo che sai che il problema "intero" rispetto a quello
continuo e' decisamente piu' ostico e temo che difficilmente sia
risolvibile in maniera standard ( branch & bound ) sulle prime due classi
 
dipende anche dalla dimensione del dominio sul quale fai
l'ottimizzazione, se il dominio e' "piccolo" forse un brute-force su
tutti i punti del dominio e' la soluzione piu' semplice, se il dominio
e' grande ( ovvero il risultato atteso come punto di ottimo a valori
intorno o superiori al centinaio ) potresti accontentarti di una
soluzione sub-ottima risolvendo il probmema continuo e poi usando di
nuovo il brute-force in un intorno della soluzione continua
 
se invece hai una board della classe "arm per tablet" quella libreria
dovrebbe essere facilmente portabile

 dovrebbe essere facilmente portabile
 
Purtroppo non sono molto ferrato in programmazione, è un progetto universitario che devo portare avanti e dalla mia ho solo alle spalle gli esami sul c.
 
La board che devo utilizzare è questa:
http://www.telit.com/telit/Pulsar/en_US.Store.display.1031./ue910-v2-series
 
 
 
L'ambiente di sviluppo si chiama Telit App Zone ed ha queste specifiche:
http://www.telit.com/telit/Pulsar/en_US.CMS.display.797./technical-specifications
 
 
Nello specifico, semplificando il problema di base, devo minimizzare una somma di questo tipo:
Sommatoria (PotenzaConsumataDispositivo_xTask_y * Dispositivo_xTask_y)
dove Dispositivo_xTask_y vale 1 se un determinato task è attivo e vale zero se è spento.
Poi il problema è più complesso perché devo considerare in più il costo dell'energia e di come vari nel tempo per assegnare un orario di esecuzione ai task.

 Poi il problema č piů complesso perché devo considerare in piů il costo dell'energia e di come vari nel tempo per assegnare un orario di esecuzione ai task.
 
come risorse stai in quella che ho chiamato classe 2, non mi hai 
specificato il numero di xTask , pero' dal genere di problema andrei di 
brute-force
 
PotenzaConsumata... sono delle costanti vero ?
 
tieni conto che mi sembra un problema binario piu' che uno intero ( tu 
hai fatto l'esame di ricerca operativo, vero ? )
 
 
 

 hai fatto l'esame di ricerca operativo, vero ? )
 
Si, è un problema binario, comunque basterebbe il vincolo <=2 sul problema integer, per questo l'ho presentato così.
No, non ho dato nessun esame simile.
 
Così ad occhio potrei stimare al massimo 100 task e con un brute-force non penso sia fattibile, non credo la board regga.
Si, la potenza consumata è sempre una costante che dipende dal task.
Il task lavaggio delicato del dispositivo lavatrice consuma sempre X Watt etc..

 Il task lavaggio delicato del dispositivo lavatrice consuma sempre X Watt etc..
 
io mediterei ancora un po' sul problema da risolvere ;-)

 cui il problema e' quanto meno non completamente formulato
 
Devo massimizzare la sommatoria col vincolo che sia inferiore alla Potenza Massima utilizzabile nell'abitazione.
 
Cmq ho iniziato ad implementarlo da solo.
In pratica devo implementare questo algoritmo:
http://courses.washington.edu/inde412/IP_SLIDES3.pdf
 


 
questo somiglia MOLTO di piu' al problema dello "zaino" (*) altro 
classico della ricerca operativo che in pratica e' una versione 
"specializzata" della ottimizzazione binaria
 
 
(*) il problema e' il seguente: ho uno zaino di capacita' nota che 
voglio riempire con oggetti di "peso" dati in modo da massimizzare la 
quantita' trasportata ( chiaramente zaino, oggetti e pesi sono solo 
degli esempi )
