Colloquium by Professor Paolo Toth
Fri, 08 Oct
|Online Event
Join us for a fascinating talk on Formulations, Relaxations and Matheuristic Algorithms for the Quadratic Multiple Knapsack Problem by Prof Paolo Toth


Time & Location
08 Oct 2021, 16:00 – 17:00 SAST
Online Event
Guests
About the Event
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…