# Mixed Integer Linear Programming (MILP)

## Introduction

* Some variables are restricted to be integers
* NP-complete
* Applications
    * Production planning
    * Scheduling
    * Many more...
* Exact Algorithms
    * Cutting plane methods
    * Variants of branch and bound
* Heuristic Methods
    * LP relaxation
    * Tabu search

## The standard form

\begin{align}
\text{maximize}\  & \mathbf{c}^T\mathbf{x} + \mathbf{k}^T\mathbf{y} \\
\text{subject to } & \\
& A\mathbf{x} &&\leq \mathbf{b} \\
& D\mathbf{y} &&\leq \mathbf{e} \\
& \mathbf{x},\mathbf{y} &&\geq 0 \\
& \mathbf{x} \in \mathbb{Z}^n
\end{align}
where $A, D \in \mathbb{R}^{m\times n}$ are matrices, $\mathbf{b}, \mathbf{e}\in\mathbb{R}^{m}$ are constants, $\mathbf{c}, \mathbf{k} \in \mathbb{R}^{n}$ objective function coefficients, and $\mathbf{x}, \mathbf{y} \in\mathbb{R}^{n}$ are the decision variables.


## Gurobi basics: Mixed Integer Programming Model
## Mathematical Model
\begin{align}
\text{maximize}\  & 2x + y + 3z \\
\text{subject to } & \\
& x+2y+z &&\leq 4 \\
& 2z + y &&\leq 5 \\
& x + y &&\geq 1 \\
& x &&\in \{0,1\} \\
& y, z \geq 0 \\
& z \in \mathbb{Z}
\end{align}

# Code in Python using gurobipy
## Step 1: Importing gurobipy package


```python
from gurobipy import *
```

## Step 2: Create an optimization model


```python
milp_model = Model("milp")
```

## Step 3: Add decision variables


```python
x = milp_model.addVar(vtype=GRB.BINARY, name="x")
y = milp_model.addVar(vtype=GRB.CONTINUOUS, lb=0, name="y")
z = milp_model.addVar(vtype=GRB.INTEGER, lb=0, name="z")
```

## Step 4: Define the objective function


```python
obj_fn = 2 * x + y + 3 * z
milp_model.setObjective(obj_fn, GRB.MAXIMIZE)
```

## Step 5: Add the constraints


```python
# Add constraint: x + 2 y + z <= 4
c1 = milp_model.addConstr(x + 2 * y + z <= 4, "c1")

# Add constraint: 2 z + y <= 5 \\
c2 = milp_model.addConstr(2 * z + y <= 5, "c2")

# Add constraint x + y >= 1
c3 = milp_model.addConstr(x + y >= 1, "c3")
```

## Step 6: Solve the model


```python
milp_model.optimize()
```

## Step 7: Output the result


```python
print('Objective Function Value: %.2f' % milp_model.objVal)
# Get values of the decision variables
for v in milp_model.getVars():
    print('%s: %g' % (v.varName, v.x))
```

2e28481db2b81dd43dbaa3a8c9a12b11fe051bf4
ipynb
Jupyter Notebook
mathematicalProgramming/Video03/Video03.ipynb
codingperspective/videoMaterials
8c9665466d8912c6f0c701c25ad9eb4802fb73a3
CC0-1.0
mathematicalProgramming/Video03/Video03.ipynb
codingperspective/videoMaterials
8c9665466d8912c6f0c701c25ad9eb4802fb73a3
CC0-1.0
mathematicalProgramming/Video03/Video03.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