MPS(형식)

MPS (format)

MPS(Mathematical Programming System)는 선형 프로그래밍(LP)과 혼합 정수 프로그래밍 문제를 제시하고 보관하기 위한 파일 형식입니다.

개요

2011년 1월의 NEOS 입력 통계.

이 포맷은 초기 IBM LP[1] 제품의 이름을 따 지어졌으며 대부분의 상용 LP 솔버들 사이에서 사실상의 표준 ASCII 미디어로 부상했습니다.기본적으로 모든 시판 LP 솔버는 이 형식을 수용하며, 오픈 소스 COIN-OR 시스템에서도 이 형식을 수용합니다.다른 소프트웨어에서는 MPS 파일을 읽기 위해 맞춤 리더 루틴이 필요할 수 있습니다.그러나 대수 모델링 언어의 수용으로 MPS 사용은 감소했습니다.예를 들어, 2011년 1월의 NEOS 서버 통계에 따르면, MPS 형식의 제출은 1% 미만이었습니다.이에 비해, AMPR의 59.4%, GAMS의 29.7%가 제출되었습니다.

MPS는 모형을 방정식으로 입력하는 것이 아니라 열 지향이며 모든 모형 성분(변수, 행 등)이 이름을 받습니다.MPS는 오래된 형식이기 때문에 펀치카드용으로 설정되어 있습니다.필드는 2, 5, 15, 25, 40 및 50 열에서 시작합니다.MPS 파일의 각 섹션은 이른바 헤더카드로 마크되어 있습니다.이러한 카드는 열 1에서 시작하는 것으로 구분됩니다.이력상의 이유로 파일 전체에서 대소문자를 사용하는 것이 일반적이지만, 많은 MPS 리더에서는 헤더 카드 이외의 모든 것에 대해 대소문자를 사용할 수 있습니다.또, 임의의 장소에서 대소문자를 사용할 수 있는 것도 있습니다.개별 엔티티에 대해 선택한 이름(제한조건 또는 변수)은 솔버에게 중요하지 않습니다.따라서 의미 있는 이름 또는 읽기 쉬운 이름을 선택해야 합니다.

MPS 형식

다음은 MPS 형식으로 작성된 샘플 모델입니다(자세한 내용은 아래에 설명되어 있습니다). 

이름 테스트 PROB 열 N 비용 L LIM1 G LIM2 E MYEQN 열 XONE 비용 1 LIM1 1 XONE LIM2 1 Y2 비용 4 LIM1 - 1 Z3 비용 9 MYEQN - 1 Z3QN 1 RHS1 LIM1 5 LIM2 10 RHS1 MYEQN 7 bounds up BND1 XONE 4 LO BND1 YTwo - 1 Up BND1 YT2 1 EndATA

비교를 위해 방정식 지향 형식으로 작성된 동일한 모델을 다음에 나타냅니다.

비용 최적화: XONE + 4*YTWO + 9*ZTIOL 대상: XONE + YTWORY <= 5 LIM2: XONE + ZTHIRE>= 10MYEQN: - Y2 + Z3 = 7 Bounds XONE < - 1 = Y1 >

이하와 같이 XONE의 하한은 지정되어 있지 않기 때문에 실장에 따라 제로 또는 -infinity 중 하나입니다.이상하게도 MPS 형식에서는 최적화의 방향을 지정하는 것은 아무것도 없고 표준적인 "기본" 방향도 없습니다.일부 LP 솔버는 특별히 지시하지 않으면 최대가 되고,[2] 다른 LP 솔버는 안전을 최우선으로 하며, 다른 LP 솔버는 기본값이 없으며, 제어 프로그램 내 어딘가에서 또는 호출 파라미터에 의한 선택이 필요합니다.모델이 최소화를 위해 공식화되고 솔버가 최대화를 필요로 하는 경우(또는 그 반대도 마찬가지), 목적 함수의 모든 계수를 부정함으로써 둘 사이를 쉽게 변환할 수 있습니다.그러면 목표 함수의 최적 값은 원래 최적 값의 음수가 되지만 변수 자체의 값은 정확합니다.일부 프로그램에서는 MPS 파일 내에서 최소화/최대화를 지정할 수 있습니다. 

OBJSENSE MAX

변수

NAME 레코드에는 열 15부터 시작하는 값을 지정할 수 있습니다.

ROWS 섹션은 모든 제약조건의 이름을 정의합니다.열 2 또는 3의 항목은 등식(= ) 행의 경우 E, 미만(=) 행의 경우 L, 보다 큰(>=) 행의 경우 G, 비제한 행의 경우 N입니다.이 절에서 명명된 행의 순서는 N으로 표시된 구속되지 않은 행을 제외하고 중요하지 않습니다. 단, 첫 번째 행은 목적 함수로 해석됩니다.

COLUMNS 섹션에는 A 행렬의 항목이 포함됩니다.지정된 열의 모든 항목은 연속해서 배치해야 합니다. 단, 열 내에서 항목(행)의 순서는 관련이 없습니다.열에 대해 언급되지 않은 행은 계수가 0임을 암시합니다.

RHS 섹션에서는 1개 이상의 우측 벡터를 정의할 수 있습니다.단, 1개 이상의 벡터가 있는 경우는 거의 없습니다.위의 예에서 RHS 벡터의 이름은 RHS1이며 문제의 3개 제약행 모두에 0이 아닌 값이 있습니다.RHS 벡터에서 언급되지 않은 행은 오른쪽이 0인 것으로 간주됩니다.

선택적 BANGES 섹션은 개별 변수가 행렬의 행에 의해 지정되지 않은 경우 해당 변수의 하한과 상한을 지정합니다.열 5에 지정된 이름을 가진 모든 경계가 세트로 취합됩니다.주어진 경계 집합에 언급되지 않은 변수는 음이 아닌 것으로 간주됩니다(하한 0, 상한 없음).UP 유형의 경계는 변수에 상한이 적용됨을 의미합니다.타입 LO의 경계는 하한이 적용됨을 의미합니다.FX의 바인딩 유형("고정")은 변수의 상한과 하한이 단일 값과 같다는 것을 의미합니다.FR("자유")의 바운드는 변수에 하한도 상한도 없으므로 음수 값을 취할 수 있음을 의미합니다.이 값의 변동은 자유 음수에 대한 MI이며, 상한은 0이지만 하한은 없습니다.바운드 타입 PL은 0에서 무한까지의 자유 양수이지만, 이것은 통상적인 디폴트이기 때문에 거의 사용되지 않습니다.MIP 모델에는 BV(바이너리), 0 또는 1(상위 정수의 경우 UI, 하위 정수의 경우 LI)과 같은 바인딩된 유형도 있습니다.SC는 반연속형(semi-continuous)의 약자로 변수가 0일 수 있지만 그렇지 않을 경우 적어도 지정된 값과 같아야 함을 나타냅니다.

RANGES라고 하는 또 다른 옵션 섹션은 여기서 설명하지 않은 다소 반직관적인 방법으로 이중 비등밀도를 지정합니다.정수 변수를 표시하는 방법도 이 문서의 범위를 벗어납니다(키워드 MARKER 및 SOS가 포함될 수 있음).마지막 카드는 ENDATA여야 합니다(홀수 철자에 주의).

MPS 표준의 몇 가지 특수한 케이스는 구현에 의해 일관되게 처리되지 않습니다.BANGES 섹션에서 변수에 양수 상한이 지정되지만 하한이 지정되지 않은 경우 해당 하한이 기본적으로 0 또는 마이너스 무한대로 설정될 수 있습니다(또한 상한이 0으로 지정되면 하한은 0 또는 [3]음수 무한이 될 수도 있습니다.정수 변수에 상한이 지정되지 않은 경우 해당 상한은 기본적으로 무한이 아닌 1로 설정될 수 있습니다.

제한 사항

MPS에는 많은 제한이 있습니다.솔버에 의해 다르게 처리되는 최적화의 방향을 지정하지 않습니다.숫자 필드의 너비는 12자이므로 정밀도가 제한됩니다.이 표현은 인간의 해석에 용이하지 않고 콤팩트하지 않다(단, 열/행 순서 정보가 저장되므로 LP 솔버 행동 재현성에 도움이 되는 경우가 많다.제한이 없고 대부분의 솔버에서 지원되는 MPS 대체 방법 중 하나는 nl 파일 형식입니다.

내선번호

많은 LP 제품에는 MPS 형식의 확장이 포함되어 있습니다.자유 형식 MPS를 사용하면 필드가 원래 표준에 의해 정의된 열을 초과할 수 있으므로 긴 이름과 보다 정확한 데이터를 사용할 수 있습니다.또한 고정된 열 위치 대신 공백 공간을 구분자로 적용할 수 있습니다(이 때문에 이름의 일부로 공백 공간을 포함했던 일부 MPS 파일은 더 이상 유효하지 않습니다).일부 확장 기능에는 MPS 파일에 새로운 종류의 데이터를 추가하는 것이 포함된다(예: 객관적 감각, 통합성 요건, 2차 데이터 또는 고급 MIP 모델링 구조를 포함하는 섹션).압축된 MPSC 파일 [4]형식도 있습니다.SMPS는[5] 특히 연구 환경에서 사용되는 확률적 프로그래밍 문제 인스턴스를 나타내도록 설계된 특수 확장입니다.

일부 확장자는 표준화되지 않았지만 형식은 여전히 일반적으로 사용됩니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ IBM, Optimization Subroutine Library, Guide and Reference, document SC23-0519, IBM[데드링크]
  2. ^ ILOG CPLEX 10.0 File Formats (PDF). ILOG. January 2006. p. 28.
  3. ^ IBM CPLEX 문서
  4. ^ "EMPS – Expand a compressed MPS file". People.sc.fsu.edu. 2005-08-31. Archived from the original on 2012-12-23. Retrieved 2013-01-22.
  5. ^ "The SMPS format for stochastic linear programs". Myweb.dal.ca. 2006-07-11. Archived from the original on 2013-06-28. Retrieved 2014-05-28.