Colloquium by Professor Paolo Toth

Colloquium by Prof Paolo Toth

Title: Formulations, Relaxations and Matheuristic Algorithms for the Quadratic Multiple Knapsack Problem

Abstract

The “Quadratic Multiple Knapsack Problem” (QMKP) generalizes two well-known maximization combinatorial optimization problems that have been intensively studied in the literature: the (single) “Quadratic Knapsack Problem” (QKP) and the “Multiple Knapsack Problem” (MKP). Owing to its many practical applications, as well as to its mathematical structure borrowing from well-studied combinatorial problems, the problem has received increasing attention in the literature over the last fifteen years, mostly concentrating on exponential-size formulations and metaheuristic approaches. QMKP is known to be strongly NP-hard.

In this talk, several polynomial-size formulations are considered, aiming at devising relaxations that produce good upper bounds in reasonable computing times. Linear models, obtained from classical reformulations of 0-1 quadratic programs, are described, and theoretical properties and dominances among them are investigated. Surrogate and Lagrangian relaxations are also proposed. We concentrate on the evaluation of the effectiveness of the Lagrangian relaxation when applied to the classical quadratic formulation and to a linear reformulation that leads to a decomposition into a set of independent, well-structured subproblems. Computational experiments on a large set of benchmark instances indicate that the use of specialized methods to solve the subproblems can be crucial to reduce the computing time and should be preferred to general purpose Mixed Integer Programming (MIP) solvers. These experiments also show that the QMKP is very difficult to solve in practice, and that exact algorithms are able to solve to optimality only small-size instances.

With the aim of solving larger instances, we propose effective metaheuristic algorithms, based on the Lagrangian Relaxation of the quadratic formulation, and on the optimal solution of Integer Linear Programming (ILP) models. Computational results on small-size benchmark instances and on new randomly generated medium-size instances are reported. These results show the good performance of the proposed algorithms, which are able to determine, within reasonable computing times, either optimal or nearly optimal solutions.

Short Bio

Paolo Toth is Professor Emeritus of Operations Research at the Department of Electrical and Information Engineering at the University of Bologna, where he was Full Professor from 1983 to 2011. His research interests include operations research and mathematical programming methodologies and, in particular, the design and implementation of effective exact and heuristic algorithms for combinatorial optimization and graph theory problems, and their application to real-world transportation, logistics, loading, routing, crew management, and railway optimization problems.

He is author of more than 180 papers published in international journals and of the book Knapsack Problems: Algorithms and Computer Implementations (co-author S. Martello; J. Wiley, 1990). He is also co-editor of the books The Vehicle Routing Problem (SIAM Monographs on Discrete Mathematics and Applications, 2002) and Vehicle Routing: Problems, Methods and Applications (MOS-SIAM Series on Optimization, 2014). He was President of EURO (Association of the European Operational Research Societies) for the period 1995-1996, and President of IFORS (International Federation of the Operational Research Societies) for the period 2001-2003.

He received several international awards, among which: the EURO Gold Medal (the highest distinction within Operations Research in Europe) in 1998; an honorary Doctorate in Operational Research (from the University of Montreal) in 2003; the Robert Herman Lifetime Achievement Award in Transportation Science (from INFORMS) in 2005; the IFORS Distinguished Lectures in 2012, the INFORMS Fellowship in 2016, and the EURO Distinguished Service Award in 2019.