Source code for brushline.strategic.coordination

"""Lagrangian budget and crew-hour coordination across spatial clusters.

Cluster subproblems remove the annual budget and crew-hour constraints and add non-negative
shadow prices to their objectives. Subgradient updates raise or lower those prices. The maximum
priced-cluster minimum is a lower bound for the original clustered problem.
"""

from __future__ import annotations

import math
import time
from datetime import UTC, datetime
from typing import Literal

from pydantic import BaseModel, ConfigDict, Field, model_validator

from brushline.strategic.decomposition import _clusters
from brushline.strategic.stateful import (
    StatefulConfig,
    StatefulMethod,
    StatefulPeriod,
    StatefulPlan,
    StatefulSegment,
    build_stateful_plan,
)

COORDINATION_SCHEMA_VERSION: Literal["brushline.stateful-coordination.v1"] = (
    "brushline.stateful-coordination.v1"
)


[docs] class CoordinationError(ValueError): """Raised when coordination inputs or prices are invalid."""
[docs] class PriceIteration(BaseModel): """One Lagrangian price iteration.""" model_config = ConfigDict(extra="forbid", frozen=True) iteration: int = Field(ge=0) cost_price: float = Field(ge=0) hours_price: float = Field(ge=0) dual_bound: float spend: float = Field(ge=0) hours: float = Field(ge=0) cluster_seconds: float = Field(ge=0)
[docs] class CoordinationResult(BaseModel): """Lagrangian coordination evidence.""" model_config = ConfigDict(extra="forbid", frozen=True) schema_version: Literal["brushline.stateful-coordination.v1"] = COORDINATION_SCHEMA_VERSION instance_id: str cluster_count: int = Field(ge=1) max_segments_per_cluster: int = Field(ge=1) baseline_objective: float dual_bound: float absolute_gap: float relative_gap: float iterations: list[PriceIteration] = Field(min_length=1) best_iteration: int = Field(ge=0) best_cost_price: float = Field(ge=0) best_hours_price: float = Field(ge=0) created_utc: datetime @model_validator(mode="after") def _time(self) -> CoordinationResult: if self.created_utc.tzinfo is None: raise ValueError("created_utc must be timezone-aware") return self
def _priced_plan( *, instance_id: str, segments: list[StatefulSegment], methods: list[StatefulMethod], periods: list[StatefulPeriod], cost_price: float, hours_price: float, max_seconds: float, created_utc: datetime | None, ) -> StatefulPlan: # The priced subproblem removes the annual constraints; prices carry their shadow value. relaxed_periods = [ StatefulPeriod(year=period.year, budget=1e12, capacity_hours=1e12) for period in periods ] return build_stateful_plan( instance_id=instance_id, segments=segments, methods=methods, periods=relaxed_periods, config=StatefulConfig( risk_weight=1.0, cost_weight=cost_price, hours_weight=hours_price, max_seconds=max_seconds, ), created_utc=created_utc, )
[docs] def coordinate_stateful( *, instance_id: str, segments: list[StatefulSegment], methods: list[StatefulMethod], periods: list[StatefulPeriod], baseline: StatefulPlan, max_segments_per_cluster: int = 150, iterations: int = 12, initial_step: float = 0.5, max_seconds_per_cluster: float = 30.0, created_utc: datetime | None = None, ) -> CoordinationResult: """Run a Lagrangian subgradient bound for the clustered stateful problem. Parameters ---------- instance_id : str Instance id. segments, methods, periods : list Full stateful problem. baseline : StatefulPlan Feasible primal plan used for the gap. max_segments_per_cluster : int, optional Maximum cluster size. iterations : int, optional Number of subgradient iterations. initial_step : float, optional Initial price step. max_seconds_per_cluster : float, optional Exact MILP limit per cluster per iteration. created_utc : datetime, optional Creation time. Returns ------- CoordinationResult Iteration prices and the best dual lower bound. Raises ------ CoordinationError If inputs are invalid or no priced subproblem can be solved. """ if not segments or not methods or not periods: raise CoordinationError("segments, methods, and periods must be non-empty") if max_segments_per_cluster < 1 or iterations < 1: raise CoordinationError("cluster size and iterations must be positive") groups = _clusters(segments, max_segments_per_cluster) total_budget = sum(period.budget for period in periods) total_capacity = sum(period.capacity_hours for period in periods) if total_budget <= 0 or total_capacity <= 0: raise CoordinationError("total budget and capacity must be positive") cost_price = 0.0 hours_price = 0.0 history: list[PriceIteration] = [] best: PriceIteration | None = None for iteration in range(iterations): started = time.perf_counter() plans = [] for cluster_index, group in enumerate(groups, start=1): plans.append( _priced_plan( instance_id=f"{instance_id}-C{cluster_index:03d}", segments=group, methods=methods, periods=periods, cost_price=cost_price, hours_price=hours_price, max_seconds=max_seconds_per_cluster, created_utc=created_utc, ) ) elapsed = time.perf_counter() - started spend = sum(plan.total_cost for plan in plans) hours = sum(plan.total_hours for plan in plans) # plan.objective = risk + cost_price*cost/1e5 + hours_price*hours/1e5 dual = ( sum(plan.objective for plan in plans) - cost_price * total_budget / 100000.0 - hours_price * total_capacity / 100000.0 ) row = PriceIteration( iteration=iteration, cost_price=round(cost_price, 6), hours_price=round(hours_price, 6), dual_bound=round(dual, 6), spend=round(spend, 2), hours=round(hours, 2), cluster_seconds=round(elapsed, 3), ) history.append(row) if best is None or row.dual_bound > best.dual_bound: best = row step = initial_step / math.sqrt(iteration + 1) cost_price = max( 0.0, cost_price + step * (spend - total_budget) / max(total_budget, 1.0), ) hours_price = max( 0.0, hours_price + step * (hours - total_capacity) / max(total_capacity, 1.0), ) assert best is not None absolute_gap = baseline.objective - best.dual_bound return CoordinationResult( instance_id=instance_id, cluster_count=len(groups), max_segments_per_cluster=max_segments_per_cluster, baseline_objective=round(baseline.objective, 6), dual_bound=round(best.dual_bound, 6), absolute_gap=round(absolute_gap, 6), relative_gap=round(absolute_gap / abs(baseline.objective), 6) if baseline.objective != 0 else 0.0, iterations=history, best_iteration=best.iteration, best_cost_price=best.cost_price, best_hours_price=best.hours_price, created_utc=created_utc or datetime.now(UTC), )
__all__ = [ "COORDINATION_SCHEMA_VERSION", "CoordinationError", "CoordinationResult", "PriceIteration", "coordinate_stateful", ]