343 lines
14 KiB
Python
343 lines
14 KiB
Python
|
from __future__ import annotations
|
||
|
|
|
||
|
|
import json
|
||
|
|
import math
|
||
|
|
from datetime import date
|
||
|
|
from typing import Any
|
||
|
|
|
||
|
|
from ortools.linear_solver import pywraplp
|
||
|
|
|
||
|
|
_MODEL_SCOPE = "diagnostic-conflict-relaxation"
|
||
|
|
_METHOD = "glop-diagnostic-relaxation.v1"
|
||
|
|
_NUMERICAL_TOLERANCE = 1e-7
|
||
|
|
_MINUTE_RELAXATIONS = {
|
||
|
|
"C4_maintenance": "maintenance-overlap-minute",
|
||
|
|
"C7_capacity": "line-day-capacity-minute",
|
||
|
|
"C8_due_date": "order-due-allowance-minute",
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
def _degree_minutes(
|
||
|
|
constraint_id: str, row: dict[str, Any],
|
||
|
|
) -> tuple[float, str, float] | None:
|
||
|
|
degree = row.get("degree") or {}
|
||
|
|
kind = str(degree.get("kind") or "")
|
||
|
|
expected_kind = {
|
||
|
|
"C4_maintenance": "overlap_minutes",
|
||
|
|
"C7_capacity": "overload_minutes",
|
||
|
|
"C8_due_date": "hours_late",
|
||
|
|
}.get(constraint_id)
|
||
|
|
if kind != expected_kind:
|
||
|
|
return None
|
||
|
|
try:
|
||
|
|
value = float(degree.get("value"))
|
||
|
|
except (TypeError, ValueError):
|
||
|
|
return None
|
||
|
|
if not math.isfinite(value) or value <= 0:
|
||
|
|
return None
|
||
|
|
if kind == "hours_late":
|
||
|
|
return value * 60.0, "solve-log-description", 6.0
|
||
|
|
if kind == "overload_minutes":
|
||
|
|
return value, "solve-log-description", 1.0
|
||
|
|
if kind == "overlap_minutes":
|
||
|
|
return value, "schedule-maintenance-overlap", 0.1
|
||
|
|
return None
|
||
|
|
|
||
|
|
|
||
|
|
def _evidence_ref(row: dict[str, Any]) -> str:
|
||
|
|
conflict_id = row.get("conflictId")
|
||
|
|
if conflict_id is not None:
|
||
|
|
return f"conflict#{conflict_id}"
|
||
|
|
return "anonymous:" + "|".join(str(row.get(key) or "") for key in (
|
||
|
|
"constraintId", "resourceName", "conflictTimeStart", "description",
|
||
|
|
))
|
||
|
|
|
||
|
|
|
||
|
|
def _physical_rhs_key(constraint_id: str, row: dict[str, Any]) -> str | None:
|
||
|
|
degree = row.get("degree") or {}
|
||
|
|
if constraint_id == "C7_capacity":
|
||
|
|
resource = str(row.get("resourceName") or "").strip()
|
||
|
|
day = str(row.get("conflictTimeStart") or "")[:10]
|
||
|
|
try:
|
||
|
|
parsed_day = date.fromisoformat(day)
|
||
|
|
except ValueError:
|
||
|
|
return None
|
||
|
|
if not resource or parsed_day.isoformat() != day:
|
||
|
|
return None
|
||
|
|
return f"{constraint_id}|{resource}|{day}"
|
||
|
|
if constraint_id == "C8_due_date":
|
||
|
|
order_nos = row.get("orderNos") or []
|
||
|
|
order_no = str(order_nos[0] if order_nos else "").strip()
|
||
|
|
if not order_no:
|
||
|
|
return None
|
||
|
|
return f"{constraint_id}|{order_no}"
|
||
|
|
if constraint_id == "C4_maintenance":
|
||
|
|
resource = str(row.get("resourceName") or "").strip()
|
||
|
|
anchor = str(
|
||
|
|
degree.get("maintenanceStart") or row.get("conflictTimeStart") or ""
|
||
|
|
).strip()
|
||
|
|
if not resource or not anchor:
|
||
|
|
return None
|
||
|
|
return f"{constraint_id}|{resource}|{anchor}"
|
||
|
|
return None
|
||
|
|
|
||
|
|
|
||
|
|
def _solve_relaxation(degrees: list[float], cap_minutes: float) -> dict[str, Any]:
|
||
|
|
solver = pywraplp.Solver.CreateSolver("GLOP")
|
||
|
|
if solver is None:
|
||
|
|
return {"status": "SOLVER_UNAVAILABLE", "objective": None, "capDual": None}
|
||
|
|
infinity = solver.infinity()
|
||
|
|
relaxation = solver.NumVar(0.0, infinity, "uniform_relaxation_minutes")
|
||
|
|
cap = solver.Constraint(-infinity, float(cap_minutes), "relaxation_cap")
|
||
|
|
cap.SetCoefficient(relaxation, 1.0)
|
||
|
|
objective = solver.Objective()
|
||
|
|
objective.SetMinimization()
|
||
|
|
for index, degree in enumerate(degrees):
|
||
|
|
residual = solver.NumVar(0.0, infinity, f"residual_{index}")
|
||
|
|
demand = solver.Constraint(float(degree), infinity, f"violation_{index}")
|
||
|
|
demand.SetCoefficient(residual, 1.0)
|
||
|
|
demand.SetCoefficient(relaxation, 1.0)
|
||
|
|
objective.SetCoefficient(residual, 1.0)
|
||
|
|
status = solver.Solve()
|
||
|
|
if status != pywraplp.Solver.OPTIMAL:
|
||
|
|
return {"status": f"SOLVER_STATUS_{status}", "objective": None, "capDual": None}
|
||
|
|
return {
|
||
|
|
"status": "OPTIMAL",
|
||
|
|
"objective": float(objective.Value()),
|
||
|
|
"capDual": float(cap.dual_value()),
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
def _row_signature(row: dict[str, Any]) -> str:
|
||
|
|
relevant = {
|
||
|
|
key: row.get(key) for key in (
|
||
|
|
"constraintId", "reliefConstraintIds", "resourceName", "conflictTimeStart",
|
||
|
|
"orderNos", "degree", "description",
|
||
|
|
)
|
||
|
|
}
|
||
|
|
return json.dumps(relevant, ensure_ascii=True, sort_keys=True, separators=(",", ":"))
|
||
|
|
|
||
|
|
|
||
|
|
def _unique_rows(
|
||
|
|
rows: list[dict[str, Any]],
|
||
|
|
) -> tuple[list[dict[str, Any]], list[str], int]:
|
||
|
|
grouped: dict[str, dict[str, dict[str, Any]]] = {}
|
||
|
|
for row in rows:
|
||
|
|
ref = _evidence_ref(row)
|
||
|
|
grouped.setdefault(ref, {}).setdefault(_row_signature(row), row)
|
||
|
|
unique: list[dict[str, Any]] = []
|
||
|
|
conflicting_refs: list[str] = []
|
||
|
|
duplicate_count = 0
|
||
|
|
for ref in sorted(grouped):
|
||
|
|
variants = grouped[ref]
|
||
|
|
raw_count = sum(1 for row in rows if _evidence_ref(row) == ref)
|
||
|
|
if len(variants) != 1:
|
||
|
|
conflicting_refs.append(ref)
|
||
|
|
continue
|
||
|
|
unique.append(next(iter(variants.values())))
|
||
|
|
duplicate_count += max(0, raw_count - 1)
|
||
|
|
return unique, conflicting_refs, duplicate_count
|
||
|
|
|
||
|
|
|
||
|
|
def _constraint_ids(row: dict[str, Any]) -> set[str]:
|
||
|
|
return {
|
||
|
|
str(value) for value in (
|
||
|
|
row.get("reliefConstraintIds") or [row.get("constraintId")]
|
||
|
|
) if value
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
def analyze_diagnostic_lp(attributions: list[dict[str, Any]]) -> dict[str, Any]:
|
||
|
|
"""Re-solve a documented diagnostic LP; never present the result as a CP-SAT dual."""
|
||
|
|
sanitized_rows, global_conflicting_refs, global_duplicate_count = _unique_rows(attributions)
|
||
|
|
constraint_ids = sorted({
|
||
|
|
str(constraint_id)
|
||
|
|
for row in attributions
|
||
|
|
for constraint_id in _constraint_ids(row)
|
||
|
|
if constraint_id
|
||
|
|
})
|
||
|
|
conflicts_by_constraint: dict[str, list[str]] = {constraint_id: [] for constraint_id in constraint_ids}
|
||
|
|
for row in attributions:
|
||
|
|
ref = _evidence_ref(row)
|
||
|
|
if ref not in global_conflicting_refs:
|
||
|
|
continue
|
||
|
|
for constraint_id in _constraint_ids(row):
|
||
|
|
conflicts_by_constraint.setdefault(constraint_id, []).append(ref)
|
||
|
|
constraints: dict[str, dict[str, Any]] = {}
|
||
|
|
for constraint_id in constraint_ids:
|
||
|
|
raw_applicable = [
|
||
|
|
row for row in attributions
|
||
|
|
if constraint_id in _constraint_ids(row)
|
||
|
|
]
|
||
|
|
_, local_conflicting_refs, duplicate_evidence_id_count = _unique_rows(raw_applicable)
|
||
|
|
conflicting_refs = sorted(set(
|
||
|
|
local_conflicting_refs + conflicts_by_constraint.get(constraint_id, [])
|
||
|
|
))
|
||
|
|
applicable = [
|
||
|
|
row for row in sanitized_rows if constraint_id in _constraint_ids(row)
|
||
|
|
]
|
||
|
|
shared_refs = [
|
||
|
|
_evidence_ref(row) for row in applicable
|
||
|
|
if len(row.get("reliefConstraintIds") or []) > 1
|
||
|
|
]
|
||
|
|
grouped: dict[str, dict[str, Any]] = {}
|
||
|
|
unsupported_refs: list[str] = []
|
||
|
|
deduplicated_refs: list[str] = []
|
||
|
|
input_sources: set[str] = set()
|
||
|
|
input_precision = 0.0
|
||
|
|
for row in applicable:
|
||
|
|
quantified = _degree_minutes(constraint_id, row)
|
||
|
|
if (
|
||
|
|
constraint_id not in _MINUTE_RELAXATIONS
|
||
|
|
or str(row.get("constraintId") or "") != constraint_id
|
||
|
|
or quantified is None
|
||
|
|
):
|
||
|
|
unsupported_refs.append(_evidence_ref(row))
|
||
|
|
continue
|
||
|
|
minutes, source, precision = quantified
|
||
|
|
rhs_key = _physical_rhs_key(constraint_id, row)
|
||
|
|
if rhs_key is None:
|
||
|
|
unsupported_refs.append(_evidence_ref(row))
|
||
|
|
continue
|
||
|
|
current = grouped.get(rhs_key)
|
||
|
|
if current is None:
|
||
|
|
grouped[rhs_key] = {
|
||
|
|
"minutes": minutes,
|
||
|
|
"evidenceRef": _evidence_ref(row),
|
||
|
|
}
|
||
|
|
elif minutes > current["minutes"]:
|
||
|
|
deduplicated_refs.append(current["evidenceRef"])
|
||
|
|
grouped[rhs_key] = {
|
||
|
|
"minutes": minutes,
|
||
|
|
"evidenceRef": _evidence_ref(row),
|
||
|
|
}
|
||
|
|
else:
|
||
|
|
deduplicated_refs.append(_evidence_ref(row))
|
||
|
|
input_sources.add(source)
|
||
|
|
input_precision = max(input_precision, precision)
|
||
|
|
|
||
|
|
common = {
|
||
|
|
"method": _METHOD,
|
||
|
|
"solver": "GLOP",
|
||
|
|
"modelScope": _MODEL_SCOPE,
|
||
|
|
"counterfactualMode": "one-constraint-at-a-time",
|
||
|
|
"nonAdditiveAcrossConstraints": True,
|
||
|
|
"uniformAcrossEvidenceRows": True,
|
||
|
|
"objectiveUnit": "residual-minute",
|
||
|
|
"relaxationUnit": "minute",
|
||
|
|
"relaxationMeaning": _MINUTE_RELAXATIONS.get(constraint_id),
|
||
|
|
"exactForLpModel": True,
|
||
|
|
"exactForCpSat": False,
|
||
|
|
"numericalTolerance": _NUMERICAL_TOLERANCE,
|
||
|
|
"evidenceCount": len(applicable),
|
||
|
|
"quantifiedCount": len(grouped),
|
||
|
|
"unsupportedCount": len(unsupported_refs),
|
||
|
|
"unsupportedEvidenceRefs": unsupported_refs,
|
||
|
|
"sharedReliefEvidenceRefs": shared_refs,
|
||
|
|
"conflictingDuplicateEvidenceRefs": conflicting_refs,
|
||
|
|
"duplicateEvidenceIdCount": duplicate_evidence_id_count,
|
||
|
|
"inputConsistencyPassed": not conflicting_refs,
|
||
|
|
"deduplicatedCount": len(deduplicated_refs),
|
||
|
|
"deduplicatedEvidenceRefs": sorted(deduplicated_refs),
|
||
|
|
"inputSources": sorted(input_sources),
|
||
|
|
"inputPrecisionMinutes": input_precision or None,
|
||
|
|
}
|
||
|
|
if conflicting_refs:
|
||
|
|
constraints[constraint_id] = {
|
||
|
|
**common,
|
||
|
|
"status": "unsupported",
|
||
|
|
"reason": "同一 conflictId 存在不一致载荷，诊断已失败关闭",
|
||
|
|
"localMarginalBenefit": None,
|
||
|
|
"oneMinuteBenefit": None,
|
||
|
|
"capDualEvidence": None,
|
||
|
|
"dualConsistencyPassed": False,
|
||
|
|
}
|
||
|
|
continue
|
||
|
|
if not grouped:
|
||
|
|
if constraint_id not in _MINUTE_RELAXATIONS:
|
||
|
|
reason = "该约束没有定义分钟型 RHS 松弛语义"
|
||
|
|
else:
|
||
|
|
reason = "没有可量化且直接归属该约束的分钟证据"
|
||
|
|
constraints[constraint_id] = {
|
||
|
|
**common,
|
||
|
|
"status": "unsupported",
|
||
|
|
"reason": reason,
|
||
|
|
"localMarginalBenefit": None,
|
||
|
|
"oneMinuteBenefit": None,
|
||
|
|
"capDualEvidence": None,
|
||
|
|
"dualConsistencyPassed": False,
|
||
|
|
}
|
||
|
|
continue
|
||
|
|
|
||
|
|
grouped_keys = sorted(grouped)
|
||
|
|
degrees = [grouped[key]["minutes"] for key in grouped_keys]
|
||
|
|
baseline = _solve_relaxation(degrees, 0.0)
|
||
|
|
local_step = min(1.0, min(degrees) / 2.0)
|
||
|
|
local = _solve_relaxation(degrees, local_step)
|
||
|
|
one_minute = _solve_relaxation(degrees, 1.0)
|
||
|
|
if any(result["status"] != "OPTIMAL" for result in (baseline, local, one_minute)):
|
||
|
|
constraints[constraint_id] = {
|
||
|
|
**common,
|
||
|
|
"status": "solver_error",
|
||
|
|
"reason": " / ".join(result["status"] for result in (baseline, local, one_minute)),
|
||
|
|
"localMarginalBenefit": None,
|
||
|
|
"oneMinuteBenefit": None,
|
||
|
|
"capDualEvidence": None,
|
||
|
|
"dualConsistencyPassed": False,
|
||
|
|
}
|
||
|
|
continue
|
||
|
|
|
||
|
|
local_benefit = (
|
||
|
|
float(baseline["objective"]) - float(local["objective"])
|
||
|
|
) / local_step
|
||
|
|
one_minute_benefit = float(baseline["objective"]) - float(one_minute["objective"])
|
||
|
|
cap_dual_benefit = max(0.0, -float(baseline["capDual"]))
|
||
|
|
consistency_error = abs(local_benefit - cap_dual_benefit)
|
||
|
|
constraints[constraint_id] = {
|
||
|
|
**common,
|
||
|
|
"status": "available",
|
||
|
|
"solverStatus": "OPTIMAL",
|
||
|
|
"localMarginalBenefit": round(local_benefit, 6),
|
||
|
|
"localStepMinutes": round(local_step, 6),
|
||
|
|
"oneMinuteBenefit": round(one_minute_benefit, 6),
|
||
|
|
"capDualEvidence": round(cap_dual_benefit, 6),
|
||
|
|
"rawCapDual": round(float(baseline["capDual"]), 6),
|
||
|
|
"dualConsistencyError": round(consistency_error, 9),
|
||
|
|
"dualConsistencyPassed": consistency_error <= _NUMERICAL_TOLERANCE,
|
||
|
|
"baselineObjectiveMinutes": round(float(baseline["objective"]), 6),
|
||
|
|
"localObjectiveMinutes": round(float(local["objective"]), 6),
|
||
|
|
"oneMinuteObjectiveMinutes": round(float(one_minute["objective"]), 6),
|
||
|
|
"sourceEvidenceRefs": [grouped[key]["evidenceRef"] for key in grouped_keys],
|
||
|
|
"interpretation": (
|
||
|
|
"局部有限差分给出统一放宽该约束时总残余违反分钟数的边际下降率；"
|
||
|
|
"GLOP cap dual 仅作数值一致性证据。"
|
||
|
|
),
|
||
|
|
}
|
||
|
|
|
||
|
|
available = [row for row in constraints.values() if row["status"] == "available"]
|
||
|
|
unsupported = [row for row in constraints.values() if row["status"] == "unsupported"]
|
||
|
|
solver_errors = [row for row in constraints.values() if row["status"] == "solver_error"]
|
||
|
|
return {
|
||
|
|
"method": _METHOD,
|
||
|
|
"solver": "GLOP",
|
||
|
|
"modelScope": _MODEL_SCOPE,
|
||
|
|
"counterfactualMode": "one-constraint-at-a-time",
|
||
|
|
"nonAdditiveAcrossConstraints": True,
|
||
|
|
"uniformAcrossEvidenceRows": True,
|
||
|
|
"exactForLpModel": True,
|
||
|
|
"exactForCpSat": False,
|
||
|
|
"cpSatNote": "CP-SAT 不提供对偶变量；本结果只对明示的诊断线性松弛模型成立。",
|
||
|
|
"availableConstraints": len(available),
|
||
|
|
"unsupportedConstraints": len(unsupported),
|
||
|
|
"solverErrorConstraints": len(solver_errors),
|
||
|
|
"conflictingDuplicateEvidenceRefs": global_conflicting_refs,
|
||
|
|
"duplicateEvidenceIdCount": global_duplicate_count,
|
||
|
|
"inputConsistencyPassed": not global_conflicting_refs,
|
||
|
|
"dualConsistencyPassed": (
|
||
|
|
bool(available) and not solver_errors and not global_conflicting_refs and all(
|
||
|
|
row["dualConsistencyPassed"] for row in available
|
||
|
|
)
|
||
|
|
),
|
||
|
|
"constraints": constraints,
|
||
|
|
}
|