7.2. AMPL 的建模与优化¶
AMPL (A Mathematical Programming Language) 是一种代数化的建模语言,目的是将复杂的优化问题简化为 抽象的代数表达形式;让用户在开发上只需要专注于 代数模型 的建立,模型完成后再将 数据 分别引入。如此不但加快开发流程,更有效降低了模型输入错误的可能性。
目前,MindOpt 可对在 Windows/Linux/OSX 平台上通过 AMPL 建立的 线性规划模型 进行求解。关于 AMPL 的更多内容请参考 AMPL 官方文档。
在本节中,我们将介绍如何使用 MindOpt 的 mindoptampl 应用来求解 AMPL 模型。
7.2.1. mindoptampl 应用¶
mindoptampl 应用在 MindOpt 安装过程中自动生成。关于 MindOpt 的安装与配置请参考 单机版安装。
根据如下方式验证 mindoptampl 应用:
MindOpt 安装完成后, mindoptampl 的路径如下:
<MDOHOME>\<VERSION>\<PLATFORM>\bin\mindoptampl用户可以如下命令行来验证 mindoptampl 应用是否可用:
mindoptampl --version
若返回类似如下的 MindOpt 和 mindoptampl 的版本信息,则说明安装成功:
1.0.0 (Darwin x86_64), driver(20230713), ASL(20201107)mindoptampl 支持直接命令行求解
.nl
格式的文件,可在命令行中直接运行如下指令来求解。mindoptampl <MDOHOME>\<VERSION>\examples\ampl\diet.nl
7.2.2. 安装 AMPL¶
用户可以在 AMPL 官网进行下载安装,如: TRY AMPL。
7.2.3. AMPL 接口参数和返回值¶
mindoptampl 提供了一些可配置的参数,用户可以通过 AMPL 的 option
命令设置 mindoptampl_options
参数,如:
ampl: option mindoptampl_options 'num_threads=4 max_time=3600';
mindoptampl 支持的全部参数可以透过以下命令获取:
mindoptampl -=
MindOpt 参数的详细说明,请参考 参数。
参数 |
说明 |
---|---|
dualization |
设置是否对模型进行对偶化 |
enable_network_flow |
设置是否启用网络单纯形法 |
enable_stochastic_lp |
设置是否启用检测随机LP结构,特定问题结构时开启可加速 |
ipm_dual_tolerance |
设置内点法使用的对偶可行性(相对)容差 |
ipm_gap_tolerance |
设置内点法中的对偶间隔(相对)容差 |
ipm_max_iterations |
设置内点法中最大迭代次数 |
ipm_primal_tolerance |
设置内点法使用的原始可行性(相对)容差 |
max_time |
设置优化器的最大求解时间(以秒为单位) |
method |
设置优化器中使用的算法 |
mip_allow_dual_presolve |
指定是否启动MIP的对偶预处理方法 |
mip_auto_configuration |
设置是否开启MIP自动参数配置 |
mip_cutoff |
设置目标值的切断值,以防止寻找比这个值更差的解 |
mip_detect_disconnected_components |
指定是否在MIP中启用非连通分量策略 |
mip_gap_abs |
设置绝对的 MIP 间隔容差 |
mip_gap_rel |
设置相对的 MIP 间隔容差 |
mip_integer_tolerance |
设置MIP求解中整型判定精度 |
mip_linearization_big_m |
设置MIP中,重列非线形函数时的最大系数 |
mip_max_stalling_nodes |
设置允许延迟的最大节点数 |
mip_max_nodes |
设置MIP中的最大节点限制 |
mip_max_sols |
设置MIP中最大解数目 |
mip_objective_tolerance |
设置MIP求解中目标值比较精度 |
mip_root_parallelism |
设置MIP求解中根节点允许的最大并发线程数 |
mip_solution_pool_size |
设置解缓存池的最大容量 |
num_threads |
设置优化求解时使用的最大线程数 |
presolve |
设置 presolver 级别 |
设置打印级别 |
|
spx_crash_start |
设置是否在单纯形法中使用初始基解生成方式 |
spx_column_generation |
设置是否在单纯形法中使用列生成 |
spx_dual_pricing |
设置单纯形法中的对偶定价策略 |
spx_dual_tolerance |
设置单纯形法使用的对偶可行性(相对)容差 |
spx_max_iterations |
设置单纯形法中的最大迭代次数 |
spx_primal_pricing |
设置单纯形法中的原始定价策略 |
spx_primal_tolerance |
设置单纯形法使用的原始可行性容差 |
wantsol |
设置是否返回结果(without -AMPL),1 写.sol文件,2 打印变量取值,8 不要打印解信息。 |
当 MindOpt 完成计算后,状态信息将以 exit code
的形式返回给 AMPL。用户可通过如下方式获取状态信息:
ampl: display solve_result_num;
关于 exit code
和状态信息,请参考 Result code.
7.2.4. AMPL调用MindOpt示例¶
以下将以 Diet 问题 为例,说明如何创建 AMPL 模型并调用 mindoptampl 应用求解。
Diet 问题使用了以下两表的数据: Prices of foods 和 Nutrition of foods。
Food |
Price |
---|---|
BEEF |
3.19 |
CHK |
2.59 |
FISH |
2.29 |
HAM |
2.89 |
MCH |
1.89 |
MTL |
1.99 |
SPG |
1.99 |
TUR |
2.49 |
Food |
A |
C |
B1 |
B2 |
---|---|---|---|---|
BEEF |
60 |
20 |
10 |
15 |
CHK |
8 |
0 |
20 |
20 |
FISH |
8 |
10 |
15 |
10 |
HAM |
40 |
40 |
35 |
10 |
MCH |
15 |
35 |
15 |
15 |
MTL |
70 |
30 |
15 |
15 |
SPG |
25 |
50 |
25 |
15 |
TUR |
60 |
20 |
15 |
10 |
Diet问题 的目标是以 最低的价格 来搭配 满足营养需求 的食物组合;该问题的代数数学模型如下:
其中
\(\mbox{buy}\) 为决策变量,
\(\mbox{f_min}\) 和 \(\mbox{f_max}\) 分别为 \(\mbox{buy}\) 的下界和上界,
\(\mbox{cost}\) 是目标函数中的系数,
\(\mbox{amt}\) 是约束矩阵,
\(\mbox{n_min}\) 和 \(\mbox{n_max}\) 分别为是约束的下界和上界。
使用AMPL前,首先将上述 Diet问题 的代数数学模型转为以下的AMPL模型
抽象的代数模型
diet.mod
,set NUTR; set FOOD; param cost {FOOD} > 0; param f_min {FOOD} >= 0; param f_max {j in FOOD} >= f_min[j]; param n_min {NUTR} >= 0; param n_max {i in NUTR} >= n_min[i]; param amt {NUTR,FOOD} >= 0; var Buy {j in FOOD} >= f_min[j], <= f_max[j]; minimize Total_Cost: sum {j in FOOD} cost[j] * Buy[j]; subject to Diet {i in NUTR}: n_min[i] <= sum {j in FOOD} amt[i,j] * Buy[j] <= n_max[i];
数据文件
diet.dat
。data; set NUTR := A B1 B2 C ; set FOOD := BEEF CHK FISH HAM MCH MTL SPG TUR ; param: cost f_min f_max := BEEF 3.19 0 100 CHK 2.59 0 100 FISH 2.29 0 100 HAM 2.89 0 100 MCH 1.89 0 100 MTL 1.99 0 100 SPG 1.99 0 100 TUR 2.49 0 100 ; param: n_min n_max := A 700 10000 C 700 10000 B1 700 10000 B2 700 10000 ; param amt (tr): A C B1 B2 := BEEF 60 20 10 15 CHK 8 0 20 20 FISH 8 10 15 10 HAM 40 40 35 10 MCH 15 35 15 15 MTL 70 30 15 15 SPG 25 50 25 15 TUR 60 20 15 10 ;
接着,在AMPL中加载上述文件,调用 mindoptampl 应用来求解该问题:
ampl: model diet.mod;
ampl: data diet.dat;
ampl: option solver mindoptampl;
ampl: option mindoptampl_options 'numthreads=4 maxtime=1e+4';
ampl: solve;
求解完成后,用户可以通过 AMPL 的 display
命令来查看结果:
ampl: display Buy;
Buy [*] :=
BEEF 0
CHK 0
FISH 0
HAM 0
MCH 46.6667
MTL 0
SPG 0
TUR 0
;