ODHCPLEX 求解器
ODHCPLEX 是基于 IBM ILOG CPLEX 引擎构建的启发式求解器（Heuristic Solver），专为加速混合整数规划（MIP）问题的求解而设计。与传统的精确求解方法不同，ODHCPLEX 侧重于在较短时间内找到高质量的可行解，而非证明最优性。它通过智能地探索解空间、应用多种启发式策略，能够在复杂的大规模 MIP 问题中快速找到接近最优的可行解。
ODHCPLEX 适用于以下场景：
- 在有限时间内需要获得高质量可行解的应用场景
- 大规模 MIP 问题中，精确求解器难以在合理时间内找到可行解
- 作为 CPLEX 精确求解的补充，提供初始可行解以加速分支定界过程
- 需要多次求解相似问题结构，通过启发式方法快速获取近似解
ODHCPLEX 的核心优势在于它能够利用 CPLEX 引擎的强大计算能力，同时采用针对性的启发式搜索策略，在求解质量与计算时间之间取得平衡。用户可以通过 GAMS 参数灵活控制启发式算法的行为，以适应不同问题的特性。
目录
- Introduction（介绍）
- Specifying Model Structure（指定模型结构）
- Heuristic Parameters（启发式参数）
- Parallel Execution（并行执行）
- Determinism（确定性）
- Detailed Description（详细描述）
一、Introduction（介绍）
ODHCPLEX（Optimization-Driven Heuristic for CPLEX）是 GAMS 集成的一款基于 CPLEX 引擎的启发式求解器，专门用于求解混合整数规划（MIP）问题。其名称中"OD"代表优化驱动（Optimization-Driven），"H"代表启发式（Heuristic），体现了该求解器的核心设计理念：以优化技术驱动启发式搜索过程。
ODHCPLEX 的主要特点包括：
- 快速求解：采用先进的启发式算法，能够在短时间内找到高质量可行解
- 可扩展性：适用于从中小规模到大规模的各种 MIP 问题
- 可配置性：提供丰富的参数选项，用户可根据问题特性灵活调整求解策略
- 集成性：与 GAMS 平台无缝集成，支持标准 MIP 模型定义
- 互补性：可作为 CPLEX 精确求解的初始解提供者，加速分支定界过程
ODHCPLEX 广泛应用于生产调度、物流优化、资源分配、投资组合优化等需要快速获得优质解的实际应用场景。
二、Specifying Model Structure（指定模型结构）
在使用 ODHCPLEX 求解器时，正确指定模型结构对于获得良好求解效果至关重要。ODHCPLEX 接受标准的 GAMS MIP 模型定义，包括目标函数、约束条件和变量声明。以下是在 GAMS 中使用 ODHCPLEX 求解器的基本步骤：
2.1 模型声明
在 GAMS 中，模型通过 MODEL 语句声明，并通过 SOLVE 语句调用 ODHCPLEX 求解器：
MODEL 模型名 /所有方程/;
SOLVE 模型名 USING MIP MINIMIZING 目标变量;
要使用 ODHCPLEX 求解器，需要在 SOLVE 语句中指定求解器选项：
OPTION MIP = ODHCPLEX;
SOLVE 模型名 USING MIP MINIMIZING 目标变量;
2.2 变量类型支持
ODHCPLEX 支持 GAMS 中的所有变量类型：
- 连续变量：可取任意实数值的变量
- 二元变量（Binary）：取值仅为 0 或 1 的变量
- 整数变量（Integer）：取整数值的变量
- 自由变量（Free）：无符号限制的连续变量
- 正变量（Positive）：下界为 0 的连续变量
- 负变量（Negative）：上界为 0 的连续变量
- 半连续变量（Semi-continuous）：取值在 0 或某个下界以上的变量
- 半整数变量（Semi-integer）：取值在 0 或某个下界以上的整数变量
2.3 方程类型
ODHCPLEX 支持线性方程和二次约束方程，包括等式约束和不等式约束。对于二次规划问题，目标函数可以包含二次项。
2.4 特殊有序集（SOS）
ODHCPLEX 支持特殊有序集（Special Ordered Sets）类型 1（SOS1）和类型 2（SOS2），这在需要处理分段线性函数或互斥选择问题时非常有用。
三、Heuristic Parameters（启发式参数）
ODHCPLEX 提供丰富的参数来控制启发式算法的行为。这些参数允许用户根据问题的具体特征调整求解策略，以在求解速度和解的质量之间找到最佳平衡点。下表列出了主要的启发式参数选项：
3.1 关键参数说明
| 参数名称 |
GAMS 参数名 |
默认值 |
取值范围 |
说明 |
| 启发式频率 |
H Freq |
0 |
0-1000000 |
控制启发式算法在分支定界树中的调用频率。值为 0 表示自动选择。正值表示每 N 个节点调用一次。 |
| 启发式策略 |
H Strategy |
3 |
0-3 |
选择使用的启发式策略类型。1=仅使用节点启发式，2=仅使用邻域搜索，3=同时使用两者。 |
| 启发式时间限制 |
H Time |
0 |
0-1e+75 |
启发式搜索的时间限制（秒）。值为 0 表示与总时间限制相同。 |
| 可行解提升 |
H Improve |
1 |
0-2 |
控制是否尝试改进已发现的可行解。0=不改进，1=标准改进，2=强改进。 |
| RINS 启发式 |
RINS |
0 |
0-1000000 |
松弛诱导邻域搜索（RINS）的频率。正值表示每 N 个节点触发一次 RINS。 |
| 解池大小 |
Pool Size |
0 |
0-1000000 |
保留的候选解数量。解池可用于存储搜索过程中找到的多个可行解。 |
| 局部分支 |
Local Branch |
0 |
0-100 |
局部分支（Local Branching）的搜索深度。值为 0 表示自动选择。 |
| 启发式节点数 |
H Nodes |
0 |
0-1000000 |
每次启发式调用允许处理的最大节点数。值为 0 表示自动选择。 |
| 截止时间限制 |
H Cutoff |
0 |
任意实数 |
目标函数截止值，启发式仅搜索目标值优于该截止值的解。值为 0 表示不使用截止限制。 |
| 线程数量 |
Threads |
0 |
0-1024 |
求解器使用的并行线程数。值为 0 表示自动选择。 |
3.2 参数设置示例
在 GAMS 中设置 ODHCPLEX 参数的示例：
OPTION MIP = ODHCPLEX;
ODHCPLEX.H_Freq = 5;
ODHCPLEX.H_Strategy = 3;
ODHCPLEX.H_Time = 60;
ODHCPLEX.RINS = 10;
ODHCPLEX.Threads = 4;
3.3 参数调优建议
- 快速找到可行解：设置 H_Freq 为较小值（如 1-5），增加启发式调用频率
- 提高解质量：设置 H_Improve = 2 并增加 RINS 频率
- 大规模问题：适当增加 H_Time 为总时间的 20-30%
- 多解需求：设置 Pool Size 为所需解的数量
- 控制并行度：根据 CPU 核心数设置 Threads 参数
四、Parallel Execution（并行执行）
ODHCPLEX 利用 CPLEX 引擎的并行计算能力，支持在多核处理器上并行执行启发式搜索过程。并行执行可以显著加速求解过程，特别是在处理大规模 MIP 问题时。
4.1 并行模式
ODHCPLEX 支持以下并行模式：
- 机会并行（Opportunistic Parallelism）：在可用线程上动态分配工作负载，线程数量可能动态变化。
- 确定性并行（Deterministic Parallelism）：在固定数量的线程上运行，保证多次运行结果可复现。
4.2 线程控制
通过 GAMS 的线程选项控制 ODHCPLEX 使用的线程数量：
OPTION THREADS = 4;
或者通过求解器参数直接设置：
ODHCPLEX.Threads = 4;
4.3 并行性能考虑
- 线程数量一般不超过物理核心数，过度并行可能导致性能下降
- 对于小规模问题，串行执行可能更快（Threads = 1）
- 对于大规模问题，建议使用 4-8 个线程以获得最佳加速比
- 在共享计算环境中，注意为其他进程保留资源
五、Determinism（确定性）
确定性（Determinism）是指在相同的输入条件下，多次求解同一问题总能得到完全相同的结果。ODHCPLEX 在默认情况下使用机会并行模式，这可能导致不同运行间结果略有差异。对于需要可复现结果的应用场景，应启用确定性模式。
5.1 启用确定性模式
通过设置以下参数启用确定性并行：
ODHCPLEX.ParallelMode = 1;
其中 ParallelMode 参数的取值：
- 0：自动（默认）- 由求解器自动选择并行模式
- 1：确定性并行 - 保证结果可复现
- 2：机会并行 - 追求最佳性能，不保证结果可复现
5.2 影响确定性的因素
以下因素可能影响求解结果的确定性：
- 线程数量的变化
- CPU 负载波动导致的执行顺序变化
- 内存分配顺序的差异
- 不同操作系统或硬件平台
5.3 确保完全可复现的推荐设置
OPTION THREADS = 4;
ODHCPLEX.ParallelMode = 1;
ODHCPLEX.Seed = 0;
注意：启用确定性模式可能会略微降低并行效率，但保证了结果的可复现性。
六、Detailed Description（详细描述）
本节提供 ODHCPLEX 求解器的详细技术描述，包括其内部工作机制、算法构成和高级配置选项。
6.1 求解器架构
ODHCPLEX 基于 CPLEX 引擎构建，其整体架构包含以下主要组件：
- 模型预处理：对输入模型进行简化、缩放、冗余约束检测和变量边界收紧等操作，减小问题规模。
- 根节点处理：在根节点上执行 LP 松弛求解、切割平面生成和启发式算法，寻找初始可行解。
- 分支定界搜索：通过分支定界树系统地探索解空间，结合启发式算法加速搜索过程。
- 启发式引擎：包括多种启发式策略，如邻域搜索、RINS、局部分支等，持续寻找和改进可行解。
- 后处理：对最终解进行可行性验证和必要时的小规模调整。
6.2 启发式算法详解
ODHCPLEX 集成了以下启发式算法：
- 邻域搜索（Neighborhood Search）：在当前最优解的邻域内搜索更优解，通过固定部分变量并求解缩减后的子问题来实现。
- RINS（Relaxation Induced Neighborhood Search）：将 LP 松弛解与当前可行解的整数约束信息结合，构建子问题进行求解。
- 局部分支（Local Branching）：在当前解附近添加局部分支约束，限制搜索空间以加速改进。
- 可行解启发式（Feasibility Heuristic）：专注于快速找到可行解，即使目标值可能不是最优的。
- 改进启发式（Improvement Heuristic）：对已找到的可行解进行局部搜索，尝试改进目标函数值。
6.3 求解选项参考
| 选项 |
GAMS 参数 |
类型 |
默认值 |
说明 |
| 时间限制 |
ResLim / TimeLim |
实数（秒） |
1e+75 |
求解过程的最大运行时间 |
| 最优性容差 |
OptCA / OptCR |
实数 |
0/0.1 |
绝对/相对最优性差距容差 |
| 可行性容差 |
F Eas |
实数 |
1e-06 |
约束违反的允许范围 |
| 整数容差 |
I Eas |
实数 |
1e-06 |
整数变量的允许偏离范围 |
| MIP 节点限制 |
NodeLim |
整数 |
无限制 |
分支定界树中允许的最大节点数 |
| 求解状态 |
SolPrint |
整数 |
2 |
控制求解过程日志的输出详细程度 |
| 相对最优间隙 |
OptCR |
实数 |
0.1 |
当当前间隙低于该值时终止求解 |
| MIP 强调 |
MIP Emphasis |
整数 |
0 |
0=平衡，1=可行性优先，2=最优性优先，3=边界优先 |
| 预处理级别 |
Pre Process |
整数 |
-1 |
预处理的强度。-1=自动，0=关闭，1=标准，2=增强 |
| 切割平面生成 |
Cuts |
整数 |
-1 |
控制切割平面生成。-1=自动，0=关闭，1=适度，2=强力 |
| 种子值 |
Seed |
整数 |
0 |
随机数生成器种子。值为 0 表示随机生成，非零值确保结果可复现 |
| 迭代限制 |
IterLim |
整数 |
无限制 |
单纯形迭代的最大次数 |
6.4 高级配置
对于有经验的用户，ODHCPLEX 提供以下高级配置选项：
- 自定义切割平面：控制 CPLEX 切割平面生成器的启用/禁用
- 预处理级别：设置预处理的强度（0=关闭，1=标准，2=增强）
- 节点选择策略：选择分支定界树中的节点选择策略（深度优先、广度优先、最佳优先等）
- 变量分支策略：控制分支变量的选择方法
- MIP 强调：设置求解器偏重于可行性或最优性
通过合理配置上述选项，用户可以根据具体问题的特性优化求解器行为，获得最佳的求解性能。
在线留言
尊敬的客户朋友，如您有任何意见建议，请通过下表反馈给我们，我们会尽快与您联系。
|
400-621-1085
