在集合覆盖形式的列生成里，RMP（受限主问题）当前 LP 最优解给出的行对偶价格是 y = (5, 0, 4)，分别对应需求 1、2、3。现在候选池里有一列还没进 RMP，它覆盖需求 {1,3}，成本是 6。(1) 这一列的 reduced cost 是多少，会进基吗？(2) 如果这列的成本是 9 呢？(3) 定价子问题一般是在解什么？列生成跑收敛之后你拿到的是什么问题的解，接下来还必须做什么？

面试官在考什么

是否理解列生成靠对偶价格评判“还没生成的列”，以及它只保证 LP 松弛最优、必须再接整数化这一步。

列生成

回答框架 · 前两步

1. reduced cost = c_S − Σ(i∈S) y_i = 6 − (5 + 4) = −3 < 0，说明这一列能改进当前 RMP 目标，应加入；成本为 9 时 reduced cost = 0，不改进当前目标（对应 y 已是该 RMP 的最优对偶解）。
2. 列覆盖多个需求，比较时必须把该列覆盖的所有行的对偶价格相加，而不是和某一行的价格比。

同一能力域的其他题

• 你说做过排产调度，用了遗传算法/模拟退火。请说明你的编码方式（染色体/状态表示）是什么？适应度函数里有没有加惩罚项？为什么？
• 你要实现一个最小化 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) 中的下界和剪枝会有什么影响？