Artikel im European Journal of Operational Research veröffentlicht

Im Rahmen unserer engen Zusammenarbeit mit Forschung und Wissenschaft hat unser Kollege Dr. Sebastian Blanc gemeinsam mit unserem Beiratsmitglied Prof. Dr. Thomas Setzer einen Beitrag im European Journal of Operational Research veröffentlicht.

Im Artikel mit dem Titel "Empirical Orthogonal Constraint Generation for Multidimensional 0/1 Knapsack Problems" wird ein neuartiger Ansatz zur Lösungen von sogenannte multidimensionalen Rucksackproblemen vorgestellt. Das multidimensionale Rucksackproblem ist eine Erweiterung des Rucksackproblems, das sich folgendermaßen verbildlichen lässt: Angenommen, es soll ein Rucksack beladen werden, der eine Gewichtsbeschränkung hat. In den Rucksack können verschiedene Artikel mit jeweils unterschiedlicher Nützlichkeit, aber auch unterschiedlichem Gewicht eingepackt werden. Zielsetzung ist nun, genau die Artikel auszuwählen, die den Gesamtnutzen maximieren und gleichzeitig die Gewichtsbeschränkung einhalten. Das multidimensionale Rucksackproblem ist eine Verallgemeinerung dieses Problems, in dem nicht nur das Gesamtgewicht begrenzt ist, sondern noch weitere Beschränkungen bestehen.

Ein realer Anwendungsfall für das multidimensionale Rucksackproblem ist das Verteilen von virtuellen Maschinen auf möglichst wenige physikalische Server, wobei u.a. Rechenlast, Speicherkapazität etc. berücksichtigt werden müssen. Dieses Problem hat eine sehr hohe Komplexität, die insbesondere durch die Anzahl der Beschränkungen beeinflusst wird. Im Artikel wird aus diesem Grund ein neuartiger Ansatz vorgestellt, der die Anzahl der Beschränkungen reduziert. Hierfür werden Ideen der Dimensionsreduktion aus dem Bereich der Data Science genutzt und auf das multidimensionale Rucksackproblem übertragen. Insgesamt werden somit insbesondere komplexe Probleme deutlich schneller lösbar.

Den Beitrag finden Sie hier.