# 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 docplex package


```python
from docplex.mp.model import Model
```

## Step 3: Create an optimization model


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

## Step 4: Add multiple binary decision variables

Adds a list of binary decision variables and stores them in the model.
```python
binary_var_list(keys,                 # sequence of objects / an integer
                lb=None,              # lower bound
                ub=None,              # upper bound
                name=<type 'str'>,    # name
                key_format=None)      # a format string or None for naming the variables
```


```python
x = knapsack_model.binary_var_list(N, 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.add_constraint(sum(w[i]*x[i] for i in range(N)) <= C)
```




    docplex.mp.LinearConstraint[](4x_0+2x_1+5x_2+4x_3+5x_4+x_5+3x_6+5x_7,LE,15)



## 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.set_objective('max',obj_fn)

knapsack_model.print_information()
```

    Model: knapsack
     - number of variables: 8
       - binary=8, integer=0, continuous=0
     - number of constraints: 1
       - linear=1
     - parameters: defaults
     - objective: maximize
     - problem type is: MILP


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


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

    Optimization is done. Objective Function Value: 46.00
    objective: 46
      x_2=1
      x_3=1
      x_4=1
      x_5=1



```python

```

8923b57caf33dd9a2f2e9eca4d5ab733f2589eb0
ipynb
Jupyter Notebook
mathematicalProgramming/Video09/09_video.ipynb
codingperspective/videoMaterials
8c9665466d8912c6f0c701c25ad9eb4802fb73a3
CC0-1.0
mathematicalProgramming/Video09/09_video.ipynb
codingperspective/videoMaterials
8c9665466d8912c6f0c701c25ad9eb4802fb73a3
CC0-1.0
mathematicalProgramming/Video09/09_video.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