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.15.1 (Darwin x86_64), driver(20210726), ASL(20201107)
    

5.5.2. AMPL 接口参数和返回值

mindoptampl 提供了一些可配置的参数,用户可以通过 AMPL 的 option 命令设置 mindoptampl_options 参数,如:

ampl: option mindoptampl_options 'numthreads=4 maxtime=1e+4';

mindoptampl 支持的全部参数可以透过以下命令获取:

mindoptampl -=

MindOpt 参数的详细说明,请参考 可选输入参数

MindOpt AMPL接口参数

参数

说明

Dualization

设置是否对模型进行对偶化

EnableNetworkFlow

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

IPM/DualTolerance

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

IPM/GapTolerance

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

IPM/MaxIterations

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

IPM/PrimalTolerance

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

Maxtime

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

Method

设置优化器中使用的算法

NumThreads

设置优化求解时使用的最大线程数

Presolve

设置 presolver 级别

SPX/CrashStart

设置是否在单纯形法中使用初始基解生成方式

SPX/ColumnGeneration

设置是否在单纯形法中使用列生成

SPX/DualPricing

设置单纯形法中的对偶定价策略

SPX/DualTolerance

设置单纯形法使用的对偶可行性(相对)容差

SPX/MaxIterations

设置单纯形法中的最大迭代次数

SPX/PrimalPricing

设置单纯形法中的原始定价策略

SPX/PrimalTolerance

设置单纯形法使用的原始可行性容差

WantSol

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

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

ampl: display solve_result_num;
Exit codes和状态信息

Exit Code

说明

0

Model status is not available.

1

Model was proven to be primal/dual feasible, and an optimal solution is available.

2

Model was proven to be primal infeasible.

3

Model was proven to be primal unbounded.

4

Model was proven to be either primal infeasible or primal unbounded.

-1

Unspecified internal error.

-2

Insufficient memory.

-10

License is not valid.

-1000

(I/O) General IO error.

-1001

(I/O) Failed to read data from file.

-1002

(I/O) Failed to write data to file.

-1003

(I/O) Invalid directory.

-1100

(I/O) Failed to parse the file.

-1200

(I/O) The input token ID for the remote computing is not valid.

-1201

(I/O) Failed to connect to the remote computing server.

-2000

Failed to input/load a model.

-2001

Model is empty.

-2002

Row index is not valid.

-2003

Column index is not valid.

-2004

Row name is not valid.

-2005

Column name is not valid.

-2010

A string attribute was not recognized.

-2011

An integer attribute was not recognized.

-2012

A real attribute was not recognized.

-3000

Solution is not available.

-3001

Unbounded ray is not available.

-3002

Solver statistics is not available.

-3003

Unrecognized basis status.

-4000

Failed to change a parameter value.

-4001

Failed to retrieve a parameter value.

-9000

Iteration limit was reached in optimization.

-9001

Time limit was reached in optimization.

-9002

Control-C command was captured in optimization.

-10000

Numerical difficulties in Simplex algorithm.

-20000

Numerical difficulties in Interior-point algorithm.

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
;