The 0-1 Multidimensional Knapsack Problem


This web page is intended to give some additional information as support to the abstract PaperId = 495

"Tabu Search for 0-1 Multidimensional Knapsack Revisited: 
Choosing Internal Heuristics and Fine Tuning of Parameters"

authored by M. Josep Blesa, Lluís Hernàndez and Fatos Xhafa 
submitted to YOR 12 Workshop

We have used the TS skeleton (see [BX00b]) to implement the Knapsack Problem.  The design part of an instanced problem is equal to the design part of the skeleton, just because this part describes the internal working of the method and that part is generic enough not to depend on the problem.  The part to be filled by the filler user depends totally on the problem to be instanciated.

Two inputs are needed for the execution of a Knapsack instance:

The problem, that consists of :
  • The number of variables (n), i.e. the number of items to be selected for the knapsack.
  • The number of constraints (m) for the knapsack.
  • The best known fitness (not used by now)
  • An array (c) of dimension n representing the benefits of items (real positive numbers).
  • A matrix A mxn representing the restrictions of the problem (real positive numbers).
  • An array b of dimension m representing the capacities (real positive numbers).
  • The setup parameters needed (by now) are: 
  • The number of independent runs
  • The number of iterations per run
  • A boolean indicating if a delta function is used (faster computation of the fitness)
  • The maximum number of neighbors to explore for each local search
  • The tabu size
  • The maximum number of iterations that a movement can be considered tabu
  • The minimum number of iterations that a movement is considered tabu
  • The maximum number of iterations that the "same" solution is allowed to be obtained
  • The number of iterations that the diversification is applied if it occurs
  • The number of iterations that the intensification is applied if it occurs
  • The number of best solutions maintained as the history needed for the intensification
  • A percentage to calculate the parameter REP of the diversification
  • The seconds the execution will be running.

  • These input values can be stored in an ascii file and introduced to the program using the << operator.   The state of the algorithm is reported to the standard output every iteration.   Some statistics are also reported at the end of every run.

    If you are interested in the executable code, please send mail to mjblesalsi.upc.es. We would send you the code as well as the readme file. This information will appear here within a few days.