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倍的学生元组是有效的，并声明一个与该元组相关联的值。

其他问题在回答中为这种情况显示了另一种语法(如下所示)。同样的语法在2011年明尼苏达大学(使用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

今晚AMPL的支持给了我一个答案。

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

使用Windows时，我们发现AMPL版本20171122和更高版本使用“格式错误的标题”消息拒绝用户的示例，但是版本20171103和更早版本接受示例(包括perfectEr.mod)。我们一直在努力解决这个问题。同时，解决办法是替换"param:偶数: value：…“。通过"param: Pair: value，：：…“。

我测试过它，它在我的AMPL版本中工作。我只在[*.*] (第23行)和冒号(:)之后添加了param: Pair: value。一切都很顺利。

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

Answer 2

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

您发布的稀疏版本适用于我；最初，我收到了一条错误消息，“结对不是一个集合”，但这是由于一个大小写与“对”不匹配造成的；一旦我修复了它，它就做了它应该做的事情。我不能重现你提到的错误。完整的工作代码：

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

我从来没有想过是否有可能像您发布的代码那样在二维表布局中这样做；对于小数据集来说，这可能更容易读懂，但我主要使用的是大型数据集。

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

set Pair dimen 2;
param Value{Pair};

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

然后按照上面的方式定义对和值，而学生是从对派生出来的。