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…