Esperimenti MIP per una classe di problemi di assegnamento quadratico

The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. A particular class of this problem is the “TaiC”. It requires a significantly reduced computational complexity to be solved in comparison to the general case. This and other properties have been used to perform experiments in order to study the complexity of the problem when varying different parameters among which there is the instances’ size. The results are shown and discussed in this paper.

Il problema di assegnamento quadratico (QAP) è uno dei problemi fondamentali di ottimizzazione combinatoria nei rami della matematica dell'ottimizzazione e della ricerca operativa. Una particolare classe di questo problema è la “TaiC”. Essa richiede una complessità computazionale per essere risolta notevolmente ridotta rispetto al caso generale. Si è voluto sfruttare questa ed altre proprietà per effettuare esperimenti al fine di studiare la complessità del problema al variare di diversi parametri tra cui la dimensione delle istanze. I risultati sono presentati e discussi in questo elaborato.