[2021] Leeds - COMP3910 Combinatorial Optimisation - Final Exam - Q2-8 Knapsack Problem
Questions 2-8 deal with the same instance of the knapsack problem. In that instance, there are n = 4 items of different sizes and profit values, and no repeated items (there is exactly one item of each type). The characteristics of the items are given in the table:
Notice that the items are numbered in the decreasing order of the ratios cj
The knapsack capacity is b = 13, which means that we can place only a selection of items in the knapsack with the sum of sizes not exceeding 13. It is required to select items so that the sum of their profits is as high as possible and the knapsack capacity is not exceeded.
If the items are indivisible, then we can either place a whole item or reject it. The corresponding ILP formulation is of the form: where n = 4 and variables xj indicate whether item j is selected or not.
Question 2 (construction heuristics) [4 marks]
Four construction heuristics are stated below. Apply them to instance (1). For each solution found, state the value of the objective function.
2.1 Heuristic “The most profitable item first, with respect to the relative cost, calculated as the ratio profitsize ”.
2.2 Heuristic “The most profitable item first, with respect to the absolute cost cj ”.
2.3 Heuristic “Largest item first”.
2.4 Heuristic “Smallest item first”.
Question 3 (improvement heuristic) [6 marks]
Consider again instance (1) of the knapsack problem. Illustrate how it can be solved by iterative improvement with transpose neighbourhood. To generate solutions, select a sequence of items and place them in the knapsack, one by one, in the order they appear in the sequence, without exceeding the knapsack capacity and without splitting the items. Start with the initial solution which arises from the sequence (4; 1; 3; 2).
Fill in the table presented below, replacing * by your entries. In the last column indicate whether a neighbour is accepted to replace the current one. Perform two iterations. Do not proceed with subsequent iterations.
Question 4 (approximation algorithm for the knapsack problem) [4 marks]
Solve instance (1) of the knapsack problem by the approximation algorithm Ext-Greedy. It is known that Ext-Greedy is an approximation algorithm with the approximation ratio = 1=2. Using the definition of an approximation algorithm, derive an upper bound on the optimal value of the objective.
Submission:
solution found by Ext-Greedy and the corresponding value of the objective;
an upper bound on the optimal value of the objective.
Question 5 (Branch-and-Bound for the knapsack problem) [12 marks]
Solve instance (1) of the knapsack problem by the Branch-and-Bound algorithm. Use the implementation presented in Chapter 7 “Branch-and-Bound Algorithm”. Note one point of difference in the problem definition: the problem in Chapter 7 has the constraint “xj and integer”, while the current problem assumes Therefore the search tree for instance (1) should have two child nodes per node, corresponding to xj = 1
and xj = 0.
The formula for calculating upper bounds remains the same:
To get started, consider the search tree presented in Fig.1, with the left subtree fully elaborated and the right subtree being incomplete.
Complete the right subtree. Use the depth-first strategy. Indicate the upper bounds for the nodes and updates of the lower bound. Number the nodes in the order they are generated, starting from 11 (there are 10 nodes already produced). Specify the optimal solution and the corresponding objective value.
Get the Solution to This Question
WeChat (微信)
WhatsApp
