关于算法:BTH004

BTH004 – Laboratory assignment 1
In this laboratory assignment you should design and implement algorithms
for the multiple knapsack problem. The assignment contains two parts; one is
mandatory and one is optional.
In part 1 (the mandatory part) you should design and implement two algorithms
for the multiple knapsack problem:

1. A (contructive) greedy algorithm.
2. An improving search (neighborhood search) algorithm.
   Part 2 (the optional part) concerns implementing a tabu-search algorithm
   (a meta-heuristic) for the considered problem.
   The assignment should be conducted individually, and it will be examined
   through a written report (one per student). The report should fulfill the requirements
   specified below.
   The deadline for submitting the report is announced by Zhenbo Cheng.
   Note that you are allowed to use any high-level programming language you
   find suitable, e.g., java, c, c++, and python.
   It is highly recommended that you start working with the assignment as soon
   as possible. It is of particular importance that you start before the scheduled
   supervision time, so that you can make as much use as possible of the teacher
   support.
   The knapsack problem
   The (standard) knapsack problem, which was introduced earlier in the course,
   can be described in the following way. Assume that you have a set of items, each
   with a (positive) weight and a (positive) value, and a knapsack (or bag) with a
   limited weight capacity. The problem is to choose (to include in the knapsack)
   items so that the weight capacity of the knapsack is not violated and the value
   of the chosen items are as high as possible.
   Mathematically, the problem can be formulated in the following way. We let
   I = {1, . . . , n} be an index set over the n items, where item i ∈ I have a value
   pi > 0 and a weight wi > 0, and we let W > 0 denote the weight capacity of the
   knapsack. For item i ∈ I, the binary decision variable xi
   is used to determine
   whether to include item i in the knapsack: xi = 1 if the item is chosen, and
   xi = 0 if it is not chosen.
   The objective function of the problem is to maximize the utility of the chosen
   items, i.e.,
   MaximizeX
   i∈I
   pixi
   .
   1
   All valid solutions to the problem should fulfill the weight constraint
   X
   i∈I
   wixi ≤ W,
   and the values of the decision variables are restricted by the constraint set
   xi ∈ {0, 1} ∀i ∈ I.
   The multiple knapsack problem
   The multiple knapsack problem is an extension to the standard knapsack problem
   in that it considers choosing items to include in m knapsacks (the standard
   knapsack problem considers only one knapsack).
   Mathematically, the multiple knapsack problem can be formulated as follows.
   We let I = {1, . . . , n} be an index set over the n items, where item i ∈ I have
   a value pi > 0 and a weight wi > 0. In addition, we let J = {1, . . . , m} be an
   index set over the m knapsacks, where Wj > 0 denotes the weight capacity of
   knapsack j ∈ J. For item i ∈ I and knapsack j ∈ J, we let the binary decision
   variable xij determine whether to include item i in knapsack j: xij = 1 if item
   i is included in knapsack j, otherwise xij = 0.
   The objective function of the problem is to maximize the utility of the chosen
   items, i.e.,
   MaximizeX
   i∈I
   X
   j∈J
   pixij .
   For each of the knapsacks, the solution space is restricted by a weight capacity
   constraint, which states that the total weight of the selected items for that
   knapsack is not allowed to exceed the weight capacity of the knapsack. This
   is modeled by the following constraint set (one constraint for each of the m
   knapsacks):
   X
   i∈I
   wixij ≤ Wj , j ∈ J.
   In addition, it needs to be explicitly modeled that an item is not allowed to be
   included in more than one of the knapsacks. This is modeled by the following
   constraint set (one constraint for each of the n items):
   X
   j∈J
   xij ≤ 1, i ∈ I.
   Finally, the values of the decision variables are restricted by the constraint set
   xij ∈ {0, 1}, i ∈ I, j ∈ J.
   Part 1 – Greedy and neighborhood search algorithms
   In the first part (the mandatory part), you should design and implement 1)
   a greedy algorithm and 2) a neighborhood search algorithm for the multiple
   knapsack problem.
   2
   Greedy algorithm
   As discussed earlier in the course, a greedy algorithm is an algorithm that starts
   with an empty solution, and iteratively adds solution components to partial
   solution until a complete solution is found.
   For knapsack problems, it is possible to construct greedy algorithms that are
   based on the relative benefit per weight unit for the considered items. We let
   bi =
   pi
   wi
   denote the relative benefit per weight unit for item i ∈ I. By comparing
   bi
   ′ =
   pi
   ′
   wi
   ′
   and bi
   ′′ =
   pi
   ′′
   wi
   ′′
   for two items i
   ′
   , i′′ ∈ I, it is possible to make a greedy
   decision on which item to include. If bi
   ′ > bi
   ′′ (i.e., bi
   ′ gives higher value per
   weight unit than bi
   ′′ ) it seems better to choose bi
   ′ than bi
   ′′ for some of the m
   knapsacks. On the other hand, if bi
   ′ < bi
   ′′ it seems better to include bi
   ′′ than
   bi
   ′ in some of the m knapsacks. If bi
   ′ = bi
   ′′ , it does not matter which one to
   choose, since bi
   ′ and bi
   ′′ in this case gives the same value per weight unit.
   A greedy algorithm for the multiple knapsack problem could be designed by
   iteratively adding to some knapsack the item with highest relative benefit (i.e.,
   i
   ′ = arg maxi∈I
   (bi), such that i
   ′ has not already been included in an earlier
   iteration).
   Please note that there are algorithm details not discussed above, which you
   need to define yourself1
   . For example, termination criteria and choice of knapsack
   in case there is sufficient amount of capacity in more than one of the
   knapsacks, has not been discussed above. In addition, you need to consider
   what you should do if there is no capacity for the item with highest relative
   value, but there are other items with smaller weight that can be added.
   Improving search (neighborhood search) algorithm
   Improving search heuristics are algorithms that iteratively improve a feasible
   solution by doing small modifications of the most recent solution.
   For a solution x, we define a neighborhood N(x) as all solutions“close
   enough”to x (according to some criteria). If y ∈ N(x), then y is a neighbor of
   x.
   Neighborhood search algorithms are improving search algorithms where a
   current solution is iteratively updated by choosing the“best”solution in the
   neighborhood of the current solution. An algorithm description (for a maximization
   problem) is provided below.
   Step 0: Find a feasible (starting) solution x
   (0) with value (cost) c(x
   (0)) and set
   solution index t = 0.
   Step 1: Determine (all points in) neighborhood N(x
   (t)
   ).
   Step 2: If c(x
   (t)
   ) ≥ c(x) ∀ x ∈ N(x
   (t)
   ), then break with local optimal solution
   x
   (t)
   .
   Step 3: Choose x
   (t+1) ∈ N(x
   (t)
   ) such that c(x
   (t+1)) ≥ c(x
   t
   )
   Set t = t + 1 and goto step 1.
   As starting solution to the neighborhood search algorithm, you could, for
   example, use the solution obtained by your greedy algorithm.
   1
   It is typically a good idea to test different approaches to see which performs best
   3
   A challenge is how to determine an appropriate neighborhood for the multiple
   knapsack problem. If the neighborhood is too large, it will be impossible to
   iterate over all solutions in the neighborhood, if it is too small, there is a high
   risk that the algorithm will get stuck in a local optima that is not so good.
   A possible way to define a neighborhood is to rotate items. As long as you
   have at least one item that is not included in any knapsack, you could define the
   neighborhood of a solution as all other feasible solutions that can be obtained
   by:
   • Moving some item (i
   ′
   ) from one knapsack (m′
   ) to another knapsack (m′′).
   • Moving some other item (i
   ′′) away from knapsack (m′′) (in order to make
   room for item i
   ′
   ). In the obtained solution, i
   ′′ is not included in any of
   the knapsacks.
   • Moving some other item (i
   ′′′), which is not included in any knapsack in
   the current solution, into knapsack m′
   .
   If bi
   ′′′ > bi
   ′′ a better solution has been found.
   When using this type of neighborhood, it is important to consider that it
   might be possible to, via rotations, make room for an additional item in some
   of the knapsacks after some item has been replaced by some other item. This
   needs to be explicitly included in the neighborhood definition.
   You are encouraged to identify some other neighborhood that you find appropriate
   for the considered problem. For example, you might find it interesting
   to consider rotation involving more than 3 items; however you need to consider
   that this increases the search space significantly.
   Part 2 – Tabu-search
   A problem with the neighborhood search heuristics is that they eventually will
   get stuck in a locally optimal solution. A locally optimal solution is a solution
   that cannot be improved by moving to any of the solutions that are sufficiently
   close in the search space (i.e., in the neighborhood), but there are solutions
   farther away that are better.
   The ideas of tabu-search methods, which are based on neighborhood search,
   are:
   • It is possible to move to a solution with worse objective if there is no
   improving solution in the neighborhood (note that it is necessary to keep
   track of the so far best found solution).
   • The k most recent solutions are tabu, i.e., they cannot be visited (otherwise
   the algorithm might immediately go back to the locally optimal
   solution).
   Tabu search algorithms (for maximization problems) can be described in a
   general way using the following algorithm description.
   Step 0: Find a feasible (starting) solution x
   (0) with value (cost) c(x
   (0)) and set
   solution index t = 0.
   4
   Step 1: Determine breaking criteria. For instance, break if maximum number
   of iterations has been reached, or no non-tabu solutions exists.
   Step 2: Determine neighborhood N(x
   (t)
   ).
   Step 3: Choose x
   (t+1) ∈ N(x
   (t)
   ) which is not in the tabu-list, and which maximizes
   c(x).
   Step 4: Update tabu-list (remove the oldest solution in the tabu-list and add
   the most recent solution, i.e., x
   (t)
   ), set t = t + 1 and go to step 1.
   In part 2 (the optional part) you are encouraged to extend your neighborhood
   search algorithm into a tabu-search algorithm.
   Requirements on report