Projekt: K-item Quadratic Knapsack Problems

Stammdaten
K-item Quadratic Knapsack Problems
Beschreibung: Wir behandeln das Rucksackproblem mit quadratischer Zielfunktion und der Zusatzbedingung, dass exakt k Gegenstaende eingepackt werden muessen. Dieses NP-schwere Problem ist im Allgemeinen fuer Instanzen mit mehr als 40 Knoten nicht mehr loesbar. Wir entwickeln ein exaktes Loesungsverfahren fuer diese Problem, indem wir einen Branch-and-Bound Algorithmus impelmentieren. Zur Berechnung von oberen Schranken verwenden wir eine Semidefinite Relaxierung, waehrend die untere Schranke mittels einer effizienten Heuristik von Letocart et al. ermittelt wird.
Schlagworte: Semidefinite Problems, K-item Quadratic Knapsack Problems
K-item Quadratic Knapsack Problems
Beschreibung: The k-item quadratic knapsack problem consists of maximizing a quadratic function subject to two linear constraints: the first one is the classical liinear capacity constraint; the second one is an equality cardinality constraint on the number of items in the knapsack. The problem is NP-hard and instances can be solved in a routine way only up to 40 variables. We want to develop an exact solution algorithm where we combine a semidefinite programming based bounding routine with a hybrid heuristic.
Schlagworte: Semidefinite Problems, K-item Quadratic Knapsack Problems
Kurztitel: n.a.
Zeitraum: 01.02.2013 - 01.01.2014
Kontakt-Email: -
Homepage: -

MitarbeiterInnen
MitarbeiterInnen Funktion Zeitraum
Angelika Wiegele
angelika.wiegele@aau.at
Institut für Mathematik
Forschungsaktivitäten
zur Visitenkarte
(intern)
  • Projektleiter/in
  • 01.02.2013 - 01.01.2014

Zuordnung
Organisationseinheit
Fakultät für Technische Wissenschaften
  Institut für Mathematik
Universitätsstraße 65-67
9020 Klagenfurt am Wörthersee
Österreich
   math@aau.at
https://www.aau.at/mathematik
zur Organisation

Kategorisierung
Projekttyp laufender Arbeitsschwerpunkt
Förderungstyp Sonstiger
Forschungstyp
  • Grundlagenforschung
  • Angewandte Forschung
Sachgebiete
  • 1104 - Angewandte Mathematik *
  • 1120 - Kombinatorik *
  • 1121 - Operations Research (5347, 5919) *
Forschungscluster Kein Forschungscluster ausgewählt
Genderrelevanz 0%
Projektfokus
  • Science to Science (Qualitätsindikator: I)
Klassifikationsraster der zugeordneten Organisationseinheiten:
Arbeitsgruppen Keine Arbeitsgruppe ausgewählt

Finanzierung
Keine Förderprogramme vorhanden

Kooperationen
Organisation Adresse
Université Paris 13
99 Avenue Jean Baptiste Clément
93430 Villetaneuse, Paris
Frankreich
99 Avenue Jean Baptiste Clément
FR - 93430  Villetaneuse, Paris