Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Dynamic Sparsification for Quadratic Assignment Problems
Speaker:Maximilian John
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 2 July 2019
Duration:30 Minutes
Building:E1 4
We present a framework for optimizing sparse quadratic assignment problems.

We propose an iterative algorithm that dynamically generates the quadratic part of the assignment problem and, thus, solves a sparsified linearization of the original problem in every iteration.
This procedure results in a hierarchy of lower bounds and, in addition, provides heuristic primal solutions in every iteration.
This framework was motivated by the task of the French government to design the French keyboard standard, which included solving sparse quadratic assignment problems with over $100$ special characters; a size where many commonly used approaches fail.
The design of a new standard
often involves conflicting opinions of multiple stakeholders in a committee.
Hence, there is no agreement on a single well-defined objective function that can be used for an extensive one-shot optimization.
Instead, the process is highly interactive and demands rapid prototyping, e.g., quick primal solutions, on-the-fly evaluation of manual changes, and prompt assessments of solution quality.
Particularly concerning the latter aspect, our algorithm is able to provide high-quality lower bounds for these problems in several minutes.

Name(s):Maximilian John
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Keywords:Quadratic Assignment; Integer Programming; Linearization; Keyboard Optimization
Attachments, File(s):

Maximilian John/MPI-INF, 06/11/2019 04:00 PM
Last modified:
Uwe Brahm/MPII/DE, 07/02/2019 04:01 AM
  • Maximilian John, 06/11/2019 04:00 PM -- Created document.