The problem that we address is, given a matrix, permute rows and columns so that the bandwidth is minimized. The matrix bandwidth reduction is a problem of general interest. Many practical problems require the solution of linear systems, and the performance of the solution methods can be highly improved by a reduction in the bandwidth of the systems matrices. Different scientific fields can take advantage from such an approach, ranging from microwave circuit design to numerical geophysics, from integrated electronics to computational chemistry, and this is why the problem has already been deeply investigated. However, these methods are often ineffective when applied to some pathological cases. We propose a new heuristic (WonderBRA) obtained as an improvement of the classical Cuthill McKee algorithm. From the computational results it appears that the new algorithm overcomes the pathological cases where the literature algorithm get stuck. The algorithm is applied to data from real applications. A comparison on real cases is also made with previous constructive approaches demonstrating the superior performance of the here proposed method.

Collaborators

Alberto Caprara (DEI - Università di Bologna), Stella Catalano, Alessandra Esposito, Daniele Pretolani (Dipartimento di Matematica e Fisica, Università di Camerino), Luciano Tarricone (DIEI, Università di Perugia).

List of papers

1. Caprara A., F. Malucelli and D. Pretolani (2002). "On Bandwidth-2 Graphs" Discrete Applied Mathematics 117: 1-13.
2. Caproni, A., F. Cervelli, M. Mongiardo, L. Tarricone and F. Malucelli, Bandwidth Reduced Full-Wave Simulation of Planar Microstrip Circuits. Journal Of Applied Comput. Electromagnetic Society, 1998. 13(2): p. 197-204.
3. Esposito, A., M. S. F. Catalano, F. Malucelli and L. Tarricone, A new matrix bandwidth reduction algorithm. Operations Research Letters, 1999. 23(3-5): p. 99-107.
4. Esposito, A., M. S. F. Catalano, F. Malucelli and L. Tarricone, Sparse Matrix Bandwidth Reduction: Algorithms, Applications and Real Industrial Cases in Electromagnetics, in High Performance Algorithms for Structured Matrix Problems, M. Paprzyky, Editor. 1999, Nova Science Publ.: p. 27-46.
5. Esposito, A., F. Malucelli and L. Tarricone. Bandwidth and profile reduction of sparse matrices:an experimental comparison of new heuristics. in ALEX'98. 1998. Trento.
6. Esposito, A., F. Malucelli and L. Tarricone, Bandwidth reduction of sparse symmetric and unsymmetric matrices: an experimental comparison of new heuristics, (1998) Università di Perugia.
7. Tarricone, L. and F. Malucelli, A new approach for the efficient solution of linear systems in moment methods using wavelet expansions, (1999) DIEI - Università di Perugia.
8. Tarricone, L., F. Malucelli and A. Esposito, Efficient Solution of Linear Systems in MW Numerical Methods. Int. Journal of Applied Comput. Electromagnetic Society, 1999. 13(3): p. 100-107.

This research has been carried out within my PhD thesis ("QAP: applications and solution methods", Dipartimento di Informatica - Università di Pisa 1993) under the supervision of Paolo Carraresi, where most of the results are summarized. If you are interested, feel free to ask me a copy of my thesis: I will be glad to send you a copy by snail mail.

List of papers

1. Carraresi, P. and F. Malucelli, Quadratic assignment problem: A review. Ricerca Operativa, 1988. 47: p. 3-32.
2. Carraresi, P. and F. Malucelli, A new branch and bound algorithm for the quadratic assignment problem, TR-14/90 (1990) Dipartimento di Informatica, Università di Pisa.
3. Carraresi, P. and F. Malucelli, A new lower bound for the quadratic assignment problem. Operations Research, 1992. 40, Supp. 1: p. S22-S27.Malucelli, F., Quadratic assignment problems: solution methods and applications, (1993) Dipartimento di Informatica, Università di Pisa.
4. Malucelli, F., A polynomially solvable class of quadratic semi-assignment problems. European Journal of Operational Research, 1996. (91): p. 619-622.
5. Malucelli, F. and D. Pretolani, Lower bounds for the quadratic semi-assignment problem, 955 (1993) C.R.T., Université de Montréal.
6. Malucelli, F. and D. Pretolani, Quadratic semi-assignment problems on structured graphs. Ricerca Operativa, 1994. 69: p. 57-78.
7. Malucelli, F. and D. Pretolani, Lower bounds for the quadratic semi-assignment problem. European Journal of Operational Research, 1995. 83(2): p. 365 - 375.
   

We test whether a given solution of a quadratic 0-1 problem is optimal. The research develops an algorithm based on the necessary and sufficient optimality condition introduced by Hirriart-Urruty for general convex problems. A measure of the quality of the solution is provided. Computational results show the applicability of the method. The method is extended to constrained quadratic 0-1 problems such as quadratic assignment and quadratic knapsack .

List of papers

1. Carraresi, P., F. Farinaccio and F. Malucelli, Testing optimality for quadratic 0-1 problems. Mathematical Programming, 1999. 85(2): p. 407-421.
2. Carraresi, P., F. Malucelli and M. Pappalardo, Testing optimality for quadratic 0-1 unconstrained problems. ZOR - Mathematical Methods of Operations Research, 1995. 42: p. 295-311.