Facility Location Example

Overview

This example demonstrates mixed-integer programming (MIP) in LumiX, combining binary decision variables (open/close facilities) with continuous flow variables (shipping quantities). It showcases how to model fixed costs, conditional constraints, and the classic Big-M formulation.

The facility location problem determines which warehouses to open and how to route shipments to minimize total cost while satisfying customer demands.

Problem Description

A logistics company needs to decide:

1. Which warehouses to open from candidate locations (binary decision)

2. How to serve customers from open warehouses (continuous flow)

Objective: Minimize total cost = fixed opening costs + variable shipping costs.

Constraints:

• Demand satisfaction: All customer demands must be met

• Capacity limits: Warehouses cannot exceed capacity

• Conditional shipping: Can only ship from open warehouses (Big-M)

• Binary opening decisions: Warehouse is either open or closed

Mathematical Formulation

Decision Variables:

\[\begin{split}\text{open}_w &\in \{0, 1\}, \quad \forall w \in \text{Warehouses} \\ \text{ship}_{w,c} &\geq 0, \quad \forall w \in \text{Warehouses}, c \in \text{Customers}\end{split}\]

Objective Function:

\[\text{Minimize} \quad \sum_{w \in \text{Warehouses}} \text{fixed\_cost}_w \cdot \text{open}_w + \sum_{w,c} \text{shipping\_cost}_{w,c} \cdot \text{ship}_{w,c}\]

Constraints:

1. Demand Satisfaction:

   \[\sum_{w \in \text{Warehouses}} \text{ship}_{w,c} \geq \text{demand}_c, \quad \forall c \in \text{Customers}\]

2. Capacity with Opening:

   \[\sum_{c \in \text{Customers}} \text{ship}_{w,c} \leq \text{capacity}_w \cdot \text{open}_w, \quad \forall w \in \text{Warehouses}\]

3. Big-M Constraint (can only ship if open):

   \[\text{ship}_{w,c} \leq M \cdot \text{open}_w, \quad \forall w \in \text{Warehouses}, c \in \text{Customers}\]

   where \(M\) is a sufficiently large constant.

Key Features

Binary Decision Variables

Open/close decisions using binary variables:

# Decision Variable 1: Binary - Open warehouse or not
open_warehouse = (
    LXVariable[Warehouse, int]("open_warehouse")
    .binary()
    .indexed_by(lambda w: w.id)
    .from_data(WAREHOUSES)

Key Points:

• LXVariable[Warehouse, int] with .binary() creates 0/1 variables

• One variable per warehouse to decide opening

• Fixed costs apply only when open_warehouse = 1

Continuous Flow Variables

Multi-indexed shipping quantities:

# Multi-indexed by (Warehouse, Customer) using cartesian product
ship = (
    LXVariable[Tuple[Warehouse, Customer], float]("ship")
    .continuous()
    .indexed_by_product(
        LXIndexDimension(Warehouse, lambda w: w.id).from_data(WAREHOUSES),
        LXIndexDimension(Customer, lambda c: c.id).from_data(CUSTOMERS),
    )
    .bounds(lower=0, upper=max(c.demand for c in CUSTOMERS))  # Upper bound needed for CP-SAT

The flow variables are indexed by (Warehouse, Customer) pairs using cartesian product.

Fixed Costs in Objective

One-time costs paid if a facility is opened:

# Objective: Minimize total cost (fixed + shipping)
cost_expr = (
    LXLinearExpression()
    .add_term(open_warehouse, coeff=lambda w: w.fixed_cost)  # Fixed costs
    .add_multi_term(ship, coeff=lambda w, c: shipping_cost(w, c))  # Shipping costs

The objective combines fixed costs (binary variables) and variable costs (continuous variables).

Big-M Constraints

Enforce “can only ship if open” using Big-M formulation:

# ship[w, c] <= M * open[w]
for warehouse in WAREHOUSES:
    for customer in CUSTOMERS:
        bigm_expr = (
            LXLinearExpression()
            .add_multi_term(
                ship,
                coeff=lambda w, c: 1.0,
                where=lambda w, c, wh=warehouse, cu=customer: w.id == wh.id and c.id == cu.id,
            )
            .add_term(
                open_warehouse,
                coeff=lambda w, wh=warehouse: -BIG_M if w.id == wh.id else 0,
            )
        )
        model.add_constraint(
            LXConstraint(f"bigm_{warehouse.name}_{customer.name}")
            .expression(bigm_expr)
            .le()
            .rhs(0)

Big-M Logic:

• If open[w] = 0: ship[w,c] <= M × 0 = 0 (cannot ship)

• If open[w] = 1: ship[w,c] <= M × 1 = M (can ship up to M)

Choosing M: Must be large enough not to constrain feasible solutions. Here, M = total_demand is safe.

Capacity with Binary Variables

Conditional capacity constraints:

for warehouse in WAREHOUSES:
    capacity_expr = (
        LXLinearExpression()
        .add_multi_term(
            ship,
            coeff=lambda w, c: 1.0,
            where=lambda w, c, wh=warehouse: w.id == wh.id,
        )
        .add_term(
            open_warehouse,
            coeff=lambda w, wh=warehouse: -wh.capacity if w.id == wh.id else 0,
        )
    )
    model.add_constraint(
        LXConstraint(f"capacity_{warehouse.name}").expression(capacity_expr).le().rhs(0)

This ensures: \(\sum_c \text{ship}_{w,c} \leq \text{capacity}_w \cdot \text{open}_w\).

Running the Example

Prerequisites:

pip install lumix[ortools]  # or cplex, gurobi (recommended for MIP)

Note: This problem uses haversine-based shipping costs (irrational numbers), which can be problematic for CP-SAT. Use OR-Tools LP, CPLEX, or Gurobi for best results.

Run:

cd examples/03_facility_location
python facility_location.py

Expected Output:

======================================================================
LumiX Example: Facility Location Problem
======================================================================

Potential Warehouses:
----------------------------------------------------------------------
  Chicago Distribution Center : Fixed cost $50,000, Capacity 1000 units
  Atlanta Hub                 : Fixed cost $45,000, Capacity 800 units
  Los Angeles Facility        : Fixed cost $60,000, Capacity 1200 units

Customers:
----------------------------------------------------------------------
  New York       : Demand 300 units
  Miami          : Demand 250 units
  Seattle        : Demand 200 units

Total Demand: 1100 units
Total Capacity: 3900 units

======================================================================
SOLUTION
======================================================================
Status: optimal
Total Cost: $147,234.56
  Fixed Costs: $90,000.00
  Shipping Costs: $57,234.56

Open Warehouses:
----------------------------------------------------------------------
  Chicago Distribution Center: Serving 2 customers (fixed cost: $50,000.00)
  Dallas Warehouse: Serving 2 customers (fixed cost: $40,000.00)

Shipping Plan:
----------------------------------------------------------------------
  Chicago Distribution Center → New York: 300.0 units ($4,500.00)
  Dallas Warehouse → Miami: 250.0 units ($6,250.00)

Complete Code Walkthrough

Step 1: Create Binary Opening Variables

# Decision Variable 1: Binary - Open warehouse or not
open_warehouse = (
    LXVariable[Warehouse, int]("open_warehouse")
    .binary()
    .indexed_by(lambda w: w.id)
    .from_data(WAREHOUSES)

Step 2: Create Continuous Shipping Variables

# Multi-indexed by (Warehouse, Customer) using cartesian product
ship = (
    LXVariable[Tuple[Warehouse, Customer], float]("ship")
    .continuous()
    .indexed_by_product(
        LXIndexDimension(Warehouse, lambda w: w.id).from_data(WAREHOUSES),
        LXIndexDimension(Customer, lambda c: c.id).from_data(CUSTOMERS),
    )
    .bounds(lower=0, upper=max(c.demand for c in CUSTOMERS))  # Upper bound needed for CP-SAT

Step 3: Set Objective (Fixed + Variable Costs)

# Objective: Minimize total cost (fixed + shipping)
cost_expr = (
    LXLinearExpression()
    .add_term(open_warehouse, coeff=lambda w: w.fixed_cost)  # Fixed costs
    .add_multi_term(ship, coeff=lambda w, c: shipping_cost(w, c))  # Shipping costs
)

Step 4: Add Demand Constraints

# Constraint 1: Satisfy customer demand
# For each customer: sum(ship[w, c] over all w) >= demand[c]
for customer in CUSTOMERS:
    demand_expr = LXLinearExpression().add_multi_term(
        ship,
        coeff=lambda w, c: 1.0,
        where=lambda w, c, cust=customer: c.id == cust.id,
    )
    model.add_constraint(
        LXConstraint(f"demand_{customer.name}")
        .expression(demand_expr)
        .ge()
        .rhs(customer.demand)

Step 5: Add Capacity Constraints

# Constraint 2: Warehouse capacity
# For each warehouse: sum(ship[w, c] over all c) <= capacity[w] * open[w]
# This is a conditional constraint: can't ship if not open
for warehouse in WAREHOUSES:
    capacity_expr = (
        LXLinearExpression()
        .add_multi_term(
            ship,
            coeff=lambda w, c: 1.0,
            where=lambda w, c, wh=warehouse: w.id == wh.id,
        )
        .add_term(
            open_warehouse,
            coeff=lambda w, wh=warehouse: -wh.capacity if w.id == wh.id else 0,
        )
    )
    model.add_constraint(
        LXConstraint(f"capacity_{warehouse.name}").expression(capacity_expr).le().rhs(0)

Step 6: Add Big-M Constraints

# ship[w, c] <= M * open[w]
for warehouse in WAREHOUSES:
    for customer in CUSTOMERS:
        bigm_expr = (
            LXLinearExpression()
            .add_multi_term(
                ship,
                coeff=lambda w, c: 1.0,
                where=lambda w, c, wh=warehouse, cu=customer: w.id == wh.id and c.id == cu.id,
            )
            .add_term(
                open_warehouse,
                coeff=lambda w, wh=warehouse: -BIG_M if w.id == wh.id else 0,
            )
        )
        model.add_constraint(
            LXConstraint(f"bigm_{warehouse.name}_{customer.name}")
            .expression(bigm_expr)
            .le()
            .rhs(0)

Step 7: Solve and Access Solution

optimizer = LXOptimizer().use_solver("ortools")
solution = optimizer.solve(model)

if solution.is_optimal():
    # Access binary variables
    for warehouse in WAREHOUSES:
        is_open = solution.variables["open_warehouse"][warehouse.id]
        if is_open > 0.5:  # Binary variable
            print(f"Open: {warehouse.name}")

    # Access flow variables
    for warehouse in WAREHOUSES:
        for customer in CUSTOMERS:
            qty = solution.variables["ship"].get((warehouse.id, customer.id), 0)
            if qty > 0.01:
                print(f"Ship {qty:.1f} from {warehouse.name} to {customer.name}")

Learning Objectives

After completing this example, you should understand:

1. Mixed-Integer Programming: Combining binary and continuous variables

2. Fixed Costs: Modeling one-time costs with binary decisions

3. Big-M Formulation: Linking binary and continuous variables conditionally

4. Conditional Constraints: Enforcing “IF-THEN” logic linearly

5. Multi-Model Flow: Indexing flow variables by pairs of models

6. MIP Solution: Interpreting binary and continuous solution values

Common Patterns

Pattern 1: Binary Decision with Fixed Cost

# Binary variable for open/close decision
open_var = (
    LXVariable[Entity, int]("open")
    .binary()
    .indexed_by(lambda e: e.id)
    .from_data(ENTITIES)
)

# Add fixed cost to objective
cost_expr = LXLinearExpression().add_term(
    open_var,
    coeff=lambda e: e.fixed_cost
)
model.minimize(cost_expr)

Pattern 2: Big-M Constraint

# ship[w,c] <= M × open[w]
# Rewritten as: ship[w,c] - M × open[w] <= 0

for warehouse in WAREHOUSES:
    for customer in CUSTOMERS:
        bigm_expr = (
            LXLinearExpression()
            .add_multi_term(
                ship,
                coeff=lambda w, c: 1.0,
                where=lambda w, c: w.id == warehouse.id and c.id == customer.id
            )
            .add_term(
                open_var,
                coeff=lambda w: -BIG_M if w.id == warehouse.id else 0
            )
        )
        model.add_constraint(
            LXConstraint(f"bigm_{warehouse.id}_{customer.id}")
            .expression(bigm_expr)
            .le()
            .rhs(0)
        )

Pattern 3: Conditional Capacity

# flow <= capacity × open
# Rewritten as: flow - capacity × open <= 0

capacity_expr = (
    LXLinearExpression()
    .add_multi_term(flow, coeff=lambda src, dst: 1.0, where=...)
    .add_term(open_var, coeff=lambda src: -capacity[src])
)
model.add_constraint(
    LXConstraint("capacity").expression(capacity_expr).le().rhs(0)
)

Pattern 4: Demand Satisfaction

# For each customer: sum over sources >= demand
for customer in CUSTOMERS:
    demand_expr = LXLinearExpression().add_multi_term(
        flow,
        coeff=lambda src, dst: 1.0,
        where=lambda src, dst: dst.id == customer.id
    )
    model.add_constraint(
        LXConstraint(f"demand_{customer.id}")
        .expression(demand_expr)
        .ge()
        .rhs(customer.demand)
    )

Extending the Example

Try These Modifications

1. Multi-Product: Add product dimension to flow variables

   ship = LXVariable[Tuple[Warehouse, Customer, Product], float]("ship")
   

2. Multi-Period: Dynamic facility opening/closing over time

3. Capacitated Levels: Different capacity options (small, medium, large)

4. Service Level: Add maximum distance or service time constraints

5. Hub Location: Warehouses can ship to other warehouses

6. Modular Capacity: Add multiple capacity modules at each location

Improving the Formulation

Better Big-M Values

Instead of global Big-M, use specific bounds per (warehouse, customer):

# Tighter bound for each pair
M_wc = min(warehouse.capacity, customer.demand)
# Better LP relaxation → faster solve times

Alternative Formulations

Consider these improvements:

1. Aggregated Big-M: Fewer constraints by combining

2. Strengthening Cuts: Add valid inequalities

3. Variable Bounds: Tighten upper bounds on flow variables

4. Preprocessing: Eliminate dominated facilities

Next Steps

After mastering this example:

1. Example 02 (Driver Scheduling): Multi-model indexing foundation

2. Example 05 (CP-SAT Assignment): Pure integer programming with CP-SAT

3. Example 11 (Goal Programming): Soft constraints for location problems

4. User Guide - MIP: Deep dive into mixed-integer programming

See Also

Related Examples:

• Driver Scheduling Example - Multi-model indexing with binary variables

• CP-SAT Assignment Example - CP-SAT solver for combinatorial problems

• Production Planning Example - Single-model indexing basics

API Reference:

• lumix.core.variables.LXVariable

• lumix.indexing.LXIndexDimension

• lumix.core.model.LXModel

• lumix.core.constraints.LXConstraint

User Guide:

• Variables Guide - Binary and integer variables for MIP

• Bilinear Product Linearization - Big-M method and bilinear linearization

• Variables Guide - Using binary variables for fixed costs

Use Cases

This pattern applies to:

• Distribution Network Design: Minimize logistics costs

• Server Placement: Cloud computing infrastructure

• Retail Site Selection: Store location optimization

• Emergency Services: Hospital/fire station placement

• Manufacturing: Plant location and production allocation

• Supply Chain: Hub-and-spoke network design

Files in This Example

• facility_location.py - Main optimization model and solution display

• sample_data.py - Data models (Warehouse, Customer) and cost calculations

• README.md - Detailed documentation and usage guide