Xjtu System Optimization And Scheduling Final Report

Posted on Edited on In Views: Waline: Word count in article: 7k Reading time ≈ 6 mins.

This is an automatically translated post by LLM. The original post is in Chinese. If you find any translation errors, please leave a comment to help me improve the translation. Thanks!

Application of Branch and Bound Method in Knapsack Problem

Final report for the course "System Optimization and Scheduling" at Xi'an Jiaotong University

1 Introduction

The Knapsack problem is a combinatorial optimization problem that is NP-complete. The problem can be described as follows: given a set of items, each with its own weight and value, and a limited total weight, how do we choose the items to maximize the total value while not exceeding the total weight of the knapsack? The name of the problem comes from the idea of choosing the most suitable items to put in the given knapsack. Similar problems often arise in fields such as business, combinatorial mathematics, computational complexity theory, cryptography, and applied mathematics.

2 Mathematical Description

The Knapsack problem can be divided into three categories based on the restrictions on the number of items: 0-1 Knapsack problem, Unbounded Knapsack problem, and Bounded Knapsack problem. In the 0-1 Knapsack problem, each item can only be selected once (either included in the knapsack or not). In the Unbounded Knapsack problem, there is no limit on the number of each item that can be included in the knapsack. In the Bounded Knapsack problem, each item has a specific limit on the number of times it can be included in the knapsack. The mathematical descriptions of these three types of Knapsack problems are explained below.

2.1 0-1 Knapsack Problem

The most basic Knapsack problem can be mathematically described as follows: given n items, where item i has a weight wi and a value vi, and a knapsack with a capacity W, we want to select a subset of items to maximize the total value while not exceeding the capacity of the knapsack. This can be formulated as the following optimization problem:

\[ \max \sum_{i=1}^nv_ix_i\\ s.t.\left\{ \begin{array}{**lr**} \sum_{i=1}^nw_ix_i\leq W\\ x_i\in\{0,1\} \end{array} \right. \]

2.2 Unbounded Knapsack Problem

The Unbounded Knapsack problem can be mathematically described as follows: given n items, where item i has a weight wi and a value vi, and a knapsack with a capacity W, we want to select a subset of items to maximize the total value while not exceeding the capacity of the knapsack. Unlike the 0-1 Knapsack problem, there is no limit on the number of each item that can be included in the knapsack. This can be formulated as the following optimization problem:

\[ \max \sum_{i=1}^nv_ix_i\\ s.t.\left\{ \begin{array}{**lr**} \sum_{i=1}^nw_ix_i\leq W\\ x_i\in N_+ \end{array} \right. \]

2.3 Bounded Knapsack Problem

The Bounded Knapsack problem can be mathematically described as follows: given n items, where item i has a weight wi, a value vi, and a quantity bi, and a knapsack with a capacity W, we want to select a subset of items to maximize the total value while not exceeding the capacity of the knapsack. Each item has a specific limit on the number of times it can be included in the knapsack. This can be formulated as the following optimization problem:

\[ \max \sum_{i=1}^nv_ix_i\\ s.t.\left\{ \begin{array}{**lr**} \sum_{i=1}^nw_ix_i\leq W\\ x_i\leq m_i\\ x_i\in N_+\\ \end{array} \right. \]

3 Solution Algorithms

3.1 Branch and Bound Algorithm

The Branch and Bound method is the most commonly used algorithm for solving integer programming problems. This method can be used to solve both pure integer programming problems and mixed integer programming problems. The Branch and Bound method is a search and iteration method that selects different branching variables and subproblems for branching. Typically, the entire feasible solution space is repeatedly divided into smaller and smaller subsets, called branching, and a lower bound is calculated for each subset of solutions (for minimization problems). This is called bounding. After each branching, those subsets whose bounds exceed the known feasible solution target value are no longer further branched, so many subsets can be ignored. This is the main idea of the Branch and Bound method. The steps of the Branch and Bound algorithm are as follows:

  1. For minimization problems, set the initial value of the best feasible solution to best = +∞.
  2. According to the branching rule, select a node (local solution) from the nodes (local solutions) that have not been fathomed, and branch it into several new nodes in the next level.
  3. Calculate the lower bound (LB) for each node based on the lower bound function.
  4. If the lower bound of a node is greater than the current best value, then the subsequent nodes do not contain feasible solutions, so this node will not be considered in the subsequent calculations. If a feasible solution with the smallest lower bound is found in this node, stop the downward search. Otherwise, continue to search downward with this node as an unfathomed node.
  5. Check if there are still unfathomed nodes. If there are, go to step 2. If there are no more unfathomed nodes, the algorithm stops, and the optimal solution is obtained.

The key to the Branch and Bound algorithm lies in the selection of branching rules and lower bound functions. Different problems have different ways of selecting them. In the Knapsack problem, the number of items included is used as the branching criterion, and different selection methods for each item result in different levels of the search tree. The lower bound function can be calculated by relaxing the constraint that the number of items included must be an integer. The specific algorithm is explained in the following sections.

3.2 Solving the 0-1 Knapsack Problem

In this problem, the calculation of the Lower Bound for a node is as follows:

  1. Calculate the unit value of each item, i.e., pi = vi/wi.
  2. Calculate the total weight w_sum and total value v_sum of the items that have already been determined (included/excluded).
  3. If w_sum > W, the node is infeasible. Otherwise, select the item with the highest unit value from the items that have not been determined and include it in the knapsack until the knapsack is full (at this point, a fractional number of items can be included, e.g., 6/7 items of type 2, the relaxation condition takes effect here). Calculate the total value v_sum of the items in the knapsack, which is the Lower Bound of the node.

The Branch and Bound algorithm proceeds as follows:

  1. Create an empty queue and put the root node into the queue.
  2. Select a node from the queue, generate its child nodes. If there are no child nodes, it means that the node is a feasible solution. Compare it with the current best solution. If it is smaller than the best solution, replace the current best solution. If there are child nodes, calculate the Lower Bound for each child node. If a child node is infeasible or its Lower Bound is greater than the current best solution, discard the node. Otherwise, add the node to the queue.
  3. Repeat step 2 until the queue is empty. The remaining best solution is the optimal solution to the problem.

The node generation algorithm is as follows:

  1. Find all items that have not been determined.
  2. Select the item with the highest unit value from these items.
  3. Generate two nodes: one with the item included and one with the item excluded.

In the Branch and Bound process, there are two main methods for selecting nodes from the queue:

  • FIFO (First-In-First-Out) selection, which selects nodes in the order they were added to the queue. The advantage is that it requires less storage space, but the disadvantage is that it requires a large amount of computation before reaching a feasible solution in order to update the best solution and perform pruning effectively.
  • Priority queue selection, which selects the node with the smallest Lower Bound from the queue for exploration. The advantage is that it requires less computation and allows for faster exploration and updating of feasible optimal solutions, making pruning more efficient. The disadvantage is that it requires more storage space.

Let's take a simple 0-1 Knapsack problem as an example:

The knapsack has a capacity of 10, and there are 5 items with their respective weights and values as shown in the table below:

Item 1 2 3 4 5
Weight 2 3 4 5 9
Value 3 4 5 8 10

The solution algorithm will be explained in the following sections.