5.5. AMPL 的建模与优化

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

目前,MindOpt 支持在 Windows/Linux/OSX 系统中,通过 AMPL 建立 线性规划模型 并调用 MindOpt 来求解。关于 AMPL 的更多内容请参考 AMPL 官方文档

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

5.5.1. 安装 AMPL 并确认 mindoptampl 应用

调用 mindoptampl 之前需要安装 MindOpt。关于 MindOpt 的安装与配置请参考 单机版 MindOpt 安装

  1. 安装AMPL

    用户可以在 AMPL 官网进行下载安装,如: TRY AMPL

  2. 验证 mindoptampl 应用

    mindoptampl 应用位于安装包的以下位置:

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

    用户可以通过命令行来验证 mindoptampl 应用:

    mindoptampl --version
    

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

    0.19.0 (Darwin x86_64), driver(20220127), ASL(20201107)
    

5.5.2. 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

设置是否启用网络单纯形法

ipm_dual_tolerance

设置内点法使用的对偶可行性(相对)容差

ipm_gap_tolerance

设置内点法中的对偶间隔(相对)容差

ipm_max_iterations

设置内点法中最大迭代次数

ipm_primal_tolerance

设置内点法使用的原始可行性(相对)容差

max_time

设置优化器的最大求解时间(以秒为单位)

method

设置优化器中使用的算法

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

设置是否返回结果(生成.sol文件)

MindOpt 完成计算后,状态信息将以 exit code 的形式返回给 AMPL。用户可通过如下方式获取状态信息:

ampl: display solve_result_num;

關於 exit code 和状态信息,請參考 异常返回码.

5.5.3. 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
;