A local-search-based heuristic for the demand-constrained multidimensional knapsack problem
Articolo
Data di Pubblicazione:
2005
Citazione:
A local-search-based heuristic for the demand-constrained multidimensional knapsack problem / P. Cappanera, M. Trubian. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - 17:1(2005), pp. 82-98. [10.1287/ijoc.1030.0050]
Abstract:
We consider an extension of the 0–1 multidimensional knapsack problem in which there are greater-than-or-
equal-to inequalities, called demand constraints, in addition to the standard less-than-or-equal-to constraints.
Moreover, the objective function coefficients are not constrained in sign. This problem is worth considering
because it is embedded in models of practical application, it has an intriguing combinatorial structure,
and it appears to be a challenging problem for commercial ILP solvers. Our approach is based on a nested tabu-search
algorithm in which neighborhoods with different structures are exploited. First, a tabu-search procedure
is carried out in which mainly the infeasible region is explored. Once feasibility has been established, a second
tabu-search procedure, which analyzes only feasible solutions, is applied. The algorithm has been tested on a
wide set of instances. Computational results are discussed.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
integer programming; heuristic algorithms; multidimensional knapsack
Elenco autori:
P. Cappanera, M. Trubian
Link alla scheda completa: