关于BPC问题的求法

Question

在求解整数规划问题时候，往往采用branch ＆ cut & price的方法。如果期间要实现列生成和cutting plane的结合，那么我们常规的操作流程是先完成列生成操作后再加入cut吗？还是可以一边列生成一边加cut呢？

如果是采用第二种思路，那么我们每次加入新列后都会导致决策变量的结果发生变化，则先前一些有效的cut将变得无效，如果此时我们不删除这些无效cut，而是保留其直接计算，是否反而会让我们求解整数解的过程变得更困难呢？

Answer 1

参考免费微信小程序：皆我百晓生 作答，经由专家-皆知整理回复，如问题解决，望采纳；如仍有疑问，请评论回复。

在解决整数规划问题时，特别是通过Branch and Cut & Price（分支与切割与定价）方法，确实存在两种主要策略来结合列生成（Price）和切割平面（Cut）：先进行完整的列生成再添加切割平面，以及同时进行列生成和切割平面的插入。

同时进行列生成与切割平面

理想情况下，最高效的实施方式是同时进行列生成和切割平面的添加。这种方法利用了每一步中模型的最新信息，这可能意味着在找到并加入新列的同时，也根据当前的解空间探索来添加新的切割平面。这样做的好处是可以更快地收紧解空间，减少不必要的探索，理论上可以加速求解过程。

处理无效Cut的问题

确实，每当引入新列时，某些先前有效的切割平面可能变得不再有效，因为解空间发生了变化。关键在于维护一个动态的切割集合。对于无效的cut，不需要立即删除它们，但应当评估它们对当前问题状态的适用性。实际上，一些表面上无效的cut在后续的分支中可能会重新变得有效。因此，一种策略是标记这些cut为暂时不可用，而不是永久移除，同时确保在每次迭代中都检查cut的有效性。

实现框架简述

由于直接提供完整的C#代码实现较为复杂且篇幅长，下面简要描述实现的关键步骤和伪代码概念，你可以基于此构建具体实现。

1. 初始化模型：建立基本的线性规划松弛模型。
2. 列生成循环：
   • 解决松弛问题：求解当前模型，得到松弛解。
   • 价格问题：基于松弛解，解决辅助问题以发现新列（变量）。
   • 添加新列：如果有新列被发现，将其加入模型。
   • 切割平面生成：检查新解，生成并添加针对当前解空间的切割平面。
3. 切割平面管理：维护一个切割平面库，每次迭代时重新评估所有切割平面的有效性。
4. 分支过程：当满足分支条件时，选择一个变量进行分支，并重复上述过程。
5. 终止条件：当找到满足精度要求的整数解，或达到预设的迭代次数等条件时停止。

伪代码示例

function BranchAndCutAndPrice():
    InitializeModel()
    while not TerminationCondition():
        SolveRelaxedProblem()
        newColumns = PriceProcedure(Solution)
        foreach column in newColumns:
            AddColumnToModel(column)
        
        cuttingPlanes = GenerateCuttingPlanes(Solution)
        foreach plane in cuttingPlanes:
            AddCutToModel(plane)
        
        // 简化的分支逻辑
        if BranchingCondition():
            BranchAndRepeatProcess()
    return BestIntegerSolutionFound()

请注意，实际应用中，列生成和切割平面的具体算法会非常复杂，涉及到高级优化技巧，如延迟加载列、强分支选择等。此外，C#实现时会依赖于特定的数学编程库，如Gurobi、CPLEX等，这些库提供了接口来执行这些操作。具体代码实现会涉及这些库的调用细节，因此建议查阅相关库的官方文档来获取详细的编程指导。