7.2. AMPL 的建模与优化

AMPL (A Mathematical Programming Language) 是一种代数化的建模语言,目的是将复杂的优化问题简化为 抽象的代数表达形式;让用户在开发上只需要专注于 代数模型 的建立,模型完成后再将 数据 分别引入。如此不但加快开发流程,更有效降低了模型输入错误的可能性。

目前,MindOpt 可对在 Windows/Linux/OSX 平台上通过 AMPL 建立的 线性规划模型 进行求解。关于 AMPL 的更多内容请参考 AMPL 官方文档

在本节中,我们将介绍如何使用 MindOptmindoptampl 应用来求解 AMPL 模型。

7.2.1. mindoptampl 应用

mindoptampl 应用在 MindOpt 安装过程中自动生成。关于 MindOpt 的安装与配置请参考 单机版安装

根据如下方式验证 mindoptampl 应用:

MindOpt 安装完成后, mindoptampl 的路径如下:

<MDOHOME>\<VERSION>\<PLATFORM>\bin\mindoptampl

用户可以如下命令行来验证 mindoptampl 应用是否可用:

mindoptampl --version

若返回类似如下的 MindOptmindoptampl 的版本信息,则说明安装成功:

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 参数的详细说明,请参考 参数

MindOpt AMPL接口参数

参数

说明

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 级别

print

设置打印级别

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 foodsNutrition of foods

Prices 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

Nutrition of foods

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问题 的目标是以 最低的价格 来搭配 满足营养需求 的食物组合;该问题的代数数学模型如下:

\[\begin{split}\begin{eqnarray} &\min & \sum_{j \in J} \mbox{cost}_j \times \mbox{buy}_j \\ &\mbox{s.t.} & \mbox{n_min}_i \leq \sum_{j \in J} \mbox{amt}_{i,j} \times \mbox{buy}_j \leq \mbox{n_max}_i, \forall i \in I, \\ & & \mbox{f_min}_j \leq \mbox{buy}_j \leq \mbox{f_max}_j, \forall j \in J. \end{eqnarray}\end{split}\]

其中

  • \(\mbox{buy}\) 为决策变量,

  • \(\mbox{f_min}\)\(\mbox{f_max}\) 分别为 \(\mbox{buy}\) 的下界和上界,

  • \(\mbox{cost}\) 是目标函数中的系数,

  • \(\mbox{amt}\) 是约束矩阵,

  • \(\mbox{n_min}\)\(\mbox{n_max}\) 分别为是约束的下界和上界。

使用AMPL前,首先将上述 Diet问题 的代数数学模型转为以下的AMPL模型

  1. 抽象的代数模型 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];
    
  2. 数据文件 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
;