Перейти к содержанию

Форматы файлов

В ArhiCloud поддерживаются три основных формата файла.

Форматы .lp, .mps - форматы записи моделей в файл для последующего хранения и использования.

Формат .sol - файл решения. Используется для записи решения задачи в файл и использования его далее, например, в качестве начального решения в других задачах.

LP

LP формат предоставляет возможность ввода задачи в естественной алгебраической формулировке. Задачу можно изменить и сохранить из солверов. Эта процедура является одним из способов создания файла в формате, который могут читать различные солверы.

Формат LP может представлять не только линейное программирование (LP), но и смешанное целочисленное программирование (MIP).

Формат LP предоставляется в качестве входной альтернативы формату файлов MPS. Файл формата LP проще создать, чем файл MPS, если ваша задача уже существует в алгебраическом формате или если у вас есть приложение, которое создает файл задачи.

Длина строки

Максимальная длина любого имени — 255 символов. Максимальная длина любой строки — 560 символов.

Комментарии

Все, что следует за обратной косой чертой \, является комментарием и игнорируется, пока не встретится перенос строки. Пустые строки также игнорируются. Пустые строки и строки комментариев могут быть размещены в любом месте любое число раз.

Пробелы

Пробелы между символами не имеют значения, при чтении файла они пропускаются. Пробелы не допускаются в ключевых словах, используемых для введения нового раздела, таких как MAX, MIN, ST или BOUNDS. Также ключевые слова должны быть отделены пробелом от остальной части файла и должны находиться в начале строки.

Пропуск пробелов может привести к тому, что солвер неправильно интерпретирует запись, например следующую:

x1 x2 = 0

Если бы Пользователь намеревался ввести этот пример как нелинейное ограничение, солвер вместо этого интерпретирует его как ограничение, указывающее, что одна переменная с названием x1x2 должна быть равна нулю.

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

Направление оптимизации

Для указания направления оптимизации формулировка задачи должна начинаться со слова MINIMIZE или MAXIMIZE, MINIMUM или MAXIMUM, или аббревиатуры MIN или MAX, в любой комбинации символов верхнего и нижнего регистра. Эти ключевые слова начинают раздел целевой функции.

Наименования переменных

Переменные могут иметь любое имя при условии, что имя не превышает 255 символов, все из которых должны быть буквенно-цифровыми (a-z, A-Z, 0-9) или одним из следующих символов: ! " # $ % & ( ) , . ; ? @ _ ' ' { } ~. Более длинные имена усекаются до 255 символов. Имя переменной не может начинаться с цифры или точки.

Букву E или e, отдельно или за которой следуют другие допустимые символы, следует избегать, так как это обозначение зарезервировано для экспоненциальных записей. Таким образом, переменные не могут называться e9, E-24, E8cats или другими именами, которые можно интерпретировать как показатель степени. Даже имена переменных, такие как eels или, example могут вызвать ошибку чтения, в зависимости от их размещения в строке файла.

Хорошая практика

Имена переменных начинаются с буквы (кроме E или e) или с символа подчеркивания.

Целевая функция

Определение целевой функции должно следовать после слов MINIMIZE или MAXIMIZE. Целевую функцию можно ввести в несколько строк, если ни одна переменная, константа не разделены символом новой строки. Например, целевую функцию 1x1 + 2x2 + 3x3 можно ввести так:

1x1 + 2x2
+ 3x3

но не так:

1x1 + 2x
2 + 3x3

Целевая функция может быть поименована путем ввода имени целевой функции и двоеточия перед самой целевой функцией. Имя целевой функции и двоеточие должны стоять в одной строке. Имена целевых функций должны соответствовать тем же рекомендациям, что и имена переменных (см. правило об именах переменных).

Если имя целевой функции не указано, солвер присваивает имя obj.

Смещение целевой функции

Вы можете дополнительно включить смещение в качестве конечного постоянного члена в целевую функцию. Например, следующая строка объявляет целевое смещение 3.1415.

obj:  x1 + 2 x2 + 3.1415

Точно так же целевое смещение следует за любыми квадратичными выражениями в формате файла LP квадратичной программы, например, в следующей строке:

obj: x + 2 y + [ x ^2 - 3 x * y ] / 2 + 3.1415

Ограничения

Раздел ограничений вводится ключевым словом subjectto. Это выражение также может отображаться как suchthat, st, S.T. или ST. в любой комбинации символов верхнего и нижнего регистра. Любое из этих выражений должно предшествовать первому ограничению и отделяться от него хотя бы одним пробелом.

Каждое определение ограничения должно начинаться с новой строки. Ограничение может быть названо путем ввода имени и двоеточия перед самим выражением ограничения. Имя ограничения и двоеточие должны стоять в одной строке. Имена ограничений должны соответствовать тем же правилам, что и имена переменных (см. правило об именах переменных). Если имена ограничений не указаны, солвер присваивает имена c1, c2, c3, и т.д.

Ограничения вводятся так же, как и целевая функция; однако за ограничением должно следовать указание его направления и коэффициент (правая часть). Правая часть должна быть напечатана в той же строке, что и направление ограничения. Приемлемыми направлениями ограничений являются <, <=, =<, >, >=, => и =. Они интерпретируются как ≤, ≤, ≤, ≥, ≥, ≥ и = соответственно.

Например, вот именованное ограничение:

time: x1 + x2 <= 10

Также, разрешены квадратичные ограничения. Квадратичные выражения указываются в квадратных скобках [], как указано в правиле о квадратичных выражениях. Спецификация квадратичного ограничения отличается от спецификации квадратичной целевой функции одним важным моментом: в квадратичном ограничении члены не делятся на два, то есть они не умножаются на 1/2, как это должно быть в квадратичной целевой функции.

Границы

Необязательный раздел (bounds) следует за разделом ограничений. Ему предшествует слово bounds или bound любое сочетание строчных и прописных символов.

Каждое определение должно начинаться с новой строки. Формат границы следующий: lb ≤ xn ≤ ub, за исключением следующих случаев.Верхняя и нижняя границы также могут быть введены отдельно, как

lb ≤ xn
xn ≤ ub

с нижней границей по умолчанию, равной 0 (нулю), и верхней границей по умолчанию, равной +∞, которая остается в силе до тех пор, пока граница не будет явно изменена.

Границы, фиксирующие переменную, можно вводить в виде простых равенств. Например, x5 = 5.6 эквивалентно `5.6 <= x5 <= 5.6.

Границы +∞ (положительная бесконечность) и -∞ (отрицательная бесконечность) должны быть введены как слова: +infinity, -infinity, +inf, -inf.

Переменная с нижней границей, равной отрицательной бесконечности, и верхней границей, равной положительной бесконечности, может быть введена как free, в любом сочетании символов верхнего и нижнего регистра, с пробелом, разделяющим имя переменной и слово free. Например, x7 free эквивалентно infinity <= x7 <= + infinity.

Последняя введенная граница имеет приоритет над ранее введенными границами.

Конец файла

LP файл должен заканчиваться ключевым словом end в любой комбинации символов верхнего и нижнего регистра, в отдельной строке.

Особенности MIP

Целочисленные переменные

Перечень целочисленных переменных приводится в разделе GENERAL, а бинарные - в разделе BINARY. Данные разделы следуют после раздела BOUNDS, либо после раздела ограничений, если BOUNDS отсутствует.

Раздел GENERAL начинается со слова GENERAL, GENERALS или GEN в любой комбинации символов верхнего и нижнего регистра. В следующей строке или строках должны быть перечислены имена всех переменных, которые должны быть ограничены общими целочисленными значениями, разделенные хотя бы одним пробелом.

Раздел BINARY начинается со слова BINARY, BINARIES или BIN в любой комбинации символов верхнего и нижнего регистра. В следующих строках должны быть перечислены имена всех переменных, которые должны быть ограничены двоичными целыми значениями, разделенные хотя бы одним пробелом.

Пример

Maximize
 obj: x1 + 2 x2 + 3 x3 + x4
Subject To
 c1: - x1 + x2 + x3 + 10 x4 <= 20
 c2: x1 - 3 x2 + x3 <= 30
 c3: x2 - 3.5 x4 = 0
Bounds
 0 <= x1 <= 40
 2 <= x4 <= 3
General
 x4
End

Особенности квадратичных задач

Данный раздел описывает особенности задач с квадратичными членами, то есть квадратичные задачи программирования или с квадратичными ограничениями (QP, QCP, MIQP, MIQCP). Квадратичные коэффициенты могут появляться в целевой функции и в ограничениях.

В квадратных скобках ([]) указаны алгебраические коэффициенты функции За квадратными скобками должен следовать знак деления (/), за которым следует число 2. Это означает, что все коэффициенты внутри квадратных скобок будут делиться на 2 при оценке квадратичных членов целевой функции. Все квадратичные коэффициенты должны быть заключены в квадратные скобки.

Для записи произведения недиагональных членов матрицы Q используется символ звездочки (*). Например, [4x * y] указывает, что коэффициенты обоих недиагональных членов Q, соответствующих переменным x и y в модели, равны 2, поскольку 4x * y равны 2x * y + 2x * y. Каждая пара недиагональных членов Q указывается только один раз. Солвер автоматически создает обе недиагональные записи Q.

Диагональные члены в Q (то есть члены с показателем степени 2) обозначаются знаком (^), за которым следует цифра 2. Например, 4x^2, указывает, что коэффициент диагонального члена Q соответствующий переменной x равен 4.

Пример

В качестве примера приведём задачу миминизации функции при условии a + b ≥ 10 и a, b ≥ 0

Запись в формате LP выглядит следующим образом.

Minimize
obj: a + b + [a^2 + 4 a * b + 7 b^2]/2
Subject To
c1: a + b >= 10
End

MPS

Формат MPS — это старейший и наиболее широко используемый формат для хранения моделей математического программирования. Существует два широко используемых варианта этого формата. В фиксированном формате различные поля всегда должны начинаться с фиксированных столбцов в файле. Свободный формат очень похож на фиксированный, но поля разделяются пробелами, а не располагаются в определённых столбцах. Одно важное практическое различие между этими двумя форматами заключается в длине имён. В фиксированном формате имена строк и столбцов состоят ровно из 8 символов, а пробелы являются частью имени. В свободном формате имена могут быть произвольно длинными, и в именах не должно быть пробелов.

ArhiPlex и ArhiCloud поддерживают чтение MPS файлов, построенных с общепринятыми правилами. Со спецификацией файлов формата MPS можно ознакомиться на следующих ресурсах:

  1. Wikipedia
  2. Gurobi Doc Center
  3. plato.asu.edu

SOL

Сохранение и загрузка решения оптимизационной задачи в ArhiPlex и в ArhiCloud осуществляется через файлы формата sol. Структура файла *.sol достаточно простая - осуществляется перечисление всех наименований переменных и их значение.

Файл состоит из пар «переменная-значение», каждая из которых находится в отдельной строке. Файл содержит по одной строке для каждой переменной в модели. Ниже приведён простой пример:

# Arhiplex Solution File Version 1.1

# Columns  1758
x1757              82.00000000000000
x1756             119.00000000000000
x1754             111.00000000000000
x1753              26.00000000000000
x1751              60.00000000000000
x1749              12.00000000000000
x1746              99.00000000000000
x1745             153.00000000000000
x1744              14.00000000000000
x1739             135.00000000000000
x1738             108.00000000000000
x1736             174.00000000000000
...