Impara Mixed-Integer Linear Programming (MILP) Applications | Integer Programming & Discrete Decision Models

Consider a company that needs to decide where to open new distribution centers and how much inventory to allocate to each. The decision of whether to open a facility is a yes-or-no (integer) choice, while the amount of inventory shipped is a continuous variable. For example, you may want to minimize total costs by choosing which of several candidate locations to open (integer variables) and how much product to send from each open facility to meet customer demand (continuous variables). This blend of discrete and continuous choices is at the heart of many analytics problems in supply chain, finance, and operations.


              1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
            
# Facility location using MILP with pulp
import pulp

# Sets of facilities and customers
facilities = ['A', 'B', 'C']
customers = ['X', 'Y']

# Fixed costs for opening each facility
fixed_cost = {'A': 1000, 'B': 1200, 'C': 1100}
# Shipping costs from facilities to customers
shipping_cost = {('A', 'X'): 4, ('A', 'Y'): 6,
                 ('B', 'X'): 5, ('B', 'Y'): 4,
                 ('C', 'X'): 7, ('C', 'Y'): 3}

# Demand for each customer
demand = {'X': 80, 'Y': 70}
# Capacity of each facility
capacity = {'A': 100, 'B': 90, 'C': 100}

# Create the MILP problem
prob = pulp.LpProblem("FacilityLocation", pulp.LpMinimize)

# Decision: y_f = 1 if facility f is open, else 0 (integer)
y = pulp.LpVariable.dicts("OpenFacility", facilities, 0, 1, pulp.LpBinary)
# Decision: x_f_c = amount shipped from facility f to customer c (continuous)
x = pulp.LpVariable.dicts("Ship", [(f, c) for f in facilities for c in customers], 0)

# Objective: Minimize total fixed + shipping costs
prob += (
    pulp.lpSum([fixed_cost[f] * y[f] for f in facilities]) +
    pulp.lpSum([shipping_cost[(f, c)] * x[(f, c)] for f in facilities for c in customers])
)

# Each customer's demand must be met
for c in customers:
    prob += pulp.lpSum([x[(f, c)] for f in facilities]) >= demand[c], f"Demand_{c}"

# Shipments from a facility cannot exceed its capacity if it is open
for f in facilities:
    prob += pulp.lpSum([x[(f, c)] for c in customers]) <= capacity[f] * y[f], f"Capacity_{f}"

# Solve the model
prob.solve()

# Output analytics decisions
for f in facilities:
    print(f"Open facility {f}: {int(pulp.value(y[f]))}")
    for c in customers:
        shipped = pulp.value(x[(f, c)])
        if shipped > 0:
            print(f"  Ship {shipped} units from {f} to {c}")
# In this model:
# - y[f] (binary) decides if facility f is open (integer decision).
# - x[(f, c)] (continuous) decides how much to ship from f to c (continuous decision).
# - Constraints ensure demand is met and facility capacities are respected only if open.
# - The objective balances fixed opening costs and variable shipping costs.

When you require integer variables in an analytics model, you introduce combinatorial complexity. This means the solver must search over both continuous and discrete choices, which can significantly increase the time and computational resources needed to find an optimal solution. However, including integrality often produces solutions that are more realistic and actionable—such as deciding exactly which facilities to open, or how many machines to purchase—rather than allowing fractional, impractical answers. As a result, there is a trade-off: enforcing integrality improves solution quality for real-world decisions, but may make the problem harder to solve compared to standard linear programs that use only continuous variables.

1. Which statement best describes the role of integer variables in a mixed-integer linear programming (MILP) model?

2. How does a mixed-integer linear programming (MILP) model differ from a standard linear programming (LP) model in analytics applications?

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 2. Capitolo 2

Chieda ad AI

Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione

Scorri per mostrare il menu


              1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
            
# Facility location using MILP with pulp
import pulp

# Sets of facilities and customers
facilities = ['A', 'B', 'C']
customers = ['X', 'Y']

# Fixed costs for opening each facility
fixed_cost = {'A': 1000, 'B': 1200, 'C': 1100}
# Shipping costs from facilities to customers
shipping_cost = {('A', 'X'): 4, ('A', 'Y'): 6,
                 ('B', 'X'): 5, ('B', 'Y'): 4,
                 ('C', 'X'): 7, ('C', 'Y'): 3}

# Demand for each customer
demand = {'X': 80, 'Y': 70}
# Capacity of each facility
capacity = {'A': 100, 'B': 90, 'C': 100}

# Create the MILP problem
prob = pulp.LpProblem("FacilityLocation", pulp.LpMinimize)

# Decision: y_f = 1 if facility f is open, else 0 (integer)
y = pulp.LpVariable.dicts("OpenFacility", facilities, 0, 1, pulp.LpBinary)
# Decision: x_f_c = amount shipped from facility f to customer c (continuous)
x = pulp.LpVariable.dicts("Ship", [(f, c) for f in facilities for c in customers], 0)

# Objective: Minimize total fixed + shipping costs
prob += (
    pulp.lpSum([fixed_cost[f] * y[f] for f in facilities]) +
    pulp.lpSum([shipping_cost[(f, c)] * x[(f, c)] for f in facilities for c in customers])
)

# Each customer's demand must be met
for c in customers:
    prob += pulp.lpSum([x[(f, c)] for f in facilities]) >= demand[c], f"Demand_{c}"

# Shipments from a facility cannot exceed its capacity if it is open
for f in facilities:
    prob += pulp.lpSum([x[(f, c)] for c in customers]) <= capacity[f] * y[f], f"Capacity_{f}"

# Solve the model
prob.solve()

# Output analytics decisions
for f in facilities:
    print(f"Open facility {f}: {int(pulp.value(y[f]))}")
    for c in customers:
        shipped = pulp.value(x[(f, c)])
        if shipped > 0:
            print(f"  Ship {shipped} units from {f} to {c}")
# In this model:
# - y[f] (binary) decides if facility f is open (integer decision).
# - x[(f, c)] (continuous) decides how much to ship from f to c (continuous decision).
# - Constraints ensure demand is met and facility capacities are respected only if open.
# - The objective balances fixed opening costs and variable shipping costs.

1. Which statement best describes the role of integer variables in a mixed-integer linear programming (MILP) model?

2. How does a mixed-integer linear programming (MILP) model differ from a standard linear programming (LP) model in analytics applications?

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 2. Capitolo 2