# Integer Programming

* All decision variables are integers

\begin{align}
\text{maximize}\  & \mathbf{c}^T\mathbf{x} \\
\text{subject to } & \\
& A\mathbf{x} &&\leq \mathbf{b} \\
& \mathbf{x} &&\geq 0 \\
& \mathbf{x} \in \mathbb{Z}^n
\end{align}

* Binary integer programming: Variables are restricted to be either 0 or 1

# Binary Knapsack Problem
* Combinatorial optimization problem
* Problem of packing the most valuable or useful items without overloading the luggage. 
    * A set of items ($N$ items), each with a weight($w$) and a value($v$)
    * Fixed capacity 
    * Maximize the total value possible



## Problem Formulation
\begin{align}
\text{maximize}\  & \sum_{i=0}^{N-1}v_{i}x_{i} \\
\text{subject to } & \\
& \sum_{i=0}^{N-1}w_{i}x_{i} & \leq C \\
& x_i \in \{0,1\} & \forall i=0,\dots,N-1
\end{align}

## Coding in Python

## Creating the data (weights and values)


```python
w = [4,2,5,4,5,1,3,5]
v = [10,5,18,12,15,1,2,8]
C = 15
N = len(w)
```

## Step 2: Importing gurobipy package


```python
from gurobipy import *
```

## Step 3: Create an optimization model


```python
knapsack_model = Model('knapsack')
```

## Step 4: Add multiple binary decision variables

Adds multiple decision variables and stores them in the model.
```python
addVars(*indices, 
        lb=0.0, 
        ub=float('inf'), 
        obj=0.0, 
        vtype=GRB.CONTINUOUS, 
        name="" 
```


```python
x = knapsack_model.addVars(N, vtype = GRB.BINARY, name="x")
```

## Step 5: Add the constraints

$$\sum_{i=1}^{N} w_{i}x_{i} \leq C$$


```python
# \sum_{i=1}^{N} w_{i}*x_{i} <= C
knapsack_model.addConstr(sum(w[i]*x[i] for i in range(N)) <= C)
```

## Step 6: Define the objective function

$$\sum_{i=1}^{N} v_{i}x_{i}$$


```python
# \sum_{i=1}^{N} v_{i}*x_{i}
obj_fn = sum(v[i]*x[i] for i in range(N))
knapsack_model.setObjective(obj_fn, GRB.MAXIMIZE)
```

## Step 7: Solve the model and output the solution


```python
knapsack_model.optimize()
print('Optimization is done. Objective Function Value: %.2f' % knapsack_model.objVal)
# Get values of the decision variables

for v in knapsack_model.getVars():
    print('%s: %g' % (v.varName, v.x))
```


```python

```

a0dc98e1b9804789fa22c187530f4111e8f53ec5
ipynb
Jupyter Notebook
mathematicalProgramming/Video04/Video04.ipynb
codingperspective/videoMaterials
8c9665466d8912c6f0c701c25ad9eb4802fb73a3
CC0-1.0
mathematicalProgramming/Video04/Video04.ipynb
codingperspective/videoMaterials
8c9665466d8912c6f0c701c25ad9eb4802fb73a3
CC0-1.0
mathematicalProgramming/Video04/Video04.ipynb
codingperspective/videoMaterials
8c9665466d8912c6f0c701c25ad9eb4802fb73a3
CC0-1.0
2021-11-21T05:02:50.000Z
2022-02-17T04:44:57.000Z
Qwen/Qwen-72B
1. YES
2. YES