AMPL: разреженный синтаксис

Этот фрагмент кода в 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 .;

Этот код работает плавно, но он громоздок, потому что нужно в два раза объявлять, какие кортежи студентов действительны, и значение, связанное с этими кортежами.

Другой вопрос показывает альтернативный синтаксис (показанный ниже) для такой ситуации в ответе. Тот же синтаксис показан в статье 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)

Есть ли какое-то решение для определения заданных кортежей и значений заданных кортежей всего в одном объявлении?


person Paulo Buchsbaum    schedule 02.05.2018    source источник


Ответы (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
...
;

Я так и не понял, возможно ли это сделать в двухмерном макете таблицы, как в опубликованном вами коде; это было бы более читабельно для небольших наборов данных, но я в основном работаю с большими.

Вы также можете устранить дублирование студентов, объявив 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.

person Geoffrey Brent    schedule 03.05.2018
comment
Да, явное перечисление кортежей работает, и это умно косвенно определять студентов. Я понимаю, что 2D-синтаксис подходит для небольших проблем, но интригует то, что в статье показан синтаксис, который просто не работает. - person Paulo Buchsbaum; 03.05.2018
comment
Я отправил эту синтаксическую проблему для поддержки AMPL, они ответили 2 раза, но я думаю, что только что поняли мои сомнения. - person Paulo Buchsbaum; 03.05.2018
comment
@PauloBuchsbaum Я не тестировал версию, которую вы опубликовали, перед написанием моего ответа, но я попробовал ее сегодня утром, и единственная проблема, с которой я столкнулся, была с именем набора с учетом регистра (см. Отредактируйте мой ответ). Как только я это исправил, все заработало нормально. Так что, возможно, это сработало для автора статьи. - person Geoffrey Brent; 04.05.2018
comment
Удивительно, но служба поддержки AMPL ответила мне и дала хороший синтаксический обходной путь (я опубликовал ответ ниже). Моя версия должна быть более обновленной, чем ваша. - person Paulo Buchsbaum; 04.05.2018
comment
@PauloBuchsbaum, ага, значит, это новая ошибка в AMPL, а не в коде! Интересно, что до сих пор об этом никто не сообщил. - person Geoffrey Brent; 04.05.2018

Сегодня вечером служба поддержки AMPL дала мне ответ.

Я очень удивлен эффективностью службы поддержки AMPL!

Используя Windows, мы обнаружили, что AMPL версии 20171122 и более поздних версий отклоняют пользовательские примеры с сообщением «искаженный заголовок», но версии 20171103 и более ранние принимают примеры (включая perfectEr.mod). Мы работаем над устранением проблемы. Между тем, можно решить эту проблему, заменив "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
person Paulo Buchsbaum    schedule 04.05.2018