<a rel="license" href="http://creativecommons.org/licenses/by/4.0/"></a><br /><span xmlns:dct="http://purl.org/dc/terms/" property="dct:title"><b>The Knapsack Problem</b></span> by <a xmlns:cc="http://creativecommons.org/ns#" href="http://mate.unipv.it/gualandi" property="cc:attributionName" rel="cc:attributionURL">Stefano Gualandi</a> is licensed under a <a rel="license" href="http://creativecommons.org/licenses/by/4.0/">Creative Commons Attribution 4.0 International License</a>.<br />Based on a work at <a xmlns:dct="http://purl.org/dc/terms/" href="https://github.com/mathcoding/opt4ds" rel="dct:source">https://github.com/mathcoding/opt4ds</a>.

# 3. The Knapsack Problem
In this first notebook, we show how to solve the Knapsack Problem using Integer Linear Programming.

## 3.1 Software Installation
If you are running this notebook in a Colab, you don't need to install anything else on your computer.

Otherwise, if you have installed the recommended Anaconda Python distribution, you have to run the following two commands:

1. To install the [Pyomo](http://www.pyomo.org/) optimization modeling language:

```
conda install -c conda-forge pyomo
```

2. To install the open source [GLPK](https://www.gnu.org/software/glpk/) solver:

```
conda install -c conda-forge glpk
```

3. (Optional) You can install some extra packages of Pyomo using the following command:

```
conda install -c conda-forge pyomo.extras
```

For details about the Pyomo installation, we refer to the official [Pyomo Documentation](https://pyomo.readthedocs.io/en/stable/).

The following lines are for running this notebook in a COLAB:


```python
import shutil
import sys
import os.path

if not shutil.which("pyomo"):
    !pip install -q pyomo
    assert(shutil.which("pyomo"))

if not (shutil.which("glpk") or os.path.isfile("glpk")):
    if "google.colab" in sys.modules:
        !apt-get install -y -qq glpk-utils
    else:
        try:
            !conda install -c conda-forge glpk 
        except:
            pass
```

## 3.2 Mixed Integer Programming model
The Knapsack problem can be formulated as follows.

The input data are: 

* The index set $I$ referring to the items
* The profit vector $c$
* The weight vector $A$
* The budget value $B$

For each item $i\in I$, we introduce a binary decision variables $x_i \in \{0,1\}$, which is used to define the following **Integer Linear Programming (ILP)**
problem:

\begin{align}\label{eq:1}
\max \;\; & c^T x \\
\mbox{s.t.} \;\; & \sum_{i \in I} A_i x_i \leq B & \\
& x_i \in \{0,1\},& \forall i \in I.
\end{align}


Since $x_i=1$ represents the decision of selecting item the $i$-th item, it is clear that the objective function (1) consists of maximizing the dot product $c^T\,x$. The single constraint (2) limits the number of selected item in such a way that the sum of the weights $A_i$ of the selected items does not exceed the available capacity $B$. The constraints (3) impose the domain on the decision variables $x_i$. 

## 3.3 Pyomo Knapsack Model
The ILP model (1)-(3) can be expressed using the Pyomo optimization modeling language as shown next.

As a first step, we need to define the input data using the standard Python data structure. The simplest method to define the data is as follows:


```python
I = range(5)        # Items
C = [2, 3, 1, 4, 3] # Profits
A = [3, 4, 2, 1, 6] # Weights
B = 9               # Budget
```

This snippet of code is defining the following input data:

* The set $I$ as the range of number from 0 to 4, using the [range](https://docs.python.org/3/library/functions.html#func-range) builtin class. You can think of the range as a generator function for the list $[0,1,2,3,4]$.
* The cost vector $C$ and the weight vector $A$ are defined as two lists, using the standard [list()](https://docs.python.org/3/library/functions.html#func-list) builtin class.
* The budget parameter is defined as a given integer.

So far, we have not used any **Pyomo** construct. Before we start, we need to import the Pyomo library:


```python
from pyomo.environ import *
```


```python
# If you want to check all the elements imported from the library uncomment the following line
# who
```

### 3.3.1 Model and Variables
The first step in defining the model consists in choosing the type of Model we want to use. In Pyomo there are two options, the [ConcreteModel](https://pyomo.readthedocs.io/en/stable/library_reference/aml/index.html#pyomo.environ.ConcreteModel) and the [AbstractModel](https://pyomo.readthedocs.io/en/stable/library_reference/aml/index.html#pyomo.environ.AbstractModel). In this first example, we use the simpler ConcreteModel as follows:


```python
# Create concrete model
model = ConcreteModel()
```

The choice of the `model` name is recommended if you are planning to use the Pyomo command line tool.

Once we have defined the model, we can define the binary decision variable by using the [Var](https://pyomo.readthedocs.io/en/stable/library_reference/aml/index.html#pyomo.environ.Var) class. We define an object of type **Var** for each element of the range $I$, with the following command:


```python
# Variables
model.x = Var(I, within=Binary)
```

The `Binary` keyword is part of the `pyomo.environ` setting, and it is used to specify the constraint $x_i \in \{0,1\}$. Other possible values for the optional parameter `within` are: `NonNegativeReals`, `PositiveReals`, `PositiveIntegers`.

Note the the choice of $x$ as a name of the variable is arbitrary. 

### 3.3.2 Objective Function
The objective function is defined via the [Objective](https://pyomo.readthedocs.io/en/stable/library_reference/aml/index.html#pyomo.environ.Objective.construct) class, as follows:


```python
# Objective Function: Maximize Profit
model.obj = Objective(expr = sum(C[i]*model.x[i] for i in I),
                      sense = maximize)
```

Again, the `obj` name is arbitrary, and you can select the one you prefer. The parameter `epxr` is mandatory, and is used to define the objective function expression. In the following example, we are using the `list comprehension` syntax to define our linear objective $\sum_{i \in I} c_i x_i$. Note that the python notation is very similar to the mathematical notation.

The parameter `sense` is optional, and it is used to define the type of objective function: `maximize` or `minimize`.

With Pyomo, we are not directly restricted to use only linear objective functions. It is the type solver we use that limits that type of problem that we can solve. As long as we use the GLPK solver, we can only define linear objective function.

### 3.3.3 Constraints
Finally, we need to define the budget constraint.
The constraints are defined using the [Constraint](https://pyomo.readthedocs.io/en/stable/library_reference/aml/index.html#pyomo.environ.Constraint) class. The minimal use of this class requires to define the `expr` input parameter. In the knapsack problem we have to define the budget constraint $\sum_{i \in I} A_i x_i \leq B$ as follows: 


```python
# Constraint
model.capacity = Constraint(expr = sum(A[i]*model.x[i] for i in I) <= B)
```

Also the constraints can be named, in this case, we named it `capacity`. The name of the constraint can be used to retrieve information about the status of the constraint in a solution, that is, given a solution $\bar x$ to check whether $\sum_{i \in I} A_i \bar x_i < B$ or $\sum_{i \in I} A_i \bar x_i = B$.

### 3.3.4 Solving the Pyomo model
The complete Pyomo model defined so far is as follows:


```python
# Create concrete model
model = ConcreteModel()
# Variables
model.x = Var(I, within=Binary)
# Objective Function: Maximize Profit
model.obj = Objective(expr = sum(C[i]*model.x[i] for i in I),
                      sense = maximize)
# Constraint
model.capacity = Constraint(expr = sum(A[i]*model.x[i] for i in I) <= B)
```

In order to solve this model, we need to use a **solver**, that is a software that binds the data to the model and solve the corresponding instance of the problem. In this notebook, we use the GLPK solver, using a `SolverFactory` as follows:


```python
# Solve the model
sol = SolverFactory('glpk').solve(model)
```


```python
# Basic info about the solution process
for info in sol['Solver']:
    print(info)
```

Finally, in order to check the values of the decision variables, we can query the solved model by using the variable, objective function, and constraints names:


```python
# Report solution value
print("Optimal solution value: z =", model.obj())
print("Decision variables:")
for i in I:
    print("x_{} = {}".format(i, model.x[i]()))
print("Capacity left in the knapsack:", B-model.capacity())
```

In this case, we have found a solution with value equal to 9, given by selecting the three items $[0, 1, 3]$. We still had a unit of capacity left in the knapsack, but since no left items as a weight equal to 1, and we cannot take fractional items, that capacity stay unused.

## 3.4 Complete Python Script
The whole Python script for solving the Knapsack problem is as follows:


```python
# Import the libraries
from pyomo.environ import ConcreteModel, Var, Objective, Constraint, SolverFactory
from pyomo.environ import maximize, Binary

# CONCRETE MODEL: Data First, then model
I = range(5)        # Items
C = [2, 3, 1, 4, 3] # Profits
A = [3, 4, 2, 1, 6] # Weights
B = 9               # Budget

# Create concrete model
model = ConcreteModel()

# Variables
model.x = Var(I, within=Binary)

# Objective Function: Maximize Profit
model.obj = Objective(expr = sum(C[i]*model.x[i] for i in I),
                      sense = maximize)

# Constraint
model.capacity = Constraint(expr = sum(A[i]*model.x[i] for i in I) <= B)

# Solve the model
sol = SolverFactory('glpk').solve(model)

# Basic info about the solution process
for info in sol['Solver']:
    print(info)
    
# Report solution value
print("Optimal solution value: z =", model.obj())
print("Decision variables:")
for i in I:
    print("x_{} = {}".format(i, model.x[i]()))
print("Capacity left in the knapsack:", B-model.capacity())
```

81ea17c61e80d9e906e996a0937619c2bd95c94a
ipynb
Jupyter Notebook
KnapsackProblem.ipynb
badcortex/opt4ds-1
0950053a07962960e8ed9507bfa02f2cc3665b46
MIT
2020-03-04T18:02:47.000Z
2022-02-27T17:40:09.000Z
KnapsackProblem.ipynb
badcortex/opt4ds-1
0950053a07962960e8ed9507bfa02f2cc3665b46
MIT
2021-03-23T11:47:24.000Z
2021-03-28T12:23:21.000Z
KnapsackProblem.ipynb
badcortex/opt4ds-1
0950053a07962960e8ed9507bfa02f2cc3665b46
MIT
2020-03-12T23:41:21.000Z
2022-03-03T13:41:29.000Z
Qwen/Qwen-72B
1. YES
2. YES