Facility Location

Example: Facility Location

Description

Imagine you are a logistics manager responsible for opening new warehouses to serve a set of customer locations. Each warehouse has a fixed cost associated with opening it, and each customer location has a demand that must be met. Your goal is to determine which warehouses to open and how much demand each warehouse should serve in order to minimize the total cost while satisfying all customer demands.

Variables

The problem involves two types of decision variables:

Warehouse Opening Variables:
- These variables, denoted as warehouse_open[i], represent whether each warehouse i is open (1) or closed (0).
- There is one variable for each warehouse.
Customer Allocation Variables:
- These variables, denoted as customer_allocation[i][j], indicate whether customer i is allocated to warehouse j (1) or not (0).
- There is a 2D array of these variables, where each row corresponds to a customer and each column corresponds to a warehouse.

Constraints

The problem enforces the following constraints:

A constraint that ensures for each customer i, the sum of allocations to all warehouses j is equal to 1, meaning that the customer is allocated to exactly one warehouse.
A constraint that ensures if a warehouse j is not open (i.e., warehouse_open[j] is 0), then the allocation of customer demand i to that warehouse (customer_allocation[i][j]) must be 0 as well.
A constraint that ensures the total demand of each customer i is met. It sums the demand allocated to each warehouse j and ensures that it is greater than or equal to the total demand of that customer.

Objectives

The objective of the problem is to minimize the total costs associated with warehouse openings and customer allocations. The total costs are computed as follows:

Warehouse Opening Costs:
- For each warehouse j, the opening cost warehouse_costs[j] is multiplied by the corresponding warehouse opening variable warehouse_open[j].
Transportation Costs:
- For each customer “i” and warehouse “j”, the transportation cost transportation_costs[i][j] is multiplied by the allocation variable customer_allocation[i][j] to represent the transportation cost of serving customer i from warehouse j.

The overall objective is to minimize the sum of the above costs across all warehouses and customers.

Code

import qaekwy as qw

def solve_facility_location(
    num_customers: int,
    num_warehouses: int,
    customer_demands: list[int],
    warehouse_costs: list[int],
    transportation_costs: list[list[int]]
):
    # Instantiate the model
    m = qw.Model()

    # Variables: whether a warehouse is open (binary: 0 or 1)
    warehouse_open = [
        m.integer_variable(name=f"warehouse_{j}", domain=(0, 1))
        for j in range(num_warehouses)
    ]

    # Variables: allocation of customer i to warehouse j (binary: 0 or 1)
    customer_allocation = [
        [
            m.integer_variable(name=f"cw{i}{j}", domain=(0, 1))
            for j in range(num_warehouses)
        ]
        for i in range(num_customers)
    ]

    # Constraint: Each customer must be allocated to exactly one warehouse
    for i in range(num_customers):
        m.constraint(
            sum(customer_allocation[i][j] for j in range(num_warehouses)) == 1
        )

    # Constraint: A warehouse must be open to serve a customer
    # (Customer demand is met only if the warehouse is open)
    for i in range(num_customers):
        for j in range(num_warehouses):
            m.constraint(
                customer_allocation[i][j] * customer_demands[i] 
                <= warehouse_open[j] * customer_demands[i]
            )

    # Constraint: Ensure each customer demand is fully met
    for i in range(num_customers):
        m.constraint(
            sum(
                customer_allocation[i][j] * customer_demands[i]
                for j in range(num_warehouses)
            ) >= customer_demands[i]
        )

    # Objective: Minimize fixed costs (opening) + variable costs (transport)
    total_cost = m.integer_variable(
        name="total_cost",
        expression=sum(
            warehouse_costs[j] * warehouse_open[j]
            + sum(
                transportation_costs[i][j] * customer_allocation[i][j]
                for i in range(num_customers)
            )
            for j in range(num_warehouses)
        )
    )

    # Set the objective to minimize
    m.minimize(total_cost)

    # Solve using Branch-and-bound searcher
    return m.solve_one(searcher="bab")


if __name__ == "__main__":
    # Problem data
    customers_count = 3
    warehouses_count = 2
    demands = [10, 20, 15]
    fixed_costs = [100, 150]
    trans_costs = [[10, 15], [12, 18], [8, 10]]

    # Solve the problem
    solution = solve_facility_location(
        customers_count, warehouses_count, demands, fixed_costs, trans_costs
    )

    # Print results
    if solution:
        print(f"{'Variable':<15} | {'Value':<10}")
        print("-" * 28)
        for var_name, value in solution.items():
            print(f"{str(var_name):<15} | {value:<10}")
    else:
        print("No solution found.")

Result

The output will display which warehouses are opened and how customers are allocated to them, along with the total cost incurred.

Variable        | Value     
----------------------------
total_cost      | 130       
warehouse_0     | 1         
warehouse_1     | 0         
cw00            | 1         
cw01            | 0         
cw21            | 0         
cw10            | 1         
cw11            | 0         
cw20            | 1