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

触发时机

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

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

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

算法类型与必答问题

复杂度分析要点

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

收敛性分析要点

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

自检清单

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

反模式

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

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

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

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

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

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

• 硬度：班次集合指数级，主问题为集合覆盖型整数规划，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