作者

Tapio Westerlund (twesterl@abo.fi) 和 Toni Lastusilta。芬兰奥布学术大学

Ville-Pekka Eronen。芬兰图尔库大学

介绍

AlphaECP 是一款基于扩展割平面（ECP）方法的混合整数非线性规划（MINLP）求解器。该求解器可应用于一般的 MINLP 问题，并能确保伪凸 MINLP 问题获得全局最优解。除非另有说明，本文档均假设所考虑的问题为最小化问题。

ECP 方法是 Kelley 割平面方法的扩展，Kelley 方法最初针对凸 NLP 问题提出 [105]。该方法在每次迭代中仅需求解一个 MIP 子问题。MIP 子问题可以求解至最优、可行解，或在中间迭代中仅求解整数松弛解。这使得 ECP 算法高效且易于实现。有关底层算法的更多信息，请参见 [199] 和 [145, 174, 198, 200]。

GAMS/AlphaECP 算法的进一步发展引入了额外的功能。现在可以在 MIP 解处调用 NLP 求解器。这提高了 AlphaECP 寻找可行且精确解的能力，特别是对于主要包含连续变量的 MINLP 问题。此外，还可以使用一种启发式方法在迭代过程中重新选择割平面，以提高求解非凸问题的能力。除了基于约束容忍度的终止条件外，当满足相对目标间隙终止准则时，算法也可以终止。此特性仅支持凸问题。

许可和软件要求

用户需要拥有 GAMS/AlphaECP 许可证才能使用 GAMS/AlphaECP。此外，求解混合整数子问题需要已获许可的 MIP 求解器，如果使用 NLP 选项，则还需要已获许可的 NLP 求解器。

运行 AlphaECP

AlphaECP 求解 MINLP 模型。如果 AlphaECP 未被指定为这些模型的默认求解器，可以在求解语句之前发出以下命令来调用它：

option minlp=alphaecp, miqcp=alphaecp;

原则上，AlphaECP 也可以处理 NLP 模型，但它更适合 MINLP 问题。然而，当与 NLP 求解器结合时，它可以找到 NLP 求解器自身无法找到的解。在这种情况下，它充当了一个良好的起始点生成器。如果您想使用 AlphaECP 求解 NLP，需要通过将 NLP 作为 MINLP 求解来"欺骗"GAMS 系统：

solve mynlpmodel minimizing obj using minlp;

在 AlphaECP 的整个运行过程中以及算法结束时，都会报告约束违反情况。仅报告非线性约束的违反情况。线性约束的违反情况由 MIP/NLP 求解器的可行性容忍度决定。

GAMS/AlphaECP 输出

以下日志输出是针对 GAMS 模型库中的 MINLP 模型 fuel.gms 获得的：

------------------------------------------------------------------------------
                  Welcome to AlphaECP v2.11.01
 MINLP Problem Solver using the Extended Cutting Plane Approach.
 Method development - T.Westerlund, Abo Akademi University, FIN
 Algorithm development - T.Lastusilta, Abo Akademi University, FIN
 Algorithm development - V.-P. Eronen, Turku University, FIN
 Westerlund Tapio and Poern Ray (2002). Optimization & Engineering, 3, 253-280
------------------------------------------------------------------------------
Minimization problem: "fuel.gms"
The GAMS-model has in total 39 elements of which 15% are non-linear(NL)
included in 16 constraints of which 25% are NL
The NL constraint signs: =E=(3), =G=(1), =L=(0)
The number of variables in NL elements are 6 from a total of 16
variables: Continuous(13), Binary(3), Integer(0)
-------------------------------------------------------------------------------
Using following settings
AlphaECP option file                                    optfile=0
Time limit for AlphaECP (in seconds)                    reslim=10000000000
Solvelink for NLP and MIP sub-solver                    solvelink=5
Solver trace file                                       solvetrace=(Inactive)
Cutting plane strategy (0-3)                            CUTdelcrit=3
Cut generation pace                                     CUTnrcuts=0
Updating multiplier if MIP is infeasible                ECPbeta=1.3
Write encountered solutions to gdx files                ECPdumpsol=0
Updating multiplier when verifying solution             ECPgamma=2
Maximum number of AlphaECP iterations                   ECPiterlim=-1
Level of AlphaECP output to statusfile (0-4)            ECPloglevel=0
Master strategy (0=User 1=Convex)                       ECPmaster=0
Return solution (1.MIP/2.NLP/...)                       ECPretsol=2
User specified start-point (0-3)                        ECPstart=3
AlphaECP strategy (1-5)                                 ECPstrategy=2
AlphaECP termination criterion (1-2)                    ECPtoltype=1
Upper limit of considered MIP solutions per MIP call    MIPnrsols=50
Relative MIP gap in intermediate sub-problems (0->1.0)  MIPoptcr=1.00
Initial iteration limit when MIPoptcr is reduced        MIPoptcrlim=200
Strategy to increase MIPoptcrlim                        MIPoptcrlimtype=0
MIP is solved to optimality with this frequency         MIPoptimaliter=0
Strategy for multiple MIP solutions                     MIPsolstrat=1
MIP solver for sub-problems and . option file number    MIPsolver=cplex.0
NLP strategy. Inactive:0 Active strategy:1-5            NLPcall=5
NLP solver call at next (incremental) iteration         NLPcalliter=0
NLP time limit per call (in seconds or auto=0)          NLPreslim=30
NLP solver for sub-problems and . option file number    NLPsolver=conopt.0
Constraint tolerance                                    TOLepsg=0.001
Distance tolerance for a new linearization              TOLepsz=0.1
Gradient tolerance                                      TOLgrad=1e-06
Infinity bound (MIP variable bound)                     TOLinfbnd=1e+10
Relative termination tolerance for MINLP                TOLoptcr=(Inactive)
-------------------------------------------------------------------------------
Itera  Stepcode, Number  Point Alpha OPT Movement Viol  Maximum   MIPobjval
tion   Problems  of Cuts usage Upd.  CR  Norm     Cons  Violation
Start-point: NL constraint (1) infeasibile
0      H         0       0     0     1   0        4     1.8E+03   NA
1      SAFGI     1       1     1     1   9.3E+03  0     1.1E-13   8566.12
1      FOUND SOLUTION:   8566.12      (NLP) in 1 sec.

2      SAFH      1       1     0     1   6.6E+03  4     1.8E+03   4844.02
3      SAFH      3       2     0     1   8.4E+03  3     1.8E+03   7031.72
4      SAFH      4       3     0     1   1E+03    2     1.8E+03   10157
5      SAH       5       4     0     1   0        1     7E+02     11925
...
100    AI        106     39    1     0   0        0     0.00067   11925
101    AI        106     39    1     0   0        0     0.00067   11925
102    AIJ       106     39    0     0   0        0     0.00067   11925
AlphaECP: Iteration procedure terminated normally
-------------------------------------------------------------------------------
Problem                   : fuel.gms
Solver Status             : Normal Completion
Model Status              : Locally Optimal
Exit comment              : No Issues
Final solution            : NLP
Objective value           : 8566.1189616876672517
Max constraint (4)        : 1.1368683772161602974e-13
Alternative solution      : MIP
Alt. objective value      : 8566.1189616876672517
Max constraint (4)        : 1.1368683772161602974e-13
Time used (seconds)       : 0.81
Time limit (seconds)      : 10000000000
Iterations used           : 102
Iteration limit           : -1
Function evaluations      : 496
Gradient evaluations      : 186
Domain violations         : 0
Gradients unusable        : 0
Alphamax bound violations : 0
ECP time usage            : 3.9 %
NLP time usage            : 3.8 %
MIP time usage            : 92.3 %
Optimal/total MIPs        : 19/102
NLP solver calls          : 8
-------------------------------------------------------------------------------

在每次迭代中，MIP 问题及其修改信息会在 10 列中给出。以下是各列的说明：

迭代：迭代标识符。

步骤代码，问题：表示本次迭代中采取的操作的字母，即下次迭代前的 MIP 问题修改。

A：MIP 求解器可行。

B：移动割平面后 MIP 求解器可行（即 alpha 更新）。

C：将割平面移近其生成点后 MIP 求解器可行。此举旨在更容易满足非线性等式约束。

D：线搜索成功（在 ECPstrategy 3 中）。

E：线搜索失败（在 ECPstrategy 3 中）。

F：调用了 NLP 求解器。

G：找到了 MINLP 解。

H：向下一个 MIP 问题添加了线性化。

I：更新了 alpha 值并可能添加了线性化。

J：所有割平面都是伪凸约束的有效下估计，非线性目标函数约束除外。

K：非线性目标函数约束值与 MIP 解值的差异超过 ε_f。进行了线性化以减小差异（在 ECPstrategy 3 中）。

L：移除了所有临时线性化。

M：域违反——某些约束无法被评估。

N：由于梯度问题，某些割平面无法生成。

O：无法生成任何割平面。

P：由于割平面反复移近其生成点，重新选择割平面。

Q：添加了临时线性化。

R：添加临时线性化失败。

S：选择了 MIP 求解器策略以寻找已遇到的解。

T：选择了要求 MIPnrsols 个解的 MIP 求解器策略。

U：选择了要求 MIPnrsols 个解且 MIPoptcr <= 0.2 的 MIP 求解器策略。

关于选项的说明

此处描述的选项可以通过使用 GAMS 选项语句或在 AlphaECP 选项文件中指定来设置。有关选项文件的更多信息，请参阅 GAMS 文档。许多选项也可以使用 GAMS 模型语句中的 option 语句设置。

AlphaECP 选项摘要

基本选项

选项	说明	默认值
ECPmaster	主策略	0
ECPstrategy	AlphaECP 策略	2
ECPtoltype	AlphaECP 终止准则	1
reslim	AlphaECP 时间限制（秒）	GAMS reslim

高级用户的算法选项

选项	说明	默认值
CUTdelcrit	割平面策略	3
CUTnrcuts	割生成速度	0
ECPbeta	MIP 不可行时的更新乘数	1.3
ECPdumpsol	将遇到的解写入 gdx 文件	0
ECPgamma	验证解时的更新乘数	2.0
ECPiterlim	最大 AlphaECP 迭代次数	-1
ECPloglevel	输出到状态文件的级别	0
ECPmaster	主策略	0
ECPretsol	返回解	2
ECPstart	用户指定的起始点	3
solvelink	NLP 和 MIP 子求解器的求解链接	5
solvetrace	求解跟踪文件名	""
solvetraceincumbent	写入跟踪记录时的最小原始界改进	1e-6
solvetracetime	写入跟踪记录的时间间隔	1
TOLepsf	伪凸目标函数终止容忍度	1e-3
TOLepsg	约束容忍度	1e-3
TOLepsz	新线性化的距离容忍度	1e-1
TOLgrad	梯度容忍度	1e-6
TOLinfbnd	无穷界（MIP 变量界）	1e10
TOLoptcr	MINLP 相对终止容忍度	GAMS optCR

MIP 求解器相关选项

选项	说明	默认值
MIPnrsols	每次 MIP 调用考虑的解数量上限	50
MIPoptcr	中间子问题的相对 MIP 间隙	1.0
MIPoptcrlim	MIPoptcr 减小时的初始迭代限制	200
MIPoptcrlimtype	增加 MIPoptcrlim 的策略	0
MIPoptimaliter	以此频率将 MIP 求解至最优	0

NLP 求解器相关选项

选项	说明	默认值
NLPcall	NLP 策略	5
NLPcalliter	下一次（增量）迭代调用 NLP 求解器	0
NLPlimsameint	在重复整数解若干次后调用 NLP	5
NLPloglevel	NLP 求解器输出级别	0
NLPreslim	每次调用的 NLP 时间限制	0

AlphaECP 选项详细说明

CUTdelcrit （整数）：割平面策略 ↵

默认值：3

值	含义
0	不移除任何有效割平面。
1	同 0，但如果无法生成常规割平面，允许在半随机点处使用临时割平面。
2	允许临时割平面和割平面重新选择，并利用内存保存点和割平面。
3	同 2，并在终止前调用重新选择启发式方法以改进解。

CUTnrcuts （实数）：割生成速度 ↵

每次迭代中生成的线性化数量可由 AlphaECP 选择，可与违反约束数量成比例，也可由固定数量决定。此外，割平面重新选择 CUTdelcrit >=2 会向问题添加割平面，同时考虑请求的割生成速度。

默认值：0

值	含义
0	由 AlphaECP 决定。
0<n<1	线性化数量 = n × 可能生成的线性化数量。
>1	指定要生成的线性化数量。

ECPbeta （实数）：MIP 不可行时的更新乘数 ↵

如果 MIP 解不可行，则使用 ECPbeta 乘数更新无效割平面。

范围：[1.001, ∞]

默认值：1.3

ECPdumpsol （整数）：将遇到的解写入 gdx 文件 ↵

默认值：0

值	含义
0	不写入。
1	写入 NLP 求解器找到的解。
2	写入 NLP 或 MIP 求解器找到的解。

ECPgamma （实数）：验证解时的更新乘数 ↵

如果获得了一个 MINLP 解，但某些割平面不是有效的下估计，则使用 ECPgamma 乘数更新它们，使其成为有效的下估计。

范围：[1.001, ∞]

默认值：2.0

ECPiterlim （整数）：AlphaECP 最大迭代次数 ↵

这是 AlphaECP 执行优化的最大迭代次数。值为 -1 表示停用 AlphaECP 迭代限制。

默认值：-1

值	含义
-1	无限制。
>=0	指定迭代限制。

ECPloglevel （整数）：输出到状态文件的 AlphaECP 输出级别 ↵

默认值：0

值	含义
0	最低输出。
1	标准输出。
2	详细输出。
3	调试输出。
4	大量调试输出。

ECPmaster （整数）：主策略 ↵

默认值：0

值	含义
0	用户定义的策略由 ECPstrategy 决定。
1	凸问题策略。将某些选项设置为适合凸问题的默认值。

ECPretsol （整数）：返回解 ↵

默认值：2

值	含义
1	返回 MIP 解。
2	返回 NLP 解（若存在且可用）。
3	返回 MIP 和 NLP 解中较好的一个。

ECPstart （整数）：用户指定的起始点 ↵

默认值：3

值	含义
0	使用 GAMS 提供的默认点。
1	使用用户提供的点。
2	使用从松弛 MIP 获得的点。
3	尝试所有选项（0、1、2），如果有多个候选点则选择最佳的一个。

ECPstrategy （整数）：AlphaECP 策略 ↵

默认值：2

值	含义
1	标准 ECP 算法。
2	带 NLP 求解器调用的标准 ECP 算法。
3	带 NLP 求解器调用和目标函数线性化的 ECP 算法。
4	同 2，但在每次 NLP 调用后还尝试改进整数解。
5	同 3，但在每次 NLP 调用后还尝试改进整数解。

ECPtoltype （整数）：AlphaECP 终止准则 ↵

默认值：1

值	含义
1	基于约束容忍度的终止。
2	如果满足条件，基于相对目标间隙的终止。

MIPnrsols （整数）：每次 MIP 调用考虑的解数量上限 ↵

默认值：50

值	含义
-1	无限制。
0	使用 GAMS 默认值。
>0	最大解数量。

MIPoptcr （实数）：中间子问题的相对 MIP 间隙 ↵

范围：[0, 1]

默认值：1.0

MIPoptcrlim （整数）：MIPoptcr 减小时的初始迭代限制 ↵

默认值：200

MIPoptcrlimtype （整数）：增加 MIPoptcrlim 的策略 ↵

默认值：0

值	含义
0	不增加。
1	每次重新优化时增加一倍。
2	每次重新优化时增加三倍。

MIPoptimaliter （整数）：以此频率将 MIP 求解至最优 ↵

指定将 MIP 子问题求解至最优的频率（每 N 次迭代执行一次最优求解）。

默认值：0

MIPsolstrat （整数）：多 MIP 解策略 ↵

默认值：1

值	含义
1	合并多个 MIP 解。
2	保留所有 MIP 解。
3	保留所有 MIP 解，并对 NLP 求解器尝试不同的起始点。
4	保留所有 MIP 解，对 NLP 求解器尝试不同的起始点，并允许在 NLP 求解器后改变整数变量。

MIPsolver （字符串）：子问题的 MIP 求解器及选项文件编号 ↵

求解器[.n] Solver 是应用于根节点的 GAMS MIP 求解器名称，n 是对应于 optfile 的整数。如果缺少 .n，则 optfile 视为零，即 MIP 求解器不会查找选项文件。此选项可用于覆盖默认值，默认使用 Option MIP = 求解器; 语句指定的 MIP 求解器或 GAMS 的默认 MIP 求解器。

默认值：GAMS MIP 求解器

NLPcall （整数）：NLP 策略 ↵

确定何时调用 NLP 求解器。

默认值：5

值	含义
0	不调用 NLP 求解器。
1	在每个 MIP 解处调用 NLP 求解器。
2	在最佳整数解处调用 NLP 求解器。
3	同 2，且在遇到同一整数解 NLPlimsameint 次时调用。
4	由 AlphaECP 决定。
5	由 AlphaECP 决定，并在调用前向变量水平添加噪声。

NLPcalliter （整数）：下一次（增量）迭代调用 NLP 求解器 ↵

指定 NLP 求解器调用的迭代间隔。

默认值：0

NLPlimsameint （整数）：重复整数解一定次数后调用 NLP ↵

如果连续 NLPlimsameint 次遇到相同的整数解，则调用 NLP 求解器。调用 NLP 求解器后计数器会重置。

范围：{1, ..., ∞}

默认值：5

NLPloglevel （布尔值）：NLP 求解器输出级别 ↵

默认情况下，NLP 求解器的详细日志在 AlphaECP 日志流中被抑制。如果启用此选项，NLP 日志将合并到 AlphaECP 日志中。

默认值：0

值	含义
0	无输出。
1	NLP 求解器日志输出到 GAMS 日志。

NLPreslim （实数）：每次调用的 NLP 时间限制 ↵

每次 NLP 求解器调用时给予所选 NLP 求解器的时间限制（秒）。将此选项设置为 0 会计算一个与问题大小相关的时间限制。

默认值：0

NLPsolver （字符串）：子问题的 NLP 求解器及选项文件编号 ↵

求解器[.n] Solver 是应用于根节点的 GAMS NLP 求解器名称，n 是对应于 optfile 的整数。如果缺少 .n，则 optfile 视为零，即 NLP 求解器不会查找选项文件。此选项可用于覆盖默认值，默认使用 Option NLP = 求解器; 语句指定的 NLP 求解器或 GAMS 的默认 NLP 求解器。

默认值：GAMS NLP 求解器

reslim （实数）：AlphaECP 时间限制（秒） ↵

默认值：GAMS reslim

solvelink （整数）：NLP 和 MIP 子求解器的求解链接 ↵

默认值：5

值	含义
1	通过脚本调用 NLP 和 MIP 求解器。
2	通过模块调用 NLP 和 MIP 求解器。
5	在内存中调用 NLP 和 MIP 求解器。

solvetrace （字符串）：求解跟踪文件名 ↵

solvetraceincumbent （实数）：写入跟踪记录时的最小原始界改进 ↵

默认值：1e-6

solvetracetime （实数）：写入跟踪记录的时间间隔 ↵

默认值：1

TOLepsf （实数）：伪凸目标函数终止容忍度 ↵

非线性目标函数值与 MIP 目标函数值之间允许的最大绝对差值（仅在 ECPstrategy 3 中使用）。

范围：[1e-20, 1]

默认值：1e-3

TOLepsg （实数）：约束容忍度 ↵

非线性约束容忍度定义了非线性约束可能违反的最大值。例如，要求为零的约束在解处的值可以保持在 ± TOLepsg 范围内。

范围：[1e-20, 1]

默认值：1e-3

TOLepsz （实数）：新线性化的距离容忍度 ↵

有效割平面与其生成点（MIP 解）之间的最大垂直距离。

范围：[1e-20, 1]

默认值：1e-1

TOLgrad （实数）：梯度容忍度 ↵

梯度的偏导数绝对值必须高于 TOLgrad 值，才被视为非零。

范围：[1e-20, 1]

默认值：1e-6

TOLinfbnd （实数）：无穷界（MIP 变量界） ↵

所有变量必须具有正有限界和负有限界，以确保 MIP 问题有界。有限界值 TOLinfbnd 将应用于单边或双边无界变量。

默认值：1e10

TOLoptcr （实数）：MINLP 相对终止容忍度 ↵

如果 |UB-LB|/(10E-12+max(|LB|,|UB|)) < TOLoptcr，则满足相对目标间隙终止准则，其中 UB 是当前最佳上界，LB 是当前最佳下界。上界通过求解 NLP 问题获得，下界来自 MIP 问题的下界。如果该不等式成立且 ECPtoltype=2，算法将终止。

范围：[1e-20, ∞]

默认值：GAMS optCR

常见问题（FAQ）

• 求解凸问题的最佳设置是什么？

  使用 ECPmaster 1。

• 如果求解速度至关重要，最佳设置是什么？

  尝试 ECPstrategy 1 和 CUTdelcrit 1，看看使用多线程的 MIP 求解器是否能提高求解速度。但请注意，对于带有非线性等式约束的非凸问题，可能找不到可行解。

• 如果求解质量至关重要，最佳设置是什么？

  使用 NLPcalliter 1 和 MIPsolstrat 4 或 3，并尝试 CUTnrcuts 选项的不同值，例如 0.1。

• 目标函数是非线性的，是否应使用默认的 ECPstrategy？

  如果目标函数约束可以写成 ECPstrategy 3 所需的格式，则此策略可能找到更好的解。如果约束和目标函数都是伪凸的，则能够找到全局最优解。