26  Repair-Capacity Investment with Precedence

NoteSource and adaptation

Based on Car rental 2, Section 12.26 of Williams (2013). Extends the adapted cyclic rental model in Chapter 25 with three indivisible repair-capacity options. The results below solve the stated instance and are not presented as the numerical answer to an unmodified textbook problem.

26.1 Problem Statement

Use all fleet, demand, return, cost, and timing data from Chapter 25. Option 1 adds one repair/car per day at depot A for 12 USD per cycle. Option 2 adds a further one repair/car per day at A for 8 USD per cycle, but requires option 1. Option 3 adds one repair/car per day at B for 10 USD per cycle. At most two options can be selected. Costs are cycle-equivalent investment charges. Re-optimize the rental and repair plan with investment choices to maximize net cycle profit.

26.2 Model Formulation

Add binary investments \(z_1,z_2,z_3\), with \(z_2\le z_1\) and \(z_1+z_2+z_3\le2\). Replace repair-capacity bounds by

\[v_{At}\le2+z_1+z_2,\quad v_{Bt}\le1+z_3,\quad v_{Ct}\le1.\]

Subtract \(12z_1+8z_2+10z_3\) from the Chapter 25 objective. All fleet balances stay active. The second-stage expansion is available only after the first expansion at A is selected; there is no fractional purchase of an option.

All decision variables and units refer to the problem statement above. Continuous variables are nonnegative unless explicitly stated otherwise; binary and integer domains are specified in the equations and code.

26.3 Pyomo Implementation

The following Python implementation uses Pyomo and HiGHS. Run from the workbook root so that the models package and shared helpers are importable. The shared solver and audit functions check optimal termination before loading values, then verify every active constraint, variable bound, and integer domain. Any imported earlier-chapter model supplies the data and balances already explained there.

The full source is problem26.py. To solve and print this problem independently:

~/.venvs/optim/bin/python -m models.common 26
import pyomo.environ as pyo
from models import problem25 as base
from models.common import frame, solve


def build():
    m = base.build()
    m.repaircap.deactivate()
    m.obj.deactivate()
    m.z = pyo.Var(range(3), domain=pyo.Binary)
    m.precedence = pyo.Constraint(expr=m.z[1] <= m.z[0])
    m.limit = pyo.Constraint(expr=sum(m.z[k] for k in range(3)) <= 2)
    m.newcap = pyo.Constraint(
        m.I,
        m.T,
        rule=lambda m, i, t: (
            m.v[i, t]
            <= base.CAP[i] + (m.z[0] + m.z[1] if i == 0 else m.z[2] if i == 1 else 0)
        ),
    )
    m.profit = pyo.Objective(
        expr=m.obj.expr - 12 * m.z[0] - 8 * m.z[1] - 10 * m.z[2], sense=pyo.maximize
    )
    return m


def check(m):
    base.check(m)
    reference = solve(base.build())
    assert pyo.value(m.profit) >= pyo.value(reference.obj) - 1e-6


def tables(m):
    answer = base.tables(m)
    reference = solve(base.build())
    answer["investment"] = frame(
        [[k + 1, pyo.value(m.z[k]), [12, 8, 10][k]] for k in range(3)],
        ["Option", "Selected", "Cycle charge (USD)"],
    )
    answer["comparison"] = frame(
        [
            ["No expansion", pyo.value(reference.obj)],
            ["Optimal expansion", pyo.value(m.profit)],
        ],
        ["Policy", "Net profit (USD/cycle)"],
    )
    return answer


def plot(m):
    a = solve(base.build())
    return (
        ["No expansion", "Optimal expansion"],
        [pyo.value(a.obj), pyo.value(m.profit)],
        "Net profit (USD/cycle)",
    )

# Solve, audit constraints, and run domain-specific checks.
from models.common import solve, audit
model = solve(build())
audit(model)
check(model)
for name, result_table in tables(model).items():
    print(name)
    print(result_table.to_string(index=False))

26.4 Optimal Solution

The solver reports optimal termination. The objective is 2,007.036177 USD per three-day cycle (maximize). The largest violation across active constraints, variable bounds, and integer domains is 1.07e-14 in the corresponding model units. The problem-specific checks also pass. These checks establish numerical consistency with the stated model, not the validity of its assumptions for a real facility.

26.4.1 Fleet plan

Day Depot Usable stock Damaged stock Rentals Repairs
1 A 15 1.1465 15 0
1 B 13.7505 2 12 2
1 C 10.5923 1.1385 6.7352 1
2 A 12.2162 2.5039 10 2
2 B 18 1.1547 18 1.1547
2 C 8.7532 1 8.7532 1
3 A 14.544 1.6514 12 1.6514
3 B 14.2503 1.4551 10 0.5082
3 C 10.6545 1.0727 10.6545 1

26.4.2 Transfers

Day From To Vehicles
3 B A 0.4857
1 C B 3.8571

26.4.3 Investment

Option Selected Cycle charge (USD)
1 0 12
2 0 8
3 1 10

26.4.4 Comparison

Policy Net profit (USD/cycle)
No expansion 1,885.6648
Optimal expansion 2,007.0362
Figure 26.1: Selected quantities from the verified optimal solution. Units are stated on the axis.

Tables round numerical values for reading; feasibility checks use the original solver values. Multiple optimal decisions may exist. Machine-readable result records the solver status and package versions. Figure-generation code is in figures/workbook.py.

26.5 Brief Discussion

Optimal expansion increases net cycle profit by 121.37 USD after paying the investment charges.

The value of a repair expansion depends on the return network, queues, and demand, not simply its added capacity. A low-price option can be unattractive when it expands the wrong depot. Experiment: compare investment values before and after increasing depot Cā€™s demand.