## Mixed-Integer Programming (MIP) Example Using CVXPY

#### Problem: Facility Location Problem

The facility location problem is a classic optimization problem where a company must decide where to open facilities (warehouses) to serve customers.

The goal is to minimize the total cost, which includes fixed costs for opening facilities and transportation costs for serving customers.

#### Problem Setup:

**Variables:**- $( x_{ij} )$: Binary decision variable, $1$ if customer $( j )$ is served by facility $( i )$, $0$ otherwise.
- $( y_i )$: Binary decision variable, $1$ if facility $( i )$ is open, $0$ otherwise.

**Parameters:**- $( f_i )$: Fixed cost of opening facility $( i )$.
- $( c_{ij} )$: Transportation cost for serving customer $( j )$ from facility $( i )$.

**Objective:**

Minimize the total cost:

$$

\text{Minimize} \quad \sum_{i} f_i y_i + \sum_{i}\sum_{j} c_{ij} x_{ij}

$$**Constraints:**- Each customer must be assigned to exactly one facility:

$$

\sum_{i} x_{ij} = 1, \quad \forall j

$$ - A customer can only be served by an open facility:

$$

x_{ij} \leq y_i, \quad \forall i, j

$$ - Binary constraints on the variables:

$$

x_{ij} \in {0, 1}, \quad y_i \in {0, 1}, \quad \forall i, j

$$

- Each customer must be assigned to exactly one facility:

#### Solving with CVXPY:

We can solve this problem using $CVXPY$, a Python library for convex optimization, which also supports **Mixed-Integer Programming**.

Here’s a step-by-step guide with Python code.

1 | import cvxpy as cp |

### Explanation:

**Decision Variables**:`x`

: This is a (`num_facilities`

$\times$`num_customers`

) matrix where each entry represents whether a customer is served by a facility.

We use`boolean=True`

to enforce the binary constraint.`y`

: This is a vector of length`num_facilities`

that indicates whether a facility is open.

**Objective**:- The objective is to minimize the sum of the fixed costs $( f_i )$ for opening facilities and the transportation costs $( c_{ij} )$ for serving customers.

**Constraints**:- We enforce the constraint that each customer is assigned to exactly one facility using
`cp.sum(x[:, j]) == 1`

. - We ensure that customers are only assigned to open facilities with
`x[i, j] <= y[i]`

.

- We enforce the constraint that each customer is assigned to exactly one facility using
**Solving**:- We use the
**GLPK_MI solver**(`solver=cp.GLPK_MI`

), which is well-suited for**mixed-integer programming**problems. - After solving, we can inspect the status, total cost, which facilities to open, and the customer assignments.

- We use the

### Output:

1 | Status: optimal |

This indicates that:

- Facilities $1$ should be opened.
- Customers $1$, $2$, $3$, $4$, and $5$ are served by facility 1.

#### Conclusion:

This example demonstrates how to model and solve a **Mixed-Integer Programming (MIP)** problem using $CVXPY$.

The facility location problem is a common application of **MIP**, and it shows how we can optimize costs by using binary decision variables to represent discrete choices (e.g., opening facilities).