你用 LNS 求解带时间窗的车辆路径问题：每轮随机移除 15% 的客户，再用贪心插入修复，只接受更好的解。你发现搜索很快停滞，而且修复阶段经常插不回去，导致解反而变差。请回答：(a) 为什么随机移除可能不如 Shaw/相关移除？(b) 修复失败时你会在算法上做什么改动？(c) 只接受更好解与模拟退火式接受相比有什么问题，你会怎么取舍？

面试官在考什么

是否分得清 destroy/repair 的分工、会用问题结构设计移除算子，并理解接受准则对搜索行为的影响。

大邻域搜索

回答框架 · 前两步

1. 随机移除不利用问题结构；Shaw/相关移除把地理近、时间窗相似、同路径或需求相近的客户一起移除，修复阶段才有机会把它们重新组合到更好的位置。
2. 修复失败的处理：用 regret insertion、允许暂时违反软约束、带回溯或允许部分插入、或增大修复算力；不能失败就直接丢弃整轮。

同一能力域的其他题

• 你说做过排产调度，用了遗传算法/模拟退火。请说明你的编码方式（染色体/状态表示）是什么？适应度函数里有没有加惩罚项？为什么？
• 你要实现一个最小化 0-1 整数规划的分支定界求解器。某实例根节点 LP 松弛下界 = 100，已知最优整数解 = 118。跑完 10 万个节点后 incumbent 仍是 118，open list 里还有 5 万个节点，其中最好的下界是 104。请回答：(a) 你用什么指标判断瓶颈在“下界太松”还是在“分支/节点选择策略差”？(b) 如果不改模型语义，只改界的紧度，列出两种手段并说明各自代价；(c) 当前 incumbent = 118，某子节点 LP 下界恰好等于 118 且解是分数，你是否剪枝，为什么？
• 一个 0-1 整数规划模型：200 个 0-1 变量、500 条约束，用求解器跑 1 小时，MIP gap 仍有 28%。日志显示 root LP relaxation 的目标值只比初始可行解好 5%，搜索树在第 3 层就展开出上万个节点。你会优先动哪几个地方？先动哪个、为什么？
• 你负责一个生产排程的混合整数规划求解服务：约 10 万变量，约束以背包和先后关系为主，16 核机器，当前分支定界跑 20 小时仍有 5% gap，LP 重求解占 80% 时间。业务要求 2 小时内给出可执行方案。团队提出三条路线：A 自研强分支+并行 B&B；B 增加问题特定割平面；C 改用约束规划/商用求解器或启发式先给可行解。作为技术负责人，你如何诊断瓶颈、排序路线、做 build/buy 取舍，并给出 90 天落地计划与验收指标？
• 整数规划：max z = 5x1 + 4x2，约束 2x1 + 3x2 ≤ 12，2x1 + x2 ≤ 7，x1, x2 ≥ 0 且取整。它的 LP 松弛最优解是 (x1, x2) = (2.25, 2.5)，z = 21.25。请回答：(1) 你会对哪个变量分支，两个子问题分别是什么，各自 LP 上界大概是多少；(2) 如果某个子问题的 LP 松弛最优解恰好是整数解，是不是就可以直接把它从待探索列表里删掉，为什么；(3) 搜索过程中的“当前下界”是怎么来的、什么时候更新它。
• 你用列生成求解一个集合覆盖型主问题（最小化总成本）。当前 RMP 的对偶解为 π = (3, 2, 5)（对应 3 个需求）。子问题返回一条覆盖需求 2 和 3、成本为 6 的列。请回答：(a) 这条列的 reduced cost 是多少？该不该加入 RMP？(b) 列生成收敛后 RMP 的 LP 最优值是 100，四舍五入得到的整数可行解是 115，这个 gap 你打算怎么处理？(c) 如果子问题改用启发式搜索而不是精确最短路，对 (b) 中的下界和剪枝会有什么影响？