A Local-Search-Based Heuristic for the Demand-Constrained Multidimensional Knapsack Problem.

INTEGER programming; HEURISTIC programming; KNAPSACK problems; CONSTRAINT satisfaction; ARTIFICIAL intelligence; MATHEMATICAL programming

We consider an extension of the 0–1 multidimensional knapsack problem in which there are greater-thanor-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. [ABSTRACT FROM AUTHOR]

Copyright of INFORMS Journal on Computing is the property of INFORMS: Institute for Operations Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)