Bibliographische Daten exportieren
Literatur vom gleichen Autor
plus im Publikationsserver
plus bei Google Scholar

Lesezeichen anlegen

Empirical orthogonal constraint generation for Multidimensional 0/1 Knapsack Problems


Verfügbarkeit überprüfen

Setzer, Thomas ; Blanc, Sebastian M.:
Empirical orthogonal constraint generation for Multidimensional 0/1 Knapsack Problems.
In: European Journal of Operational Research. 282 (2020) 1. - S. 58-70.
ISSN 0377-2217


Link zum Volltext (externe URL): https://doi.org/10.1016/j.ejor.2019.09.016


Existing techniques for solving large Multidimensional Knapsack Problems (MKP) aim at reducing the number of variables (items). While these approaches solve problems with many items efficiently, their performance declines with increasing number of constraints. We propose empirical orthogonal constraint generation (EOCG) to reduce the number of constraints. The intuition is that, geometrically, each constraint is a dimension of a hypercube, with capacity as side length, while items correspond to vectors with their weights as coordinates along the dimensions–the basis vectors. MKP problems guarantee the feasibility of a solution by one constraint on the coordinate sum for each dimension. In contrast, EOCG aims at reducing the number of dimensions to be constrained by using new basis vectors to represent the optimal item set with less coordinates. The key challenge is that a concise problem representation has to be formulated so that its solution also solves the original MKP. EOCG allows for this transfer by successively choosing new dimensions so that capacity violations on the next dimension added decline with a steep descent until a valid and optimal solution is found. We evaluate EOCG on established benchmark instances, which EOCG often solves in lower dimensions. EOCG finds the currently best-known solutions to all high-dimensional Chu and Beasley instances, improves the best-known solutions to two Glover and Kochenberger instances, and proves the optimality of a solution to another instance.

Weitere Angaben

Zusätzliche Informationen:Corrigendum to Section 5: https://doi.org/10.1016/j.ejor.2019.12.029
Schlagwörter:Multidimensional Knapsack Problem; Dimension reduction; Constraint generation
Institutionen der Universität:Wirtschaftswissenschaftliche Fakultät > Betriebswirtschaftslehre > Lehrstuhl für Allgemeine Betriebswirtschaftslehre und Wirtschaftsinformatik
DOI / URN / ID:10.1016/j.ejor.2019.09.016
Titel an der KU entstanden:Ja
Eingestellt am:24. Sep 2020 13:56
Letzte Änderung:06. Okt 2020 15:58
URL zu dieser Anzeige:http://edoc.ku-eichstaett.de/24891/