AMPL：稀疏语法

Question

AMPL 中的这段代码正确解决了对匹配算法：

set Student;.
        # student tuples inside Student x Student
set Pair within {Student, Student}; 

       # sparse value in that tuples    
param value {Pair};

var x {Pair} binary;  # decision var

maximize total_value: sum {(i,j) in Pair} value[i,j] * x[i,j];

s.t. perfect_match {i in Student}:  # constraint
sum {(i,j) in Pair} x[i,j] + sum {(j,i) in Pair} x[j,i] = 1;

data;

set Student := A  B  C  D  E  F G H I J;

# sparse set of student tuples   
set Pair:  A  B  C  D  E  F G H I J :=  
A  -  -  -  -  -  - - - - -
B  +  -  -  -  -  - - - - -
C  +  +  -  -  -  - - - - -
D  +  +  +  -  -  - - - - -
E  +  +  +  +  -  - - - - -
F  +  +  +  +  +  - - - - -
G  +  +  +  +  +  + - - - -
H  +  +  +  +  +  + + - - -
I  +  +  +  +  +  + + + - -
J  +  +  +  +  +  + + + + -;

# sparse matrix with scores
param value:  A  B  C  D  E  F G H I J :=  
A  .  .  .  .  .  . . . . .
B  3  .  .  .  .  . . . . .
C  5  8  .  .  .  . . . . .
D  1 -4  7  .  .  . . . . .
E  2 -1  9  2  .  . . . . .
F  2  5  3  2  9  . . . . .
G  8  2  1  1  3 -2 . . . .
H  2  3  3  4  5  1 1 . . .
I 13 -1  3  4  4 -5 2 2 . .
J  1  2  6  6  7 -4 5 6 1 .;

此代码运行顺利，但很麻烦，因为必须声明 2 倍有效的学生元组以及与该元组关联的值。

其他 shows an alternative syntax (showed below) for that kind of situation in an answer. The same syntax is showed in a 2011 paper from Darin England from University of Minnesota (Mathematical programming formulations using AMPL) 第 5 页。

# sparse matrix with scores
param: pair: value:  A  B  C  D  E  F G H I J :=  
A  .  .  .  .  .  . . . . .
B  3  .  .  .  .  . . . . .
C  5  8  .  .  .  . . . . .
D  1 -4  7  .  .  . . . . .
E  2 -1  9  2  .  . . . . .
F  2  5  3  2  9  . . . . .
G  8  2  1  1  3 -2 . . . .
H  2  3  3  4  5  1 1 . . .
I 13 -1  3  4  4 -5 2 2 . .
J  1  2  6  6  7 -4 5 6 1 .;

但是，它在更新的 AMPL 版本中生成错误：

malformed header: extra ':' (last colon)

是否有一些解决方案可以在一个声明中定义集合元组和集合元组的值？

Answer 1

Is there some solution for defining set tuples and values of set tuples in just one declaration?

你发布的稀疏版本对我有用；最初我收到一条错误消息 "pair is not a set" 但这是由于与 "Pair" 的大小写不匹配造成的；一旦我解决了这个问题，它就做了它应该做的。我无法重现您提到的错误。完整的工作代码：

set Student;
        # student tuples inside Student x Student
set Pair within {Student, Student}; 

       # sparse value in that tuples    
param value {Pair};

data;

set Student := A  B  C  D  E  F G H I J;

param: Pair: value:  A  B  C  D  E  F G H I J :=  
A  .  .  .  .  .  . . . . .
B  3  .  .  .  .  . . . . .
C  5  8  .  .  .  . . . . .
D  1 -4  7  .  .  . . . . .
E  2 -1  9  2  .  . . . . .
F  2  5  3  2  9  . . . . .
G  8  2  1  1  3 -2 . . . .
H  2  3  3  4  5  1 1 . . .
I 13 -1  3  4  4 -5 2 2 . .
J  1  2  6  6  7 -4 5 6 1 .;

（如果有所不同，则使用 AMPL 3.1.0.201510231950）

稀疏数据输入的其他选项：

param: pair: value :=
A B 3
A C 5
B C 8
...
;

或者：

param: pair: value :=
[A,*]
B 3
C 5
D 1
...
J 1
[B,*]
C 8
D -4
...
J 2
...
;

我从来没有想过是否可以像您发布的代码那样在二维 table 布局中进行；这对于小型数据集来说更具可读性，但我主要使用大型数据集。

您还可以通过将 Pair 声明为一组对，然后将 Student 定义为作为 Pair 中元组的任一成员的所有值的集合来消除学生的重复：

set Pair dimen 2;
param Value{Pair};

set Students := setof{(i,j) in Pair} i union setof{(i,j) in Pair} j;

然后如上定义Pair和Value，Student由Pair派生

Answer 2

今晚AMPL支持给了我答案。

我对AMPL支持团队的效率感到非常惊讶！

Using Windows, We found that AMPL version 20171122 and later reject the user's examples with the "malformed header" message, but versions 20171103 and earlier accept the examples (including perfectEr.mod). We have been working to fix the problem. Meanwhile, a workaround is to replace "param: Pair: value: . . ." by "param: Pair: value [,]: . . .".

我已经测试过了，它可以在我的 AMPL 版本中使用。我只在 param: Pair: value（第 23 行）之后和冒号（:）之前添加了 [*.*]。一切顺利。

reset;
set Student;
set Pair within {Student, Student}; # Student cross Student;

param value {Pair};

# Decision Variable
var x {Pair} binary;

# Objective
maximize total_value: sum {(i,j) in Pair} value[i,j] * x[i,j];

# Constraint
s.t. perfect_match {i in Student}:
sum {(i,j) in Pair} x[i,j] + sum {(j,i) in Pair} x[j,i] = 1;

data;

# Students names
set Student := A  B  C  D  E  F G H I J;  

# affinity in defined tuples (Pair)
param: Pair: value [*,*]: 
   A  B  C  D  E  F G H I J :=   
A  .  .  .  .  .  . . . . .
B  3  .  .  .  .  . . . . .
C  5  8  .  .  .  . . . . .
D  1 -4  7  .  .  . . . . .
E  2 -1  9  2  .  . . . . .
F  2  5  3  2  9  . . . . .
G  8  2  1  1  3 -2 . . . .
H  2  3  3  4  5  1 1 . . .
I 13 -1  3  4  4 -5 2 2 . .
J  1  2  6  6  7 -4 5 6 1 .;

option solver CPLEX;
solve;
option omit_zero_rows 1;
display x

AMPL：稀疏语法

AMPL: sparse syntax

linear-programming

ampl