编者按：
本文将详细介绍列生成算法，一种处理大规模线性规划问题的常用算法，特别适用于NP-hard问题的启发式算法设计。我们将以一维下料问题为模型，通过Python调用Gurobi求解器，展示列生成算法的入门教程。
【编码】系列文章为『运筹OR帷幄』最新推出的版块之一，主要聚焦于经典算法的代码实现及案例可视化，或最新paper算法复现。目的是为了理论联系实际，以代码为基础让算法理论能够落地。
前言：
列生成方法（Column Generation，CG）是一种解决大型线性规划问题的有效方法。对于初学者来说，从D-W分解（Dantzig-Wolfe decomposition）开始可能会让人感到困惑。我们将从一个新的角度来简单描述列生成方法的一个初步使用。我们将以旅行商问题（Travelling salesman problem，TSP）、车辆路径问题（Vehicle Routing Problem，VRP）、车间调度问题（Scheng）等一系列组合优化问题的下界（lower bound）求解方向为例进行说明。
优化对象：一维下料问题
一维下料问题的一般描述是：钢材厂（或其他材料厂）有一批长度已知的钢管，需要按照顾客订单进行切割。每个顾客都需要一定长度的钢管，目标是怎样切割钢管使得既能满足客户需求，又使得消耗的材料最少。
我们先确定决策变量：表示是否写切割钢管i，既然是整数规划，取值只能是整数。为了确保最小浪费，我们需要添加变量表示在钢管i上切割多少次来满足客户j的需求。
在此，我们通过一个具体的例子来详细解释列生成算法的步骤和实现。我们给出一个简单的初始模型和其限制条件，然后逐步解释如何通过列生成算法求解该问题。我们将逐步展示如何从初始的可行解开始，通过求解主规划和子问题，逐步逼近最优解。
主规划和子问题的求解将通过Python调用Gurobi求解器进行。我们也会解释如何从模型中获取乘子，并如何使用这些乘子来求解子问题以找到新的可行列。
在介绍完列生成算法的基本步骤后，我们将简要提及列生成算法在科学研究中与动态规划、分支定界等算法的结合使用，如分支定价算法（branch and price）。我们将指出，虽然列生成算法在理论上可以与这些算法结合使用，但本文将主要关注其基本思想和初始入门步骤。
我们将提到列生成算法在求解最优解时的价值，特别是在对智能算法如遗传算法、模拟退火等提供优良的下界估计。我们将简要介绍整数规划的精确算法与近似算法的区别与关联，并提供相关学习资源供读者深入学习。
本文的目的是为了让读者对列生成算法有一个初步的了解和掌握，为进一步深入研究打下基础。如有任何问题或建议，欢迎审稿人及各位读者赐教。
审稿人介绍：
PhilFWu，俄亥俄州立大筹学博士，现为LLamasoft的应用科学家。专注于研究并编写路径优化问题和供应链网络优化问题的求解器。在运筹学领域有深厚的学术背景和丰富的实践经验。
吐服，大连海事大学物流实验室研究生，研究方向包括港口仿真、航线优化等。对物流工程与管理有浓厚的兴趣。
浊清风，教授（大连海事大学物流系教授、博士生导师），从事交通物流网络优化、计算机仿真等研究。在国内外享有较高的学术声誉，曾多次获得重要奖项。