Maximizing Efficiency – The Knapsack Problem

Posted on by Dinh Quan Tran

One of the most prominent aims, if not the most important, of Applied Mathematics lies in maximizing the efficiency of its subjects. Almost every industry and discipline in this world uses mathematical models to increase productivity as well as selecting the best targets for the given resources. This gives rise to a separate discipline of Applied Mathematics, namely Mathematical Optimization, which today we will look at along with one of its most important problems, the Knapsack Problem.

  1. What is Mathematical Optimization: 

A very formal definition would be:

“Mathematical optimization or mathematical programming is the selection of a best element (with regard to some criterion) from some set of available alternatives.”

From this definition, we can surely realize the very basic elements of what an optimization problem might look like. Of course there is the input, which are the ingredients or resources that you are willing to spend to achieve your goal. There are also given constraints which limits your options for your goal (for example, the constraint “bad weather” might prevent you from achieving your 10-kilometer run although the input – your strength – is enough provided that the weather is good). After passing your input through all the constraints, you will now possess a limited number or range of options, and the task for the mathematical model would be to select the best choice from those options.

Let’s look at an example below to see the interactions of input, constraints and output:

You are tasked to buy six kilograms of potatoes. There are two types you can buy: 2-kilogram bags costing $5 and 1-kilogram bags costing $3. Calculate the least amount of money to spend?

If all given data is just as above, we can easily deduce the least amount of money spent to be $15 by buying three 2-kilogram bags (the reason being that 2-kilogram bags cost less per kilogram at $2.5 compared to 1-kilogram bags at $3). However, if one more constraint is given:

The number of 2-kilogram bags must be smaller than 3.

then the answer changes to $16 (two 2-kilogram bags and two 1-kilogram bags). So constraints do greatly impact the results of optimization problems, and it is important that procedures adhere to them strictly to produce the best results.

Another question might be: Why is mathematical programming an alternative name to mathematical optimization? There are several reasons. First, mathematical optimization basically defines the operating procedures for the system to follow in order to achieve maximum results; so in some sense it basically “writes the program” for the system, resulting in the name. Secondly, mathematical optimization is easily one of the most computer-dependent branches of mathematics. Sure, we can calculate by hand the most simple of optimization problems, but for greater ones that can involve thousands of variables and inputs along with numerous constraints, it is ill-advised and sometimes even impossible to do so. With its impressive processing speed, computers are a much more viable way of approach, thus the name “mathematical programming”.

With that set, we can now proceed to one of the signature problems of the field.

  1. The Knapsack Problem:

…or rather, how to fill the knapsack with the most value?

The Knapsack Problem and its variations are more often the most commonly found problems in Optimization, partly due to its rather non-specific requirements allowing for many different combinations of inputs and constraints to be used. The underlying idea is to fill the most valuable items, or any other objects with a value, into a fixed-size knapsack or any other given constraints. Among the variations, three generalizations are often recognized:

  • The 0-1 knapsack problem:

Given a set of \displaystyle {n} items numbered from 1 up to \displaystyle {n} , each with a weight \displaystyle {w_{i}} and a value \displaystyle {v_{i}} , along with a maximum weight capacity \displaystyle {W} ,

Maximize \displaystyle {\sum _{i=1}^{n}v_{i}x_{i}}

subject to \displaystyle {\sum _{i=1}^{n}w_{i}x_{i}\leq W} and \displaystyle {x_{i}\in \{0,1\}}

  • The bounded knapsack problem:

Basically a harder version of the 0-1 knapsack problem, the bounded knapsack problem replace the constraint of maximum one copy per item and instead replacing it with a predefined maximum number of copy for every item:

Maximize \displaystyle {\sum _{i=1}^{n}v_{i}x_{i}}

subject to \displaystyle {\sum _{i=1}^{n}w_{i}x_{i}\leq W} and \displaystyle {x_{i}\in \{0,1,...,c_{i}\}}

  • The unbounded knapsack problem:

The unbounded knapsack problem removes the maximum number of items altogether:

Maximize \displaystyle {\sum _{i=1}^{n}v_{i}x_{i}}

subject to \displaystyle {\sum _{i=1}^{n}w_{i}x_{i}\leq W}

Funnily enough, the example I gave above is a Knapsack problem. Did you spot it?

See you next week!

Unknown's avatar

Author:

Leave a comment