---
name: jmsc-algorithm
description: Use when designing and analyzing a solution algorithm for a 《管理科学学报》 (Journal of Management Sciences in China) manuscript — giving exact / heuristic / decomposition methods with complexity analysis and, for iterative methods, convergence proofs. "It runs fast" is not analysis. Use after the model and properties are established.
---

# 算法设计与分析（jmsc-algorithm）

## 触发时机

- 模型有了，但求解方法只是"调用求解器/跑得快"
- 算法没有复杂度分析，或没有收敛性论证
- 启发式无近似比/界，无法说明解的质量
- 审稿质疑"算法贡献在哪、能否保证收敛"

## 核心：算法必须可分析，不止可运行

本刊看的是**算法贡献的可分析性**："跑得快"不算分析。要么给**复杂度**（精确/近似算法），要么给**收敛性**（迭代算法），要么给**界/近似比**（启发式），三者至少其一并配数值验证。

## 算法类型与必答问题

| 算法类型 | 必须回答 |
|----------|----------|
| 精确算法（DP/B&B/列生成） | 时间/空间复杂度；状态空间规模；是否多项式 |
| 分解算法（Benders/Lagrangian/ADMM） | 子问题可解性；收敛到何点（最优/KKT）；收敛速率 |
| 迭代算法（梯度/不动点/拍卖） | 收敛性证明；步长条件；线性/次线性速率 |
| 启发式/近似 | 近似比 ρ 或最坏情形界；与下界的 gap |
| 元启发式（GA/SA/PSO） | 参数设定依据；与精确解/界对比（不能只给"更好"） |

## 复杂度分析要点

- 用 O(·) 给出**关于输入规模的**时间与空间复杂度，并指明输入规模如何定义（n 个客户、T 期、|S| 状态…）。
- 区分**最坏 / 平均 / 实例相关**复杂度，别混用。
- 若是 NP-hard 问题，先给硬度结论，再说明为何用启发式/近似。

## 收敛性分析要点

- 陈述收敛**到什么**（全局最优 / 局部 / 稳定点 / 均衡）。
- 给出收敛**条件**（凸性、步长、Lipschitz、单调）。
- 有条件就给**速率**（线性、次线性 O(1/k)、二阶）。

## 自检清单

- [ ] 算法用伪代码给出，输入/输出/终止条件明确
- [ ] 复杂度以 O(·) 表达，输入规模定义清楚
- [ ] 迭代算法有收敛性证明（到什么点、什么条件、什么速率）
- [ ] 启发式有近似比或与界/最优的 gap，而非只比对手好
- [ ] NP-hard 已说明，启发式的使用有正当理由
- [ ] 算法性质用数值实验验证（见 jmsc-numerical-experiments）

## 反模式

- 只说"算法高效""收敛快"，无 O(·)、无证明
- 元启发式只报"比基准好 X%"，不给界、不与最优/下界比
- 把"调用 CPLEX/Gurobi 求解"当成算法贡献
- 收敛图当收敛证明用

## 本刊算法节审稿期待与退稿模式

《管理科学学报》对算法贡献的核查围绕"可分析性"：硬度是否定位、复杂度/收敛/界是否至少给其一、数值是否回证理论界。下表对齐本刊高频退稿语与修法：

| 退稿信号 | 根因 | 本刊期望的修法 |
|----------|------|----------------|
| "算法只是工程实现" | 把调求解器/调包当贡献 | 给出针对模型结构的分解或精确算法，并证其性质 |
| "无复杂度分析" | 只报运行秒数 | 以 O(·) 写时间/空间，明确输入规模定义 |
| "收敛性未证" | 迭代法只给收敛图 | 证明收敛到何点、何条件、何速率，图仅作佐证 |
| "启发式解质量无保证" | 只比基准百分比 | 给近似比 ρ 或与下界/松弛解的 gap |
| "硬度未定位就上启发式" | 跳过复杂性归约 | 先给 NP-hard 归约或引用，再论证启发式的正当性 |

> 锚点：本刊已刊优化类论文常以"问题硬度 → 算法框架（伪代码）→ 复杂度/收敛定理 → 数值回证界"组织算法节；分解算法须说明子问题每次迭代可解。具体体例以编辑部最新稿约为准。

## 微型走查：医疗排班优化的算法分析

虚构稿件《急诊科医护协同排班的列生成算法》。按算法决策规则走一遍（示意数字仅作演示）：

- **硬度**：班次集合指数级，主问题为集合覆盖型整数规划，NP-hard（由集合覆盖归约），故不直接枚举。
- **算法框架**：列生成——主问题为线性松弛（限定班次池），子问题为带资源约束最短路（生成负 reduced cost 的新班次），外层分支定界保证整数最优。伪代码给出输入（n=30 名医护、T=14 天、技能等级 3 档）、输出（整数排班）、终止（无负 reduced cost 列且 LP=IP 或分支耗尽）。
- **复杂度**：定价子问题为带资源约束最短路，状态空间 O(T·|R|)，|R| 为资源标签数；整体非多项式（NP-hard 本质），报告列生成轮数随规模的经验增长。
- **解质量**：根节点 LP 给下界 LB=4180 工时成本，整数解 4310，gap≈3.1%，落在近优区间，并报分支定界封闭 gap。
- **收敛性**：列生成有限步终止（班次池有限），证每轮目标单调不增。

审稿人若追问"为何不直接用商业求解器跑 MIP"，回应应锚到可扩展性：n=30、T=14 时直接 MIP 1 小时内不收敛到 3% gap，列生成 6 分钟达到，体现算法贡献而非调包。

## 输出格式

```
【算法类型】精确 / 分解 / 迭代 / 启发式 / 元启发式
【伪代码】有 / 无（输入/输出/终止条件齐？）
【复杂度】时间 O(…)，空间 O(…)，输入规模=<…>
【收敛性】到<点>，条件<…>，速率<…> / 不适用
【解质量】近似比 ρ=… / gap=… / 仅经验对比（弱）
【硬度】NP-hard? 是/否 → 启发式理由
【下一步】jmsc-numerical-experiments
```