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. Keywords: Integer Programming; Heuristic Algorithms; Multidimensional Knapsack

A LOCAL SEARCH BASED HEURISTIC FOR THE DEMAND CONSTRAINED MULTIDIMENSIONAL KNAPSACK PROBLEM / P. CAPPANERA; M. TRUBIAN. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - ELETTRONICO. - 17:(2005), pp. 82-98. [10.1287/ijoc.1030.0050]

A LOCAL SEARCH BASED HEURISTIC FOR THE DEMAND CONSTRAINED MULTIDIMENSIONAL KNAPSACK PROBLEM

CAPPANERA, PAOLA;
2005

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. Keywords: Integer Programming; Heuristic Algorithms; Multidimensional Knapsack
17
82
98
P. CAPPANERA; M. TRUBIAN
File in questo prodotto:
File Dimensione Formato  
IJOC-MDMKP.pdf

Accesso chiuso

Tipologia: Altro
Licenza: DRM non definito
Dimensione 188.14 kB
Formato Adobe PDF
188.14 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2158/1812
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 24
  • ???jsp.display-item.citation.isi??? 20
social impact