МПС (формат)
MPS (система математического программирования) — это формат файла для представления и архивирования задач линейного программирования (LP) и смешанного целочисленного программирования .
Обзор [ править ]
Формат был назван в честь раннего продукта IBM LP. [1] и стал де-факто стандартным носителем ASCII среди большинства коммерческих решателей LP. По существу, все коммерческие решатели LP принимают этот формат, а также он принимается системой COIN-OR с открытым исходным кодом . Для другого программного обеспечения может потребоваться специальная программа чтения для чтения файлов MPS. Однако с появлением языков алгебраического моделирования использование MPS сократилось. Например, согласно статистике сервера NEOS , в январе 2011 года менее 1% заявок было в форме MPS по сравнению с 59,4% заявок AMPL и 29,7% заявок GAMS .
MPS ориентирован на столбцы (в отличие от ввода модели в виде уравнений), и все компоненты модели (переменные, строки и т. д.) получают имена. MPS — старый формат, поэтому он настроен для перфокарт: поля начинаются со колонок 2, 5, 15, 25, 40 и 50. Разделы файла MPS отмечаются так называемыми заголовочными карточками, которые отличаются начиная со столбца 1. Хотя по историческим причинам обычно используется верхний регистр во всем файле, многие программы чтения MPS допускают смешанный регистр для всего, кроме карточек заголовков, а некоторые допускают смешанный регистр где угодно. Имена, которые вы выбираете для отдельных объектов (ограничений или переменных), не важны для решателя; следует выбирать осмысленные имена или простые имена для чтения кода постобработки.
Формат MPS [ править ]
Вот небольшой пример модели, написанной в формате MPS (более подробно описано ниже):
NAME TESTPROB
ROWS
N COST
L LIM1
G LIM2
E MYEQN
COLUMNS
XONE COST 1 LIM1 1
XONE LIM2 1
YTWO COST 4 LIM1 1
YTWO MYEQN -1
ZTHREE COST 9 LIM2 1
ZTHREE MYEQN 1
RHS
RHS1 LIM1 5 LIM2 10
RHS1 MYEQN 7
BOUNDS
UP BND1 XONE 4
LO BND1 YTWO -1
UP BND1 YTWO 1
ENDATA
Для сравнения, вот та же модель, записанная в формате, ориентированном на уравнения:
Optimize
COST: XONE + 4*YTWO + 9*ZTHREE
Subject To
LIM1: XONE + YTWO <= 5
LIM2: XONE + ZTHREE >= 10
MYEQN: - YTWO + ZTHREE = 7
Bounds
XONE <= 4
-1 <= YTWO <= 1
End
Как упоминалось ниже, нижняя граница XONE равна нулю или бесконечности, в зависимости от реализации, поскольку она не указана. Как ни странно, в формате MPS ничто не указывает направление оптимизации, и не существует стандартного направления «по умолчанию»; некоторые решатели LP максимизируют, если не указано иное, другие минимизируют, [2] а третьи ставят безопасность на первое место, не имеют значения по умолчанию и требуют выбора где-то в программе управления или с помощью вызывающего параметра. Если модель сформулирована для минимизации, а решатель требует максимизации (или наоборот), легко выполнить преобразование между ними, отрицая все коэффициенты целевой функции. Тогда оптимальное значение целевой функции будет отрицательным по отношению к исходному оптимальному значению, но значения самих переменных будут правильными. Некоторые программы поддерживают указание минимизации/максимизации в файле MPS.
OBJSENSE MAX
Переменные [ править ]
Запись NAME может иметь любое значение, начиная со столбца 15.
Раздел ROWS определяет имена всех ограничений; записи в столбце 2 или 3: E для строк равенства ( = ), L для строк меньше ( <= ), G для строк больше ( >= ) и N для строк без ограничений. Порядок строк, названных в этом разделе, неважен, за исключением неограничивающих строк, отмеченных N, первая из которых будет интерпретироваться как целевая функция.
Раздел COLUMNS содержит записи A-матрицы. Все записи данного столбца должны располагаться последовательно, хотя внутри столбца порядок записей (строк) не имеет значения. Подразумевается, что строки, не упомянутые в столбце, имеют нулевой коэффициент.
Раздел RHS позволяет определить один или несколько векторов правой части; их редко бывает больше одного. В приведенном выше примере имя вектора RHS — RHS1, и он имеет ненулевые значения во всех трех строках ограничений задачи. Предполагается, что строки, не упомянутые в векторе RHS, имеют правую часть, равную нулю.
Необязательный раздел BOUNDS определяет нижнюю и верхнюю границы отдельных переменных, если они не заданы строками в матрице. Все границы, имеющие имя в столбце 5, рассматриваются как набор. Переменные, не упомянутые в данном наборе BOUNDS, считаются неотрицательными (нижняя граница равна нулю, верхняя граница отсутствует). Граница типа UP означает, что к переменной применяется верхняя граница. Граница типа LO означает, что применяется нижняя граница. Привязанный тип FX («фиксированный») означает, что переменная имеет верхнюю и нижнюю границы, равные одному значению. Связанный тип FR («свободный») означает, что переменная не имеет ни нижней, ни верхней границы и поэтому может принимать отрицательные значения. Вариантом этого является MI для свободного отрицательного значения, дающее верхнюю границу 0, но не имеющую нижней границы. Связанный тип PL предназначен для свободного положительного значения от нуля до плюс бесконечности, но, поскольку это обычное значение по умолчанию, он используется редко. Существуют также связанные типы для использования в моделях MIP : BV для двоичного значения, равного 0 или 1. UI для верхнего целого числа и LI для нижнего целого числа. SC означает полунепрерывный и указывает, что переменная может быть нулевой, но в противном случае она должна быть равна как минимум заданному значению.
Другой необязательный раздел, называемый ДИАПАЗОНЫ, определяет двойные неравенства несколько нелогичным способом, который здесь не описан. Способы маркировки целочисленных переменных также выходят за рамки этой статьи (учитываются ключевые слова MARKER и, возможно, SOS). Последняя карта должна быть ENDATA (обратите внимание на странное написание).
Некоторые особые случаи стандарта MPS не всегда обрабатываются реализациями. В разделе BOUNDS, если переменной задана неположительная верхняя граница, но нет нижней границы, ее нижняя граница может по умолчанию быть равна нулю или минус бесконечности (кроме того, если верхняя граница задана как ноль, нижняя граница может быть нулевой или отрицательной). бесконечность). [3] Если для целочисленной переменной не указана верхняя граница, ее верхняя граница по умолчанию может быть равна единице, а не плюс бесконечности.
Ограничения [ править ]
MPS имеет множество ограничений. Он не определяет направление оптимизации, которое решатели обрабатывают по-разному. Числовые поля имеют ширину 12 символов, что ограничивает точность. Представление не является ни простым для интерпретации человеком, ни компактным (хотя сохраняет информацию о порядке столбцов/строк, что часто полезно для воспроизводимости поведения решателя LP). Одной из альтернатив MPS, которая не имеет своих ограничений и поддерживается большинством решателей, является формат файла nl .
Расширения [ править ]
Многие продукты LP включают расширения формата MPS. Свободный формат MPS позволяет использовать длинные имена и более точные данные, позволяя полям выходить за пределы столбцов, определенных исходным стандартом, и применять пробелы в качестве разделителей вместо фиксированных позиций столбцов (обратите внимание, что это приводит к тому, что некоторые файлы MPS, включающие пробелы как часть имен, уже недействителен). Некоторые расширения включают добавление новых типов данных в файл MPS (например, разделы, включающие объективный смысл, требования целостности, квадратичные данные или расширенные конструкции моделирования MIP). Существует также сжатый формат файлов MPSC. [4] ИМПС [5] — это специализированное расширение, предназначенное для представления примеров задач стохастического программирования , особенно используемое в исследовательских средах.
Хотя некоторые расширения не стандартизированы, этот формат все еще широко используется.
См. также [ править ]
- Линейное программирование
- Формат файла MPS — описание формата от авторов lp_solve
- xMPS – расширенный формат MPS.
Ссылки [ править ]
- ^ IBM, Библиотека подпрограмм оптимизации, Руководство и справочник, документ SC23-0519 , IBM [ мертвая ссылка ]
- ^ Формат файла ILOG CPLEX 10.0 (PDF) . Январь 2006. с. 28.
{{cite book}}:|work=игнорируется ( помогите ) - ^ Документ IBM CPLEX
- ^ «EMPS – Развернуть сжатый файл MPS» . People.sc.fsu.edu. 31 августа 2005 г. Архивировано из оригинала 23 декабря 2012 г. Проверено 22 января 2013 г.
- ^ «Формат SMPS для стохастических линейных программ» . Myweb.dal.ca. 11 июля 2006 г. Архивировано из оригинала 28 июня 2013 г. Проверено 28 мая 2014 г.