We show that modulators can be interpreted as heuristic solvers for a particular class of optimisation problems. Then, we exploit this theoretical result to propose a novel technique to deal with very large Unconstrained Discrete Quadratic Programming (UDQP) problems characterised by quadratic forms entailing a circulant matrix. The result is a circuit based optimisation approach involving a recast of the original problem into signal processing specifications, then tackled by the systematic design of an electronic system. This is reminiscent of analog computing, where untractable differential equations were solved by designing electronic circuits analogue to them. The approach can return high quality sub-optimal solutions even when many hundreds of variables are considered and proved faster than conventional empirical optimisation techniques. Detailed examples taken from two different domains illustrate that the range of manageable problems is large enough to cover practical applications.

On the Approximate Solution of a Class of Large Discrete Quadratic Programming Problems by Delta Sigma Modulation: The Case of Circulant Quadratic Forms / Callegari, S.; Bizzarri, F.; Rovatti, R.; Setti, G.. - In: IEEE TRANSACTIONS ON SIGNAL PROCESSING. - ISSN 1053-587X. - STAMPA. - 58:12(2010), pp. 6126-6139. [10.1109/TSP.2010.2071866]

On the Approximate Solution of a Class of Large Discrete Quadratic Programming Problems by Delta Sigma Modulation: The Case of Circulant Quadratic Forms

G. Setti
2010

Abstract

We show that modulators can be interpreted as heuristic solvers for a particular class of optimisation problems. Then, we exploit this theoretical result to propose a novel technique to deal with very large Unconstrained Discrete Quadratic Programming (UDQP) problems characterised by quadratic forms entailing a circulant matrix. The result is a circuit based optimisation approach involving a recast of the original problem into signal processing specifications, then tackled by the systematic design of an electronic system. This is reminiscent of analog computing, where untractable differential equations were solved by designing electronic circuits analogue to them. The approach can return high quality sub-optimal solutions even when many hundreds of variables are considered and proved faster than conventional empirical optimisation techniques. Detailed examples taken from two different domains illustrate that the range of manageable problems is large enough to cover practical applications.
File in questo prodotto:
File Dimensione Formato  
TSPSIGMASELTA.pdf

non disponibili

Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 919.84 kB
Formato Adobe PDF
919.84 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2696606
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo