Facility Location Problem

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

from qaekwy.engine import DirectEngine
from qaekwy.model.constraint.relational import RelationalExpression
from qaekwy.model.variable.integer import IntegerExpressionVariable, IntegerVariable
from qaekwy.model.modeller import Modeller
from qaekwy.model.specific import SpecificMinimum
from qaekwy.model.searcher import SearcherType


class FacilityLocationProblem(Modeller):
    def __init__(
        self,
        num_customers,
        num_warehouses,
        customer_demands,
        warehouse_costs,
        transportation_costs,
    ):
        super().__init__()

        # Create variables to represent warehouse openings and customer allocations
        warehouse_open = [
            IntegerVariable(var_name=f"warehouse_{i}", domain_low=0, domain_high=1)
            for i in range(num_warehouses)
        ]

        customer_allocation = [
            [
                IntegerVariable(
                    var_name=f"cw{i}{j}", domain_low=0, domain_high=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):
            self.add_constraint(
                RelationalExpression(
                    sum(customer_allocation[i][j] for j in range(num_warehouses)) == 1
                )
            )

        # Constraint: Ensure each customer demand is met only if the corresponding warehouse is open
        for i in range(num_customers):
            for j in range(num_warehouses):
                self.add_constraint(
                    RelationalExpression(
                        customer_allocation[i][j] * customer_demands[i] <= warehouse_open[j] * customer_demands[i]
                    )
                )

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

        # Objective: Minimize total costs while meeting customer demands
        total_costs = IntegerExpressionVariable(
            var_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)
            )
        )


        # Add variables problem
        for warehouse_var in warehouse_open:
            self.add_variable(warehouse_var)
        for customer_vars in customer_allocation:
            for customer_var in customer_vars:
                self.add_variable(customer_var)

        self.add_variable(total_costs)


        # Adding the objective
        self.add_objective(SpecificMinimum(total_costs))

        # Set the search strategy to Depth-First Search (DFS)
        self.set_searcher(SearcherType.BAB)



if __name__ == "__main__":
    # Create a Qaekwy engine for direct interaction
    qaekwy_engine = DirectEngine()

    # Define problem parameters: number of customers, warehouses, demands, costs, and transportation costs
    num_customers = 3
    num_warehouses = 2
    customer_demands = [10, 20, 15]
    warehouse_costs = [100, 150]
    transportation_costs = [[10, 15], [12, 18], [8, 10]]

    # Create the facility location problem instance
    facility_location_problem = FacilityLocationProblem(
        num_customers,
        num_warehouses,
        customer_demands,
        warehouse_costs,
        transportation_costs,
    )

    # Request the Qaekwy engine to solve the facility location problem
    response = qaekwy_engine.model(model=facility_location_problem)

    # Retrieve the list of solutions from the response
    list_of_solutions = response.get_solutions()

    solution = list_of_solutions[0]
    for solution_item, solution_value in solution.items():
        print(f"| {solution_item}\t| {solution_value}\t|")