Mixed-Integer Programming (MIP) Example Using CVXPY

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:

  • (xij): Binary decision variable, 1 if customer (j) is served by facility (i), 0 otherwise.
  • (yi): Binary decision variable, 1 if facility (i) is open, 0 otherwise.

• Parameters:

  • (fi): Fixed cost of opening facility (i).
  • (cij): Transportation cost for serving customer (j) from facility (i).

• Objective:
  Minimize the total cost:
  Minimize∑ifiyi+∑i∑jcijxij

• Constraints:

  1. Each customer must be assigned to exactly one facility:
     ∑ixij=1,∀j
  2. A customer can only be served by an open facility:
     xij≤yi,∀i,j
  3. Binary constraints on the variables:
     xij∈0,1,yi∈0,1,∀i,j

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.

import cvxpy as cp
import numpy as np

# Data (example)
num_facilities = 3  # Number of facilities
num_customers = 5   # Number of customers

# Fixed costs for opening each facility
f = np.array([100, 200, 300])

# Transportation costs from each facility to each customer
c = np.array([
    [8, 10, 7, 6, 9],
    [6, 8, 5, 7, 10],
    [10, 7, 6, 8, 7]
])

# Decision variables
# x_ij: binary, 1 if customer j is served by facility i
x = cp.Variable((num_facilities, num_customers), boolean=True)

# y_i: binary, 1 if facility i is open
y = cp.Variable(num_facilities, boolean=True)

# Objective: Minimize fixed and transportation costs
# Updated to use elementwise multiplication (cp.multiply)
objective = cp.Minimize(cp.sum(f @ y) + cp.sum(cp.multiply(c, x)))

# Constraints
constraints = []

# Each customer must be assigned to exactly one facility
for j in range(num_customers):
    constraints.append(cp.sum(x[:, j]) == 1)

# Customers can only be assigned to open facilities
for i in range(num_facilities):
    for j in range(num_customers):
        constraints.append(x[i, j] <= y[i])

# Solve the problem using another solver such as GLPK_MI
problem = cp.Problem(objective, constraints)
problem.solve(solver=cp.GLPK_MI)

# Results
print("Status:", problem.status)
print("Total Cost:", problem.value)
print("Facilities to Open:", y.value)
print("Customer Assignments:")
print(x.value)

Explanation:

1. Decision Variables:

   • x: This is a ( num_facilities × 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.

2. Objective:

   • The objective is to minimize the sum of the fixed costs (fi) for opening facilities and the transportation costs (cij) for serving customers.

3. 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].

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

Output:

Status: optimal
Total Cost: 140.0
Facilities to Open: [1. 0. 0.]
Customer Assignments:
[[1. 1. 1. 1. 1.]
 [0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0.]]

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