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 (более подробно объясненный ниже):
НАЗВАНИЕ TESTPROBРЯДЫ N СТОИМОСТЬ L LIM1 G LIM2 E MYEQNКОЛОННЫ СТОИМОСТЬ XONE 1 LIM1 1 XONE LIM2 1 YTWO COST 4 LIM1 1 YTWO MYEQN -1 Z ТРИ СТОИМОСТЬ 9 LIM2 1 ZTHREE MYEQN 1RHS RHS1 LIM1 5 LIM2 10 RHS1 MYEQN 7ОГРАНИЧЕНИЯ ВВЕРХ BND1 XONE 4 LO BND1 YTWO -1 ВВЕРХ BND1 YTWO 1ENDATA
Для сравнения, вот та же модель, записанная в формате, ориентированном на уравнения:
Оптимизировать СТОИМОСТЬ: XONE + 4 * YTWO + 9 * ZTHREEПри условии LIM1: XONE + YTWO <= 5 LIM2: XONE + ZTHREE> = 10 MYEQN: - YTWO + ZTHREE = 7Границы XONE <= 4 -1 <= YTWO <= 1Конец
Как упомянуто ниже, нижняя граница XONE равна нулю или бесконечности, в зависимости от реализации, потому что она не указана. Как ни странно, в формате MPS ничто не указывает направление оптимизации, и нет стандартного направления «по умолчанию»; некоторые решатели LP будут максимизировать, если не проинструктированы иначе, другие минимизируют [2], а третьи ставят безопасность на первое место и не имеют значения по умолчанию и требуют выбора где-то в управляющей программе или с помощью вызывающего параметра. Если модель сформулирована для минимизации, а решатель требует максимизации (или наоборот), легко выполнить преобразование между ними, отрицая все коэффициенты целевой функции. Тогда оптимальное значение целевой функции будет отрицательным по сравнению с исходным оптимальным значением, но сами значения переменных будут правильными. Некоторые программы поддерживают указание минимизации / максимизации в файле MPS.
ОБЪЕКТ МАКСИМУМ
Переменные
Запись NAME может иметь любое значение, начиная со столбца 15.
Раздел ROWS определяет имена всех ограничений; записи в столбце 2 или 3 - это E для строк равенства (=), L для строк меньше (<=), G для строк больше (> =) и N для строк без ограничений. Порядок строк, названных в этом разделе, не важен, за исключением не ограничивающих строк, отмеченных N, первая из которых будет интерпретироваться как целевая функция.
Раздел COLUMNS содержит элементы A-матрицы. Все записи для данного столбца должны быть размещены последовательно, хотя внутри столбца порядок записей (строк) не имеет значения. Строки, не упомянутые для столбца, имеют нулевой коэффициент.
Раздел RHS позволяет определить один или несколько векторов правой части; редко бывает больше одного. В приведенном выше примере имя вектора RHS - RHS1, и он имеет ненулевые значения во всех 3 строках ограничений задачи. Предполагается, что строки, не упомянутые в векторе 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] SMPS [5] - это специализированное расширение, предназначенное для представления примеров задач стохастического программирования , особенно используемых в исследовательских средах.
Хотя некоторые расширения не стандартизированы, формат все еще широко используется.
Смотрите также
- Линейное программирование
- Формат файла MPS - описание формата авторами lp_solve
- xMPS - расширенный формат MPS
Рекомендации
- ^ IBM, Библиотека подпрограмм оптимизации, Руководство и справочник, документ SC23-0519 , IBM[ мертвая ссылка ]
- ^ Форматы файлов ILOG CPLEX 10.0 (PDF) . ILOG . Январь 2006. с. 28.
- ^ Документ IBM CPLEX
- ^ «EMPS - развернуть сжатый файл MPS» . People.sc.fsu.edu. 31 августа 2005 г. Архивировано из оригинала на 2012-12-23 . Проверено 22 января 2013 .
- ^ «Формат SMPS для стохастических линейных программ» . Myweb.dal.ca. 2006-07-11. Архивировано из оригинала на 2013-06-28 . Проверено 28 мая 2014 .