top of page

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

Registration is Closed
See other events
Colloquium by Professor Paolo Toth
Colloquium by Professor 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…

Share This Event

bottom of page