Colossus

什么是 Colossus

Colossus 是一个高性能、可针对特定问题定制和拓展的列生成求解框架，用于求解大规模（混合）整数线性规划问题。

本框架提供列生成算法中与具体问题无关的部分：限制主问题的迭代求解、定价子问题的调度、列池管理、迭代终止条件判断、求解结果的记录与输出。与具体问题相关的部分由用户通过 ToolBox 提供。

框架追求：

1. 算法清晰化、数据结构透明化。
2. 便捷的外部接口，保证算法的可拓展性。

目前，Colossus 框架的主体模块已经测试完毕，子模块还在开发测试中，暂未开源~~ 这篇文档的主要目的是记录开发进展，对相关的接口进行说明，避免时间长了我自己都看不懂自不己写了啥，哈哈哈…

重要说明：当前版本求解器已从 Gurobi 切换到 COPT（Cardinal Optimizer），Engine 内部使用 coptpy 库与求解器交互。

框架结构：

Colossus/
├── engine.py
├── utils.py
├── __init__.py
├── dualfinder.py
├── raggedlst.py
├── common_exact_method/
├── common_heuristic_method/
├── common_pool_management/
└── examples/

这个框架算是对我第一年研究生生涯方法论层面的总结，当然还有很多待完善的地方。希望我可以在毕业之前把这个框架完善好，下一步打算融合一些机器学习的东西进去。

就这样，over~~

如果你也在做列生成、分支定价、或者大规模整数规划，欢迎一起交流。这个框架虽然还远称不上成熟，但至少让我的代码不再是一锅粥了。也欢迎催更——说不定你催一催，我就更有动力把坑填完了 😄。

项目名：Colossus，对，就是那个“巨像”，希望它有一天真的能成为巨像吧~~

API 接口

Colossus.ToolBox

ToolBox 是自定义工具箱，为 Engine 提供必要的可调用对象。列生成算法与具体问题相关的部分实际只有五件事：

1. 如何构造初始列？
2. 限制主问题是如何定义的？
3. 定价子问题怎么求解？
4. 如果想把生成的列写入文件，格式是什么？
5. 如何管理列池？

这五件事需要根据具体问题自行定义，框架无法代劳。框架能做的是让你更快捷、更有逻辑、更规范地完成它们：

1. 如何构造初始列？通过 addTool 添加 name='generateInitialCols' 的可调用对象。必须定义。
2. 限制主问题是如何定义的？通过 addTool 添加 name='buildRestrictedMP' 的可调用对象。必须定义。
3. 定价子问题怎么求解？通过 addTool 添加 name='updateAndSolveSP_Exact' 或 name='updateAndSolveSP_Heuristic' 的可调用对象。必须定义至少一个。
4. 如果想把生成的列写入文件，格式是什么？通过 addTool 添加 name='coefficients_formatter' 的可调用对象。可以空着不定义，如果你不需要把列写入文件的话。
5. 如何管理列池？通过 addTool 添加 name='modifyColumnPool' 的可调用对象。可以空着不定义，如果你没有什么特殊的列池管理策略的话。

addTool(name, tool, *args, **kwargs)

把可调用对象 tool 以名称 name 注册到工具箱中。*args 和 **kwargs 用于预先固定该可调用对象模板规定以外的其它参数。

构建工具箱
toolbox = ToolBox()
toolbox.addTool('generateInitialCols', generateInitialCols)
toolbox.addTool('buildRestrictedMP', buildRestrictedMP)
toolbox.addTool('updateAndSolveSP_Exact', updateAndSolveSP_Exact)
toolbox.addTool('updateAndSolveSP_Heuristic', updateAndSolveSP_Heuristic)
toolbox.addTool('coefficients_formatter', coefficients_formatter)
toolbox.addTool('modifyColumnPool', modifyColumnPool)

问题结构是灵活的，但代码规则是写死的，所以定义上述方法时必须遵循格式规范，否则 Engine 读不懂。

原则上讲，这些可调用对象的参数必须与模板保持一致，这些参数将由 Engine 在求解时自动传入。但为了灵活性起见，你也可以定义模板规定以外的其它参数，对于这类参数，必须在使用 addTool 时通过 *args、**kwargs 提前把它们固定住。

generateInitialCols()

生成限制主问题的初始列。

generateInitialCols模板
def generateInitialCols():
    1. 创建ColumPool列池对象
    2. 构造Column列对象加入到ColumnPool中形成初始列池
    3. 返回ColumnPool列池对象

buildRestrictedMP(columnpool)

构造限制主问题的数学模型。

buildRestrictedMP模板
def buildRestrictedMP(columnpool):
    1. 根据输入的columnpool列池对象中包含的初始列column对象，构造COPT求解器的Model对象
    2. 返回COPT求解器的Model类对象

updateAndSolveSP_Exact(y, fingerprint, omega_next_col)

精确求解单个定价子问题。返回改善列 Column 对象构成的 list。

updateAndSolveSP_Exact模板
def updateAndSolveSP_Exact(y,fingerprint,omega_next_col):
    1. 创建一个用于存放改善列对象的列表improve_column_lst
    2. 根据限制主问题的对偶值列表y和子问题表示fingerprint构造子问题并使用精确解算法求解
    3. 根据reducedcost判断是否存在改善列
        1. 构造改善列Column对象，其中改善列在列池columnpool对象中的方案编码omega应该是omega_next_col
        2. 将得到的Column对象加入improve_column_lst中
    4. 返回improve_column_lst

updateAndSolveSP_Heuristic(y, fingerprint, omega_next_col)

启发式求解单个定价子问题。返回改善列 Column 对象构成的 list。

updateAndSolveSP_Heuristic模板
def updateAndSolveSP_Heuristic(y,fingerprint,omega_next_col):
    1. 创建一个用于存放改善列对象的列表improve_column_lst
    2. 根据限制主问题的对偶值列表y和子问题表示fingerprint构造子问题并使用（元）启发式算法求解
    3. 根据reducedcost判断是否存在改善列
        1. 构造改善列Column对象，其中改善列在列池columnpool对象中的方案编码omega应该是omega_next_col
        2. 将得到的Column对象加入improve_column_lst中
    4. 返回improve_column_lst

coefficients_formatter(coefficients)

把 Column 对象的 coefficients 属性转换为格式化的字符串，使写入 .col 文件后具备可读性。

coefficients_formatter模板
def coefficients_formatter(coefficients):
    1. 传进来的是Column对象的coefficents属性，定义它格式化后的字符串
    2. 返回格式化后的字符串

modifyColumnPool(current_iter, columnpool)

在列生成迭代过程中对列池进行自定义的增删操作。

modifyColumnPool模板
def modifyColumnPool(current_iter,columnpool):
    1. 第一个参数是列生成当前的轮次,第二个参数是Columnpool列池对象
    2. 通过ColumnPool对象的增删操作对列池就地进行修改

Colossus.Environment

Environment 是一个 dataclass 数据类，用于管理求解引擎 Engine 的行为参数。

Environment(variables_name, relaxed_variables_name, relaxed_variables_type, fingerprint_lst, barrier_method_on=True, exact_solve_on=True, heuristic_solve_on=True, sps_parallel_on=False, process_num=None, process_initializer=None, process_initargs=None, mini_batch_percent=1.0, lp_file_ouput_on=True, ilp_file_output_on=True, col_file_output_on=True, result_file_output_on=False, dual_alpha=0, truncate_threshold=1e-3, max_not_bertter=inf, max_time_limit=3600.0, rmp_log_to_console=False, current_reduced_cost_on=False, in_rmp_optimal_basis_when_on=False)

构造求解环境配置。

参数：

• variables_name (list) – 限制主问题决策变量（新列对应变量）的 name 属性。
• relaxed_variables_name (list) – 用于指定限制主问题是通过线性松弛主问题中的哪些变量得到的，第一个字符串对应的变量将被当作需要生成的变量（列）。Engine 将在最后阶段把这些变量恢复为 relaxed_variables_type 中对应的类型。建议这些字符串的首字母不同，可避免 startswith 方法失效。
• relaxed_variables_type (list) – 字符串（'INTEGER' 或 'BINARY'）列表，用于指定限制主问题中被松弛掉的变量原本的类型。
• fingerprint_lst (list) – 元组的列表，存放所有子问题的唯一标识 fingerprint。
• barrier_method_on (bool) – 设定限制主问题是否使用内点法求解。推荐使用默认值开启内点求解，内点法得到的对偶变量一般好于单纯形法得到的。
• exact_solve_on (bool) – 设定是否用精确解算法求解定价子问题。如果同时设置了 heuristic_solve_on=True，则精确解算法将在最后被调用兜底。
• heuristic_solve_on (bool) – 设定是否使用启发式算法求解定价子问题。
• sps_parallel_on (bool) – 设定子问题是否使用并行求解模型，默认关闭。开启后将忽略 mini_batch_percent 参数（mini_batch 策略只能在子问题串行求解的情形下使用）。
• process_num (int) – 可选。设定子问题并行求解时开启的进程数，默认为 None，此时将根据机器 CPU 核心数自动确定进程数。
• process_initializer (callable) – 当 sps_parallel_on=True 时必须设置。用于在子进程中为存放全局变量的模块初始化全局变量，该函数只在创建进程池时被调用一次。
• process_initargs (tuple) – 当 sps_parallel_on=True 时必须设置。将作为参数自动解包传递给 process_initializer。
• mini_batch_percent (float) – 设定列生成每轮迭代求解多少个能产生改善列的子问题后就终止。例如有 10 个子问题，设定 mini_batch_percent=0.2，如果第 1 个子问题可以产生改善列，第 2 个不能，第 3 个能，就求解到第 3 个子问题不再继续，记录断点为第 4 个子问题，下一轮迭代从子问题 4 开始。如果只有一个子问题，设置这个参数没有意义。
• lp_file_ouput_on (bool) – 设定是否输出限制主问题的模型文件。
• ilp_file_output_on (bool) – 设定是否输出模型的不可行性文件。
• col_file_output_on (bool) – 设定是否将经由 updateAndSolveSP_Exact 或 updateAndSolveSP_Heuristic 生成的 Column 对象写入 .col 后缀的列文件。
• result_file_output_on (bool) – 设定是否将模型的求解结果写入 .result 后缀的文件。
• dual_alpha (float) – 设定对偶平滑的系数，本轮次 ，默认设置为 0 即不进行对偶平滑处理。注意 dual_alpha 在迭代过程中默认使用几何衰减策略，即 dual_alpha=0.87096359*dual_alpha，差不多列生成迭代 100 次 dual_alpha 就会从 1 衰减到 0。
• truncate_threshold (float) – 设定当限制主问题相邻两次最优值差的绝对值相差多大时认定没有发生改进。
• max_not_bertter (int) – 设定当限制主问题相邻两次最优值连续 max_not_bertter 次没有发生改进就终止迭代。
• max_time_limit (float) – 设定求解多长时间后，如果限制主问题还没有收敛就强制停止迭代。
• rmp_log_to_console (bool) – 设定是否展示求解器求解限制主问题的过程。
• current_reduced_cost_on (bool) – 设定是否记录变量在当前轮次限制主问题求解后的检验数。
• in_rmp_optimal_basis_when_on (bool) – 设定是否记录列在列生成的哪些迭代轮次进入了限制主问题的最优基。

除了 variables_name、relaxed_variables_name、relaxed_variables_type、fingerprint_lst 四个参数是必须设置的，其它参数都是可选的。如果你不理解这些参数的设置，请使用默认配置。

设置求解环境
environment = Environment('labda',['labda'],['INTEGER'],[(1,)]) 

以上设置的意思是：主问题对应变量名叫 labda，被松弛的变量名叫做 labda，松弛之前它是求解器的整数类型，而子问题只有一个，它的 fingerprint 是 (1,)。其余环境参数使用默认配置。

Colossus.Column

在列生成中，一个列包含的信息由以下几部分构成：

1. 这个列在方案集合中对应的索引？
2. 这个列在目标函数中的系数？
3. 这个列在约束中对应的系数？

Column 类用来存储这些信息，并且还提供了其它一些属性用于列池的管理。

Column()

构造一个列对象，各属性如下：

• omega (int) – 这个列在限制主问题中对应的索引，必须设置。对应信息1
• reduced_cost (float | int) – 这个列对应的 reduced cost。如果是初始列，即不是通过定价子问题产生的，请将这个属性设置为 None。
• dummy_reduced_cost (float | int) – 虚拟的 reduced cost，默认 None。
• current_reduced_cost (float | int) – 列生成当前迭代轮次下这个列对应的检验数，随迭代自动更新。默认不记录，只有在 environment.current_reduced_cost_on=True 时才记录。
• tau (float | int) – 这个列在限制主问题目标函数中的系数，必须设置。对应信息2
• coefficients (list) – 这个列在限制主问题约束中对应的系数，必须设置。对应信息3
• in_rmp_optimal_basis_when (list) – 存储当前这个列在列生成的哪些轮次进入了限制主问题的最优基。默认不记录，只有在 environment.in_rmp_optimal_basis_when_on=True 时才记录。
• service_target (不可变对象) – 这个列对应的服务对象是谁，设定值需要是一个不可变对象（比如整数值或元组）。可选，仅在需要对方案集分组时设置。

一般来说，创建 Column 对象时至少要把信息 1、2、3 对应的参数设置好，其它参数设不设置取决于你自己的需求：

Column对象构造
column = Column()
column.omega = ...
column.tau = ...
column.coefficients = [...]

Colossus.ColumnPool

ColumnPool 用于管理列对象 Column，继承自 dict，支持使用 [omega] 直接查询 omega 对应的 Column 对象。

ColumnPool()

创建一个列池对象，各属性如下：

• omega_next_col (int) – 用于查询下一个添加进来的 Column 对象的 omega 应该设置为多少。它在列生成迭代的整个过程中单调不减，从而保证列的索引不会因为某些列的删除而发生错乱。
• col_num (int) – 用于查询当前列池中包含多少列。
• deleted_col_pool (dict) – 存储从当前列池中被删去的列。有的时候你可能误删了某些列，然后又想把这些列拿回去，可以从 deleted_col_pool 中找。
• groupby (dict) – 嵌套 dict 对象，可以快速查询列池中所有取特定 service_target 值的 Column 对象构成的 dict，仅在创建 Column 对象时设置了 service_target 属性时才生效。
• **_changed** (bool) – 用于检测列池是否发生修改。一旦检测到列池状态变化，Engine 会自动对限制主问题模型做出相应的修改，然后重置状态。
• _memory_change (dict) – 用于记录发生的修改，值是 Column 对象的 omega 属性构成的列表。

1. ColumnPool 对方案集合的索引管理是单调不减的，所以建模的时候如果你确实需要对方案集做分组处理，请使用额外的 indicator parameter，具体操作参考：https://yuanshengshe.github.io/posts/4e8c5c2/，2026年9月21日，最新版本的Colossus已经支持方案集合分组了
2. ColumnPool 实施的是惰性更新的机制，通过 _changed 和 _memory_change 参数实现。这两个参数不建议你在外部做修改，除非你懂会有什么后果。
3. ColumnPool 的所有属性都只建议读取不建议修改，它们会随着 ColumnPool 提供的方法的调用而自动更新。

addCol(column)

原子级的添加新列。

delColByOmega(omega)

原子级的删除列。

addCols(column_lst)

批量添加新列。

delColByReducedCost(lb=-inf, ub=inf)

批量删除列，删除 reduced cost 落在 之外的列。

getOmega()

获取列池中所有列的 omega（键）构成的集合。

getOmegaGroupBy(service_target)

获取所有 service_target 取指定值的 Column 对象的 omega 属性构成的集合。

增加和删除列
def addCol(self,column):
    # 原子级的添加新列
    ...
def delColByOmega(self,omega):
    # 原子级的删除列
   ...
def addCols(self,column_lst):
    # 批量添加新列
    ...
def delColByReducedCost(self,lb=-float('inf'),ub=float('inf')):
    # 批量删除列
    ...
def _alreadyCommitChangeToRMP(self):
    # 如果已经将所有变更提交到了RMP中，则重置列池的状态为未修改，这个方法不需要提供给用户，在Engine内部使用，用户不准调用这个
    ...
def getOmega(self):
    # 获取列池中所有列的omega（键）构成的集合
    ...
def getOmegaGroupBy(self,service_target):
    # 获取所有service_target取指定值的Column对象的omega属性构成的集合
    ...

大部分时候你应该只会用到 addCol 方法，除非你有特定的列池管理需求。

Colossus.Engine

Engine 是列生成框架的接口。内部实现比较复杂，但只要把 Environment 对象和 ToolBox 对象构造好交给它，然后调用 runEngine 就可以跑起来。

Engine(name, environment, toolbox)

构造求解引擎。name 是引擎的名字，会作为相关文件输出的前缀。

runEngine()

运行列生成求解流程。

构造Engine引擎
engine = Engine('csp_engine',environment,toolbox) # 第一个参数是引擎的名字，会作为相关文件输出的前缀
engine.runEngine()

默认情况下，运行 Engine 之后控制台会打印配置信息与列生成迭代表格。迭代表格各列含义如下：

• iter – 列生成迭代当前的轮次
• time(s) – 从 Engine 启动到当前轮次的时长
• cols_num – 当前列的数量
• rmp_obj – RMP 最优值
• no_better – 连续未改进次数
• rmp_time(s) – 当前轮次中限制主问题的求解时长
• sps_method – 当前轮次中子问题求解使用的定价方式
• sps_time(s) – 当前轮次子问题的求解时长

控制台输出示例
>>Engine配置信息
[1] Environment(variables_name='lam', relaxed_variables_name=['lam', 'u'], relaxed_variables_type=['BINARY', 'BINARY'], fingerprint_lst=[(1,), (2,), (3,), (4,)], barrier_method_on=True, exact_solve_on=True, heuristic_solve_on=False, sps_parallel_on=False, process_num=None, process_initializer=None, process_initargs=..., mini_batch_percent=1.0, lp_file_ouput_on=False, ilp_file_output_on=False, col_file_output_on=False, result_file_output_on=True, dual_alpha=0, truncate_threshold=0.001, max_not_bertter=inf, max_time_limit=3600.0, rmp_log_to_console=False, current_reduced_cost_on=False, in_rmp_optimal_basis_when_on=False)
[2] ToolBox contains tools: buildRestrictedMP, generateInitialCols, updateAndSolveSP_Exact
>>Note:在调用runEngine前请先检查配置是否满足你的要求

>>预备：初始列构造完毕
Cardinal Optimizer v8.0.6. Build date Aug  7 2026
Copyright Cardinal Operations 2026. All Rights Reserved

>>限制主问题数学模型构造完毕，进入列生成迭代轮次

>>列生成迭代过程：
+-----+---------+---------+--------------+----------+------------+------------+------------+
|iter |time(s)  |cols_num |rmp_obj       |no_better |rmp_time(s) |sps_method  |sps_time(s) |
+-----+---------+---------+--------------+----------+------------+------------+------------+
|1    |0.01     |0        |4,000.00      |0         |0.00        |exact       |0.00        |
|2    |0.01     |4        |3,000.00      |0         |0.00        |exact       |0.00        |
|3    |0.02     |8        |2,000.00      |0         |0.00        |exact       |0.00        |
|4    |0.03     |12       |2,000.00      |1         |0.00        |exact       |0.00        |
|5    |0.04     |16       |2,000.00      |2         |0.00        |exact       |0.00        |
|6    |0.05     |19       |1,006.00      |0         |0.00        |exact       |0.00        |
|7    |0.06     |22       |1,006.00      |1         |0.00        |exact       |0.00        |
|8    |0.07     |25       |1,006.00      |2         |0.00        |exact       |0.00        |
|9    |0.08     |29       |1,006.00      |3         |0.00        |exact       |0.00        |
|10   |0.09     |33       |509.00        |0         |0.00        |exact       |0.00        |
|11   |0.09     |37       |14.00         |0         |0.00        |exact       |0.00        |
|12   |0.11     |40       |12.00         |0         |0.01        |exact       |0.00        |
|13   |0.12     |42       |12.00         |1         |0.01        |exact       |0.00        |
+-----+---------+---------+--------------+----------+------------+------------+------------+
>>列生成迭代终止原因：无法再找到改善列
>>列生成迭代轮次终止，下面将根据现有ColumnPool对主问题进行求解：

Setting parameter 'Logging' to 1
Setting parameter 'LpMethod' to -1
Model fingerprint: 5ced3ba1

Using Cardinal Optimizer v8.0.6 on Windows (25H2 Build 26200 - x86_64)
The CPU model is 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
Hardware has 4 physical cores and 8 logical cores. Using instruction set X86_AVX512_E1 (14)
Minimizing a MIP problem

The original problem has:
    277 rows, 46 columns and 572 non-zero elements
    46 binaries

Starting the MIP solver with 8 threads and 32 tasks

Best solution   : 12.000000000
Best bound      : 12.000000000
Best gap        : 0.0000%
Solve time      : 0.01
Solve node      : 1
MIP status      : solved
Solution status : integer optimal (relative gap limit 0.0001)
>>已经将Engine=VSP_BAP_engine的求解结果写入VSP_BAP_engine.result文件中

Colossus.Result

第一次写列生成算法的时候没有经验，写完想要获取求解结果以及迭代过程中的相关数据非常麻烦。

所以针对 Colossus 框架的设计，专门提供了一个 dataclass 数据类 Result 来存放求解结果以及迭代过程中的相关数据。

Result()

不需要自行创建，在 Engine 运行完成后访问 engine.result 属性即可。

• history_incumbent (list) – 存储限制主问题历史每个轮次最优目标函数值
• history_col_num (list) – 存储限制主问题历史每个轮次列的数量
• history_rmp_time (list) – 存储限制主问题历史每个轮次的求解时长
• history_sps_time (list) – 存储历史每个轮次求解一组子问题的用时
• history_optimal_basis_col_omega (list) – 嵌套 list 对象，存储历史每个轮次那些在限制主问题最优基中的 Column 对象对应的 omega 属性
• best_objective (float) – 求解主问题的最优值
• total_time (float) – 总求解时长
• master_problem_time (float) – 最后求解主问题的时长

Colossus.common_exact_method

针对子问题的常见形式提供一些精确求解算法，目前包含的算法较少，还在开发测试当中…

资源限制最短路（rcssp）

label_setting_method(adjacency_lst, s_node, t_node, resource_ub)

求解带资源约束的最短路问题（RCSPP），返回最优目标值 best_obj 与最优路径 best_path。

label_setting_method
def label_setting_method(adjacency_lst,s_node,t_node,resource_ub):
    # Args:
    #     adjacency_lst：邻接表，默认顶点node值0,1,2,...,len(adjacency_lst)-1。[[(1,1,2),(2,2,2)],[],[]]这个图有3个node分别是0,1,2。只有两条弧分别从0到1,0到2。cost分别是1和2，资源消耗都是2
    #     s_node：起点对应node值
    #     t_ndoe：重点对应node值
    #     resource_ub：资源上限值
    # Returns:
    #     best_obj：最优目标值
    #     best_path：最优目标值对应路径，满足资源限制约束！

参考论文 Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation 复现的求解 RCSPP 问题的单向标签算法。仅适用于弧成本和资源消耗非负的图。

时间拓展网络（tenetwork）

提供时间拓展网络的构造数据结构，方便用户在求解定价子问题时搭建网络。

• Node – 节点对象，属性包括 nid（节点唯一编号）、group（节点归属集合标识）、pos（位置信息）、time（时刻信息）。
• NodeGroup – 节点分组管理对象，继承自 dict，提供 addNode 方法。可以按 group 获取节点，也可以判断指定 group 中是否存在指定 pos 和 time 取值的节点。
• Arc – 弧对象，属性包括 aid（弧唯一编号）、group（弧归属集合标识）、cost（弧成本）、start_node（弧起点）、end_node（弧终点）。
• TENetwork – 时间拓展网络对象，管理节点集合和弧集合。属性包括 node_lst（节点列表）、arc_lst（弧列表）、ns_nid（源点编号）、nt_nid（汇点编号）、adjacency_lst（邻接表，存的是弧对象引用，修改弧的 cost 属性即可自动更新邻接表）。

TENetwork构造
net = TENetwork(node_lst, arc_lst, ns_nid, nt_nid)

最短路（spp）

提供无资源约束的最短路求解算法。

• floyd_method(adjacency_lst, s_node=None, t_node=None) – Floyd 算法，求解任意两点（或指定起终点）之间的最短路。
• topological_sorting_method(adjacency_lst, topological_N, s_node, t_node) – 在 DAG（有向无环图）上通过拓扑排序求解最短路，适用于时间拓展网络这种天然无环的图，比通用最短路算法更快。
• get_topological_sort_from_adj(adjacency_lst) – 根据邻接表求图的拓扑排序，作为 topological_sorting_method 的输入。

背包问题（kp）

提供常见背包问题的精确求解算法（基于动态规划）。

• knapsack_01_method(price_array, weight_array, capacity, cache=False, parallel=False) – 0-1 背包问题，每个物品只能选一次。
• knapsack_unbounded_method(price_array, weight_array, capacity) – 完全背包问题，每个物品可选无限次。
• knapsack_bounded_method(price_array, weight_array, num_array, capacity, cache=False, parallel=False) – 多重背包问题，每个物品有数量上限。

分配问题（ap）

• hungarian_method(cost_array) – 匈牙利算法，求解指派问题的精确最优解。

Colossus.common_heuristic_method

提供一些常用的子问题启发式求解算法，目前包含的算法较少，还在开发测试当中…

jaya(objfunc, population, maxiter=50, minimization=True, *args, **kwargs)

返回最优目标值 best_obj。

jaya
def jaya(objfunc,population,maxiter=50,minimization=True,*args,**kwargs):
    # Args:
    #     objfunc：一个可调用对象，第一个参数必须是sol（一维ndarray数组），用于接受个体编码计算目标函数值，
    #              objfunc的其他参数通过*args,**kwargs固定，返回值必须是一个浮点数
    #     population：初始种群，一个二维ndarray数组
    #     maxiter：最大迭代次数
    #     minimization：bool对象，表示当前是最小化问题还是最大化问题
    # Returns:
    #     best_obj：最优目标值

Jaya 算法是一种不含超参数的元启发式算法，适用于无约束连续优化问题。基本思想是维护一个种群，将每个个体向种群最优个体的方向拉、往最坏个体的反方向拉，随机性体现在拉的力度上。优点是无需调超参数，缺点是容易陷入局部最优，全局搜索能力不强。

*args 和 **kwargs 的存在是考虑到在列生成算法中子问题的 objfunc 会不断发生变化。可以把 objfunc 看成一个模板函数，在定义 updateAndSolveSP_Heuristic 时先在其外部定义一个 objfunc，通过固定参数方式得到特定的 objfunc，进而避免反复创建函数的开销。

Colossus.common_pool_management

提供一些常见的列池管理（列增删）策略，目前包含的算法较少，还在开发测试当中…

ageBasedRetention(current_iter, columnpool, scale, start_threshold=0)

对列池就地进行删除操作，只保留年龄落在 [current_iter-scale, current_iter] 的列。

ageBasedRetention
def ageBasedRetention(current_iter,columnpool,scale,start_threshold=0):
    # Args:
    #     current_iter：当前迭代轮次
    #     columnpool：列池对象
    #     scale：年龄阈值，越小保留的列越少，越大保留的列越多
    #     start_threshold：启动阈值，当列池中列的数量高于该值时才会启动策略

参考论文 Accelerating Column Generation in Highly Degenerate Integer Programming Problems with Template Pricing 实现的基于年龄的列删除策略。对每一列记录一个”年龄”：如果该列曾进入最优 RMP 基，则年龄 = 最近一次进入基的迭代；如果从未进入基，则年龄 = 它被加入 RMP 的迭代。在 current_iter 轮次结束时，只保留年龄落在 [current_iter-scale, current_iter] 的列。

start_threshold 的设计是合理的：当列池特别小的时候没必要删列，反而浪费时间。关于 scale 和 start_threshold 参数怎么设置，可以学习上面那篇文章的做法，做二维的网格搜索画热力图。实验结果表明 start_threshold 对求解时间的影响不是很大，然后进一步针对 scale 取值画折线图选择合适的值。

重大更新

方案集分组功能

新增方案集合分组的功能，开始觉得不必要，在复现 Integrated vessel traffic scheduling and berth allocation with restricted channel widths 这篇文章的时候发现这个功能是非常有必要存在的。为什么？

假设你的子问题是按船舶 进行分解的，子问题是为了生成船舶服务方案，当然我们可以引入比方说 indicator parameter 表示方案 是不是服务的船舶 ，但如果我确实需要知道方案服务的是哪条船就得做求和运算 （这个事情是很常见的，如果说 master problem 中又存在参数使用下标 ）。这个表达起来是很繁琐的。

如果你提前把方案集分好了组，比方说按船舶分组，那我方案集就会写成 ，这里面的方案就全是针对船舶 的，我的选择变量就会定义成 ，表示我是否选择服务船舶 的方案 。就不存在做求和运算找方案具体服务的是哪条船的问题。

如何在 Colossus 中实现方案分组？

1. 只需要创建 Column 对象的时候设置 service_target 属性就可以了
2. 后续可通过 ColumnPool 对象的 groupby 属性获取指定 service_target 取值的 Column 对象构成的字典
3. 可使用 getOmegaGroupBy 方法获取指定 service_target 取值的 Column 对象的 omega 属性构成的集合

子问题并行求解

2026年9月30日初步实现了 Colossus 框架子问题并行求解的功能，开多个进程跑子问题。一般情况下还是不建议开启并行求解模型，除非你的子问题数量很多且单个子问题求解时间与进程创建开销相比要长的多。

用法：

1. 设置 environment 的 sps_parallel_on 参数为 True
2. 设置 environment 的 process_initializer 参数，这是一个可调用对象，用于初始化存放全局变量的那个模块中的全局变量
3. 设置 environment 的 process_initargs 参数，这是一个 tuple 对象，会被自动解包作为参数传递给 process_initializer
4. 创建 toolbox 的时候，求解方法 updateAndSolveSP_Heuristic 或 updateAndSolveSP_Exact 不建议固定额外参数（不然会导致并行计算非常慢），如果确实有额外数据参数需要使用，只能将这些参数设置为存放全局变量的那个模块中的全局变量，然后通过 模块名.全局变量名 使用。假设是模块 global_data.py，你想要 _global_dataloader 参数，就通过 global_data._global_dataloader 获取。这里有个坑：不要 from global_data import _global_dataloader，因为 _global_dataloader 是 global_data 模块的全局变量，你直接导入无法建立起关联，始终拿到手的是 _global_dataloader 初始化之前的值，即使你已经对 global_data 模块的全局变量做过更新了。因为在 python 里面 from global_data import _global_dataloader 不是“给模块属性起个别名”，而是导入那一刻把模块属性的值复制/绑定到当前模块的变量名上。之后两者就基本没关系了。

这里得解释一下为什么有 2、3、4 这样别扭的操作：

因为 Colossus 的并行化计算是基于 multiprocessing 多进程实现的，在子问题求解的时候 Engine 引擎会把用于子问题求解的方法以及数据 pickle 序列化给各个子进程，例如：

result_lst_of_improved_column_lst = processpool.starmap(
    self.toolbox.updateAndSolveSP_Heuristic,
    [(y,fingerprint,_omega_next_col) for fingerprint,_omega_next_col in\
    zip(self.environment.fingerprint_lst,range(omega_next_col,\
        omega_next_col+resevered*len(self.environment.fingerprint_lst),resevered))]
    )

注意：这段代码传给子进程的不是函数本身，而是函数的序列化结果。子进程会进一步做反序列化操作，导入函数所在的那个模块以及涉及到的所有相关模块。

这里的问题是如果 self.toolbox.updateAndSolveSP_Heuristic 是一个纯函数的话，这步 pickle 序列化会非常快，因为纯函数的序列化结果就是（函数所在模块，函数名）。但如果有数据，特别是你的数据还特别大的话，那这个序列化和反序列化会特别特别缓慢，因为 python 序列化数据的话是直接针对值做的。从而，如果 self.toolbox.updateAndSolveSP_Heuristic 是一个利用 toolbox.addTool 固定了参数的 partial 函数，那每一轮次列生成迭代都会有巨额的序列化和反序列化开销，最终导致并行超级超级慢…

所以引入了 4 的要求。构造子问题求解函数的时候，就不要使用 addTool 去固定除了 (y,fingerprint,omega_next_col) 之外的数据参数。这样子问题求解这块儿的序列化和反序列化时间长的问题就解决了。但很多时候，构造子问题求解函数确实需要额外的参数呀！对于子问题的求解函数所需的额外数据参数，我们需要把它们写成某一个模块儿（比如叫 global_data.py）的全局变量。然后在子问题求解函数内部需要用相关参数的时候使用 global_data.全局变量名 的方式获取就行了。

关于为什么有 2、3 的要求，这里就要回到 multiprocessing 的工作原理上了。

还是以上面那段代码为例，multiprocessing 会根据传入函数的序列化结果做反序列化操作，把函数所在的那个模块以及涉及到的所有相关模块全部重新导入一遍。这就存在问题了，即使我在主程序（位于主进程中）对 global_data.py 模块做了全局变量的初始化操作，例如调用 _initialize_module_global_vars，但它重新把 global_data.py 模块导入子进程后，子进程的 global_data.py 模块中的全局变量还会是未初始化状态！！！这就导致在子进程中 updateAndSolveSP_Heuristic 拿到手的全局变量还是 None 值。

global_data.py
_global_dataloader = None
_global_tenetworks = None

def _initialize_module_global_vars(dataloader,tenetworks):
    # 调用完这个方法后这个模块的全局变量将被初始化
    global _global_dataloader
    global _global_tenetworks
    _global_dataloader = dataloader
    _global_tenetworks = tenetworks

这就是要求 2、3 要解决的问题。Engine 在创建进程池的时候，会让子进程把 global_data.py 模块导入，然后调用 process_initializer(process_initargs) 初始化模块中的全局变量。

这里的原理是 multiprocessing 在创建进程池的时候会根据 process_initializer 序列化的结果 ('global_data.py','process_initializer') 反序列化知道要把模块 global_data.py 导入子进程，然后在子进程内部调用 process_initializer(process_initargs) 初始化当前子进程内部这个 global_data.py 模块的全局变量。虽然这里也涉及到对数据参数做序列化和反序列化操作，但由于在整个列生成的迭代过程中，创建进程池只发生一次，所以这个开销有时候也是可以接受的。

还有一个坑！

multiprocessing 创建进程池的时候会重新导入主模块，目的是为了把所有可能能够用上的模块全部导入到子进程中。这里就会存在一个问题，如果你的 runEngine 直接写在主模块的顶层就会导致递归导入。最简单的解决办法是主模块所有内容全部写到 if name == "main": 下面。不要担心子进程不知道哪些模块需要导入，multiprocessing 很聪明，会自动根据写入进程的函数的反序列化结果把所有涉及到的模块找到然后统统导入到子进程中的！！！