Empirical orthogonal constraint generation for Multidimensional 0/1 Knapsack Problems

Thomas Setzer and Sebastian M. Blanc

European Journal of Operational Research, 2020, vol. 282, issue 1, 58-70

Abstract: 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.

Keywords: Multidimensional Knapsack Problem; Dimension reduction; Constraint generation (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719307568
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:282:y:2020:i:1:p:58-70

DOI: 10.1016/j.ejor.2019.09.016

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().