"""Typed move operators and feasibility repair for optimization assignments.
Operators propose reversible bundles of assignment changes. Each bundle records the exact before
and after option for every touched variable, so apply and undo are deterministic. Repair removes
access, budget, monitoring-budget, and capacity violations, and tries a treatment option for a
service miss; it never invents a fix for a blocked growth or treatment model.
"""
from __future__ import annotations
import random
from typing import Protocol
from pydantic import BaseModel, ConfigDict, Field, model_validator
from brushline.model.validation import ContractValidation
from brushline.optimization.evaluator import (
AssignmentChange,
EvaluationViolation,
ScheduleEvaluator,
)
from brushline.optimization.formulation import Formulation
OPERATOR_NAMES: tuple[str, ...] = (
"toggle",
"method_change",
"shift",
"swap",
"block_move",
"monitoring_move",
"destroy_repair",
)
[docs]
class OperatorError(ValueError):
"""Raised when a move or repair request is inconsistent."""
[docs]
class OperatorConfig(BaseModel):
"""Operator and repair settings.
Parameters
----------
max_block_periods : int, optional
Maximum periods in one block move. Defaults to 3.
destroy_fraction : float, optional
Share of variables destroyed before repair. Defaults to 0.2.
max_repair_steps : int, optional
Maximum repair changes. Defaults to 100.
respect_access : bool, optional
Skip treatment variables in inaccessible periods. Defaults to True.
locked_variables : list of int, optional
Variable indices that operators must not change.
"""
model_config = ConfigDict(extra="forbid", frozen=True)
max_block_periods: int = Field(default=3, ge=1, le=10)
destroy_fraction: float = Field(default=0.2, gt=0, le=1)
max_repair_steps: int = Field(default=100, ge=1, le=1000)
respect_access: bool = True
locked_variables: list[int] = Field(default_factory=list)
[docs]
class Move(BaseModel):
"""A reversible bundle of assignment changes.
Parameters
----------
kind : str
Move kind.
changes : tuple of AssignmentChange
Changes in application order.
description : str, optional
Human explanation.
"""
model_config = ConfigDict(extra="forbid", frozen=True)
kind: str = Field(min_length=1)
changes: tuple[AssignmentChange, ...] = Field(min_length=1)
description: str = ""
@model_validator(mode="after")
def _unique_variables(self) -> Move:
variables = [change.variable for change in self.changes]
if len(set(variables)) != len(variables):
raise ValueError("a move may touch each variable only once")
return self
[docs]
def apply(self, assignment: dict[int, int]) -> dict[int, int]:
"""Apply the move to an assignment.
Parameters
----------
assignment : dict of int to int
Current assignment.
Returns
-------
dict of int to int
New assignment.
Raises
------
OperatorError
When a before value does not match.
"""
updated = dict(assignment)
for change in self.changes:
if updated.get(change.variable) != change.before:
raise OperatorError(f"move before value does not match variable {change.variable}")
updated[change.variable] = change.after
return updated
[docs]
def undo(self, assignment: dict[int, int]) -> dict[int, int]:
"""Undo the move on an assignment.
Parameters
----------
assignment : dict of int to int
Current assignment.
Returns
-------
dict of int to int
Restored assignment.
Raises
------
OperatorError
When an after value does not match.
"""
updated = dict(assignment)
for change in reversed(self.changes):
if updated.get(change.variable) != change.after:
raise OperatorError(f"move after value does not match variable {change.variable}")
updated[change.variable] = change.before
return updated
[docs]
class MoveOperator(Protocol):
"""Protocol for a deterministic, seed-driven operator."""
name: str
[docs]
def propose(self, assignment: dict[int, int], rng: random.Random) -> Move | None:
"""Propose one move, or None when no eligible variable exists."""
...
[docs]
class OperatorState:
"""Shared eligibility and option helpers.
Parameters
----------
formulation : Formulation
Optimization formulation.
config : OperatorConfig, optional
Operator settings.
"""
def __init__(self, formulation: Formulation, config: OperatorConfig | None = None) -> None:
self.formulation = formulation
self.config = config or OperatorConfig()
self.variables = {variable.index: variable for variable in formulation.variables}
self.treatment_options = {
option.option_id: option for option in formulation.treatment_options
}
self.period_order = {
period.period_id: index
for index, period in enumerate(
sorted(formulation.periods, key=lambda item: item.start_year)
)
}
self.segments = {segment.segment_id: segment for segment in formulation.segments}
self.locked = set(self.config.locked_variables)
if any(index not in self.variables for index in self.locked):
raise OperatorError("locked variable is not in the formulation")
[docs]
def eligible(
self,
assignment: dict[int, int],
*,
kind: str | None = None,
selected: bool = False,
multiple_options: bool = False,
) -> list[int]:
"""Return eligible variable indices.
Parameters
----------
assignment : dict of int to int
Current assignment.
kind : str or None, optional
Restrict to ``treatment`` or ``monitoring``.
selected : bool, optional
Require a non-``none`` selection.
multiple_options : bool, optional
Require at least two options.
Returns
-------
list of int
Sorted eligible indices.
"""
indices: list[int] = []
for index, variable in sorted(self.variables.items()):
if index in self.locked:
continue
if kind is not None and variable.kind != kind:
continue
if multiple_options and len(variable.option_ids) < 2:
continue
option = assignment.get(index)
if option is None:
continue
if selected and option == 0:
continue
if self.config.respect_access and variable.kind == "treatment":
segment = self.segments[variable.target_id]
if variable.period_id in segment.inaccessible_period_ids:
continue
indices.append(index)
return indices
[docs]
def option_ids(self, index: int) -> list[str]:
"""Return option ids for one variable.
Parameters
----------
index : int
Variable index.
Returns
-------
list of str
Option ids.
"""
return list(self.variables[index].option_ids)
[docs]
def alternative(
self,
index: int,
assignment: dict[int, int],
rng: random.Random,
*,
different_method: bool = False,
) -> int | None:
"""Choose an alternative option index.
Parameters
----------
index : int
Variable index.
assignment : dict of int to int
Current assignment.
rng : random.Random
Random source.
different_method : bool, optional
Prefer a treatment option with a different method.
Returns
-------
int or None
Alternative option index, or None.
"""
variable = self.variables[index]
current = assignment[index]
alternatives = [option for option in range(len(variable.option_ids)) if option != current]
if different_method and variable.kind == "treatment":
current_method = self._method(variable.option_ids[current])
preferred = [
option
for option in alternatives
if self._method(variable.option_ids[option]) not in {None, current_method}
]
alternatives = preferred or alternatives
if not alternatives:
return None
return rng.choice(alternatives)
def _method(self, option_id: str) -> str | None:
option = self.treatment_options.get(option_id)
return None if option is None else option.method
[docs]
class ToggleOperator:
"""Toggle one variable to a random alternative option."""
name = "toggle"
def __init__(self, state: OperatorState) -> None:
self.state = state
[docs]
def propose(self, assignment: dict[int, int], rng: random.Random) -> Move | None:
"""Propose a toggle move.
Parameters
----------
assignment : dict of int to int
Current assignment.
rng : random.Random
Random source.
Returns
-------
Move or None
Toggle move, or None.
"""
candidates = self.state.eligible(assignment, multiple_options=True)
if not candidates:
return None
index = rng.choice(candidates)
after = self.state.alternative(index, assignment, rng)
if after is None:
return None
return Move(
kind=self.name,
changes=(AssignmentChange(variable=index, before=assignment[index], after=after),),
description="toggle one variable",
)
[docs]
class MethodChangeOperator:
"""Change one selected treatment to an option with a different method."""
name = "method_change"
def __init__(self, state: OperatorState) -> None:
self.state = state
[docs]
def propose(self, assignment: dict[int, int], rng: random.Random) -> Move | None:
"""Propose a method change.
Parameters
----------
assignment : dict of int to int
Current assignment.
rng : random.Random
Random source.
Returns
-------
Move or None
Method change, or None.
"""
candidates = self.state.eligible(
assignment, kind="treatment", selected=True, multiple_options=True
)
candidates = [
index
for index in candidates
if any(
self.state._method(self.state.option_ids(index)[option])
not in {None, self.state._method(self.state.option_ids(index)[assignment[index]])}
for option in range(len(self.state.option_ids(index)))
if option != assignment[index]
)
]
if not candidates:
return None
index = rng.choice(candidates)
after = self.state.alternative(index, assignment, rng, different_method=True)
if after is None:
return None
return Move(
kind=self.name,
changes=(AssignmentChange(variable=index, before=assignment[index], after=after),),
description="change the treatment method",
)
[docs]
class ShiftOperator:
"""Shift one selected treatment to the adjacent period for the same segment."""
name = "shift"
def __init__(self, state: OperatorState) -> None:
self.state = state
[docs]
def propose(self, assignment: dict[int, int], rng: random.Random) -> Move | None:
"""Propose a period shift.
Parameters
----------
assignment : dict of int to int
Current assignment.
rng : random.Random
Random source.
Returns
-------
Move or None
Period shift, or None.
"""
candidates = self.state.eligible(assignment, kind="treatment", selected=True)
pairs: list[tuple[int, int]] = []
for index in candidates:
variable = self.state.variables[index]
option_id = variable.option_ids[assignment[index]]
for candidate in self.state.variables.values():
if (
candidate.kind == "treatment"
and candidate.target_id == variable.target_id
and abs(
self.state.period_order[candidate.period_id]
- self.state.period_order[variable.period_id]
)
== 1
and option_id in candidate.option_ids
and candidate.index not in self.state.locked
and not (
self.state.config.respect_access
and candidate.period_id
in self.state.segments[candidate.target_id].inaccessible_period_ids
)
):
pairs.append((index, candidate.index))
if not pairs:
return None
source, target = rng.choice(sorted(pairs))
option_id = self.state.variables[source].option_ids[assignment[source]]
target_after = self.state.variables[target].option_ids.index(option_id)
return Move(
kind=self.name,
changes=(
AssignmentChange(variable=source, before=assignment[source], after=0),
AssignmentChange(
variable=target,
before=assignment[target],
after=target_after,
),
),
description="shift a treatment to the adjacent period",
)
[docs]
class SwapOperator:
"""Swap options between two eligible variables of the same kind."""
name = "swap"
def __init__(self, state: OperatorState) -> None:
self.state = state
[docs]
def propose(self, assignment: dict[int, int], rng: random.Random) -> Move | None:
"""Propose a swap.
Parameters
----------
assignment : dict of int to int
Current assignment.
rng : random.Random
Random source.
Returns
-------
Move or None
Swap, or None.
"""
candidates = self.state.eligible(assignment)
by_kind: dict[str, list[int]] = {}
for index in candidates:
by_kind.setdefault(self.state.variables[index].kind, []).append(index)
pairs: list[tuple[int, int]] = []
for indices in by_kind.values():
for left_position, left in enumerate(indices):
for right in indices[left_position + 1 :]:
left_option = self.state.variables[left].option_ids[assignment[left]]
right_option = self.state.variables[right].option_ids[assignment[right]]
if (
left_option != right_option
and left_option in self.state.variables[right].option_ids
and right_option in self.state.variables[left].option_ids
):
pairs.append((left, right))
if not pairs:
return None
left, right = rng.choice(sorted(pairs))
left_before = assignment[left]
right_before = assignment[right]
left_after = self.state.variables[left].option_ids.index(
self.state.variables[right].option_ids[right_before]
)
right_after = self.state.variables[right].option_ids.index(
self.state.variables[left].option_ids[left_before]
)
return Move(
kind=self.name,
changes=(
AssignmentChange(variable=left, before=left_before, after=left_after),
AssignmentChange(variable=right, before=right_before, after=right_after),
),
description="swap two assignments",
)
[docs]
class BlockMoveOperator:
"""Set a contiguous period block for one segment to one treatment option."""
name = "block_move"
def __init__(self, state: OperatorState) -> None:
self.state = state
[docs]
def propose(self, assignment: dict[int, int], rng: random.Random) -> Move | None:
"""Propose a block move.
Parameters
----------
assignment : dict of int to int
Current assignment.
rng : random.Random
Random source.
Returns
-------
Move or None
Block move, or None.
"""
blocks: list[tuple[int, ...]] = []
for segment in self.state.formulation.segments:
variables = sorted(
[
variable
for variable in self.state.variables.values()
if variable.kind == "treatment"
and variable.target_id == segment.segment_id
and variable.index not in self.state.locked
and not (
self.state.config.respect_access
and variable.period_id in segment.inaccessible_period_ids
)
],
key=lambda item: self.state.period_order[item.period_id],
)
for start in range(len(variables)):
for length in range(1, self.state.config.max_block_periods + 1):
block = tuple(item.index for item in variables[start : start + length])
if len(block) == length:
blocks.append(block)
if not blocks:
return None
block = rng.choice(blocks)
option_ids = self.state.variables[block[0]].option_ids
option = rng.choice(list(range(1, len(option_ids))) or [0])
option_id = option_ids[option]
changes_list: list[AssignmentChange] = []
for index in block:
target_ids = self.state.variables[index].option_ids
after = target_ids.index(option_id) if option_id in target_ids else 0
changes_list.append(
AssignmentChange(
variable=index,
before=assignment[index],
after=after,
)
)
changes = tuple(changes_list)
if all(change.before == change.after for change in changes):
return None
return Move(
kind=self.name,
changes=changes,
description="set a contiguous treatment block",
)
[docs]
class MonitoringMoveOperator:
"""Change one monitoring option."""
name = "monitoring_move"
def __init__(self, state: OperatorState) -> None:
self.state = state
[docs]
def propose(self, assignment: dict[int, int], rng: random.Random) -> Move | None:
"""Propose a monitoring move.
Parameters
----------
assignment : dict of int to int
Current assignment.
rng : random.Random
Random source.
Returns
-------
Move or None
Monitoring move, or None.
"""
candidates = self.state.eligible(assignment, kind="monitoring", multiple_options=True)
if not candidates:
return None
index = rng.choice(candidates)
after = self.state.alternative(index, assignment, rng)
if after is None:
return None
return Move(
kind=self.name,
changes=(AssignmentChange(variable=index, before=assignment[index], after=after),),
description="change the monitoring option",
)
[docs]
class RepairResult(BaseModel):
"""The result of a deterministic feasibility repair.
Parameters
----------
assignment : dict of int to int
Repaired assignment.
changes : list of AssignmentChange
Applied repair changes.
feasible : bool
Whether all hard violations were removed.
remaining : list of EvaluationViolation
Remaining hard violations.
"""
model_config = ConfigDict(extra="forbid", frozen=True)
assignment: dict[int, int]
changes: list[AssignmentChange] = Field(default_factory=list)
feasible: bool
remaining: list[EvaluationViolation] = Field(default_factory=list)
[docs]
def repair_assignment(
evaluator: ScheduleEvaluator,
assignment: dict[int, int],
config: OperatorConfig | None = None,
) -> RepairResult:
"""Repair resource and access violations deterministically.
Parameters
----------
evaluator : ScheduleEvaluator
Exact evaluator.
assignment : dict of int to int
Starting assignment.
config : OperatorConfig, optional
Repair settings.
Returns
-------
RepairResult
Repaired assignment, changes, feasibility, and remaining violations.
"""
rules = config or OperatorConfig()
state = OperatorState(evaluator.formulation, rules)
current = dict(assignment)
changes: list[AssignmentChange] = []
for _ in range(rules.max_repair_steps):
result = evaluator.evaluate(current)
if result.feasible:
return RepairResult(assignment=current, changes=changes, feasible=True)
violation = result.violations[0]
change = _repair_change(evaluator, state, current, violation)
if change is None:
return RepairResult(
assignment=current,
changes=changes,
feasible=False,
remaining=result.violations,
)
current[change.variable] = change.after
changes.append(change)
final = evaluator.evaluate(current)
return RepairResult(
assignment=current,
changes=changes,
feasible=final.feasible,
remaining=final.violations,
)
def _repair_change(
evaluator: ScheduleEvaluator,
state: OperatorState,
assignment: dict[int, int],
violation: EvaluationViolation,
) -> AssignmentChange | None:
if violation.code == "EVALUATION-ACCESS" and violation.variable_index is not None:
index = violation.variable_index
if index in state.locked or assignment.get(index) == 0:
return None
return AssignmentChange(variable=index, before=assignment[index], after=0)
if violation.code in {
"EVALUATION-BUDGET",
"EVALUATION-MONITORING-BUDGET",
"EVALUATION-CAPACITY",
}:
if violation.code == "EVALUATION-MONITORING-BUDGET":
candidates = [
index
for index in state.eligible(assignment, kind="monitoring", selected=True)
if state.variables[index].period_id == violation.period_id
]
else:
candidates = [
index
for index in state.eligible(assignment, kind="treatment", selected=True)
if state.variables[index].period_id == violation.period_id
and (
violation.code != "EVALUATION-CAPACITY"
or state._method(state.variables[index].option_ids[assignment[index]])
== violation.target_id
)
]
if not candidates:
return None
index = sorted(candidates)[-1]
return AssignmentChange(variable=index, before=assignment[index], after=0)
if violation.code == "EVALUATION-SERVICE" and violation.target_id is not None:
variable = next(
(
item
for item in state.variables.values()
if item.kind == "treatment"
and item.target_id == violation.target_id
and item.period_id == violation.period_id
),
None,
)
if variable is None or len(variable.option_ids) < 2:
return None
if variable.index in state.locked:
return None
before = assignment[variable.index]
after = next(
(option for option in range(1, len(variable.option_ids)) if option != before),
None,
)
if after is None: # pragma: no cover - guarded by the option-count check above
return None
return AssignmentChange(variable=variable.index, before=before, after=after)
return None
[docs]
class RepairOperator:
"""Reset a random subset and repair feasibility."""
name = "destroy_repair"
def __init__(
self,
state: OperatorState,
evaluator: ScheduleEvaluator,
) -> None:
self.state = state
self.evaluator = evaluator
[docs]
def propose(self, assignment: dict[int, int], rng: random.Random) -> Move | None:
"""Propose a destroy-repair move.
Parameters
----------
assignment : dict of int to int
Current assignment.
rng : random.Random
Random source.
Returns
-------
Move or None
Destroy-repair move, or None.
"""
candidates = self.state.eligible(assignment, selected=True)
if not candidates:
return None
count = max(1, round(len(candidates) * self.state.config.destroy_fraction))
destroyed = set(rng.sample(candidates, min(count, len(candidates))))
current = dict(assignment)
for index in destroyed:
current[index] = 0
repaired = repair_assignment(self.evaluator, current, self.state.config)
changed = [
AssignmentChange(
variable=index,
before=assignment[index],
after=repaired.assignment[index],
)
for index in sorted(assignment)
if assignment[index] != repaired.assignment[index]
]
if not changed:
return None
return Move(
kind=self.name,
changes=tuple(changed),
description="destroy a subset and repair feasibility",
)
[docs]
def default_operators(
evaluator: ScheduleEvaluator, config: OperatorConfig | None = None
) -> tuple[MoveOperator, ...]:
"""Return the default operator portfolio.
Parameters
----------
evaluator : ScheduleEvaluator
Exact evaluator.
config : OperatorConfig, optional
Operator settings.
Returns
-------
tuple of MoveOperator
Toggle, method change, shift, swap, block, monitoring, and repair operators.
"""
state = OperatorState(evaluator.formulation, config)
return (
ToggleOperator(state),
MethodChangeOperator(state),
ShiftOperator(state),
SwapOperator(state),
BlockMoveOperator(state),
MonitoringMoveOperator(state),
RepairOperator(state, evaluator),
)
[docs]
def apply_move(assignment: dict[int, int], move: Move) -> dict[int, int]:
"""Apply a move.
Parameters
----------
assignment : dict of int to int
Current assignment.
move : Move
Move to apply.
Returns
-------
dict of int to int
New assignment.
"""
return move.apply(assignment)
[docs]
def undo_move(assignment: dict[int, int], move: Move) -> dict[int, int]:
"""Undo a move.
Parameters
----------
assignment : dict of int to int
Current assignment.
move : Move
Move to undo.
Returns
-------
dict of int to int
Restored assignment.
"""
return move.undo(assignment)
[docs]
def validate_move(formulation: Formulation, move: Move) -> ContractValidation:
"""Validate that every touched option exists.
Parameters
----------
formulation : Formulation
Formulation.
move : Move
Move to validate.
Returns
-------
ContractValidation
Errors and counts.
"""
errors: list[str] = []
variables = {variable.index: variable for variable in formulation.variables}
for change in move.changes:
variable = variables.get(change.variable)
if variable is None:
errors.append(f"MOVE-VARIABLE: unknown variable {change.variable}")
continue
for option in (change.before, change.after):
if option < 0 or option >= len(variable.option_ids):
errors.append(f"MOVE-OPTION: variable {change.variable} option {option} is invalid")
return ContractValidation(tuple(errors), (), {"changes": len(move.changes)})
__all__ = [
"OPERATOR_NAMES",
"BlockMoveOperator",
"MethodChangeOperator",
"MonitoringMoveOperator",
"Move",
"MoveOperator",
"OperatorConfig",
"OperatorError",
"OperatorState",
"RepairOperator",
"RepairResult",
"ShiftOperator",
"SwapOperator",
"ToggleOperator",
"apply_move",
"default_operators",
"repair_assignment",
"undo_move",
"validate_move",
]