Abstract: Quello di trovare il massimo o il minimo di una funzione quadratica a
variabili binarie è uno dei più importanti problemi di ottimizzazione discreta, che trova numerose applicazioni, per esempio, in Fisica Statistica (nella determinazione degli stati di energia minima dei vetri di spin), nella progettazione ottima di circuiti integrati, nella assegnazione delle frequenze a trasmettitori radio, nella determinazione ottima dei turni delle partite di un campionato.
Essendo classificato come "NP-difficile", è possibile trovare istanze anche di poche decine di variabili, per le quali è pressoché impossibile trovare e certificare una soluzione ottima in tempi di calcolo accettabili. Nel seminario verranno illustrate le più recenti tecniche utilizzate per la soluzione esatta di questo problema, che consentono di risolvere alcune istanze anche di decine di migliaia di variabili.
Verrà fatto infine un breve cenno all'estensione di tali tecniche al caso di funzioni generali a variabili intere, eventualmente soggette ad alcuni vincoli.
Nessun commento:
Posta un commento