# Mixed Integer Linear Programming (MILP)

## Introduction

* Some variables are restricted to be integers
* NP-complete
* Applications
    * Production planning
    * Scheduling
    * Many more...

## 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.


## CPLEX 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 docplex
## Step 1: Importing Model from docplex package


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

## Step 2: Create an optimization model


```python
milp_model = Model(name = "MILP")
```

## Step 3: Add decision variables


```python
x = milp_model.binary_var(name = 'x')
y = milp_model.continuous_var(name = 'y', lb = 0)
z = milp_model.integer_var(name="z", lb=0)
```

## Step 4: Add the constraints


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

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

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

## Step 5: Define the objective function


```python
obj_fn = 2 * x + y + 3 * z
milp_model.set_objective('max', obj_fn)

milp_model.print_information()
```

## Step 6: Solve the model


```python
milp_model.solve()
```

## Step 7: Output the result


```python
milp_model.print_solution()
```


```python

```

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