MPS (format)

MPS (Mathematical Programming System) är ett filformat för att presentera och arkivera linjär programmering (LP) och blandade heltalsprogrammeringsproblem .

Översikt

NEOS indatastatistik för januari 2011.

Formatet fick sitt namn efter en tidig IBM LP-produkt och har dykt upp som ett de facto-standard ASCII- medium bland de flesta kommersiella LP-lösare. I princip alla kommersiella LP-lösare accepterar detta format, och det accepteras också av COIN-OR- systemet med öppen källkod. Annan programvara kan kräva en anpassad läsarrutin för att kunna läsa MPS-filer. Men med acceptansen av algebraiska modelleringsspråk har MPS-användningen minskat. Till exempel, enligt NEOS- serverstatistiken i januari 2011 var mindre än 1 % av bidragen i MPS-form jämfört med 59,4 % av AMPL och 29,7 % av GAMS -inlämningarna.

MPS är kolumnorienterat (i motsats till att skriva in modellen som ekvationer), och alla modellkomponenter (variabler, rader, etc.) får namn. MPS är ett gammalt format, så det är inställt för hålkort: Fälten börjar i kolumn 2, 5, 15, 25, 40 och 50. Delar av en MPS-fil är markerade med så kallade header-kort, som kännetecknas av sina med början i kolumn 1. Även om det är typiskt att använda versaler i hela filen av historiska skäl, accepterar många MPS-läsare blandade versaler för allt utom huvudkorten, och vissa tillåter blandade versaler var som helst. Namnen som du väljer för de enskilda entiteterna (begränsningar eller variabler) är inte viktiga för lösaren; man bör välja meningsfulla namn, eller lätta namn för en efterbearbetningskod att läsa.

MPS-format

Här är en liten exempelmodell skriven i MPS-format (förklaras mer detaljerat nedan):

NAMN TESTPROB RADER N KOSTNAD L LIM1 G LIM2 E MYEQN KOLUMNER XONE KOSTNAD 1 LIM1 1 XONE LIM2 1 YTWO KOSTNAD 4 LIM1 1 YTWO MYEQN -1 ZTREE KOSTNAD 9 LIM2 1 ZTHREE MYEQN 1 RHS0 RHSIM RHS1 MYQN 7 1 XONE 4 LO BND1 YTWO -1 UPP BND1 YTWO 1 ENDATA

För jämförelse, här är samma modell skriven i ett ekvationsorienterat format:

Optimera KOSTNAD: XONE + 4*YTWO + 9*ZTHREE Med förbehåll för LIM1: XONE + YTWO <= 5 LIM2: XONE + ZTHREE >= 10 MYEQN: - YTWO + ZTHREE = 7 Gränser XONE <= 4 -1 <= YTWO <= 1 Slut

Som nämnts nedan är den nedre gränsen för XONE antingen noll eller -oändlighet, beroende på implementering, eftersom den inte är specificerad. Konstigt nog specificerar ingenting i MPS-format riktningen för optimeringen, och det finns ingen standard "standard"-riktning; vissa LP-lösare kommer att maximera om de inte instrueras på annat sätt, andra kommer att minimera, och ytterligare andra sätter säkerheten först och har ingen standard och kräver ett val någonstans i ett kontrollprogram eller av en anropsparameter. Om modellen är formulerad för minimering och lösaren kräver maximering (eller vice versa), är det lätt att konvertera mellan de två genom att negera alla koefficienter för objektivfunktionen. Det optimala värdet för objektivfunktionen blir då det negativa av det ursprungliga optimala värdet, men själva variablernas värden blir korrekta. Vissa program stöder specificering av minimering/maximering i MPS-filen.

OBJSENSE MAX

Variabler

NAME-posten kan ha vilket värde som helst, med början i kolumn 15.

Sektionen ROWS definierar namnen på alla begränsningar; poster i kolumn 2 eller 3 är E för likhetsrader ( = ), L för rader som är mindre än ( <= ), G för rader större än ( >= ) och N för rader som inte är begränsande. Ordningen på raderna som nämns i detta avsnitt är oviktig, förutom för icke-begränsande rader markerade N, av vilka den första skulle tolkas som den objektiva funktionen.

Sektionen KOLUMNER innehåller posterna i A-matrisen. Alla poster för en given kolumn måste placeras i följd, även om ordningen på posterna (raderna) är irrelevant inom en kolumn. Rader som inte nämns för en kolumn antyds ha en koefficient på noll.

RHS-sektionen tillåter att en eller flera vektorer på höger sida definieras; det är sällan mer än en. I exemplet ovan är namnet på RHS-vektorn RHS1 och har värden som inte är noll i alla tre begränsningsraderna i problemet. Rader som inte nämns i en RHS-vektor skulle antas ha en högersida av noll.

Det valfria avsnittet GRÄNSER anger nedre och övre gränser för enskilda variabler, om de inte ges av rader i matrisen. Alla gränser som har ett förnamn i kolumn 5 tas tillsammans som en mängd. Variabler som inte nämns i en given BOUNDS-uppsättning anses vara icke-negativa (nedre gränsen noll, ingen övre gräns). En gräns av typen UP betyder att en övre gräns tillämpas på variabeln. En gräns av typen LO betyder att en nedre gräns tillämpas. En bunden typ av FX ("fixed") betyder att variabeln har övre och nedre gränser lika med ett enda värde. En bunden typ av FR ("fri") betyder att variabeln varken har lägre eller övre gränser och kan därför anta negativa värden. En variant på det är MI för fri negativ, vilket ger en övre gräns på 0 men ingen nedre gräns. Bunden typ PL är för en fri positiv från noll till plus oändlighet, men eftersom detta är den normala standarden används den sällan. Det finns också bundna typer för användning i MIP- modeller – BV för binär, är 0 eller 1. UI för övre heltal och LI för lägre heltal. SC står för semi-kontinuerlig och indikerar att variabeln kan vara noll, men om inte måste vara lika med åtminstone det angivna värdet.

Ett annat valfritt avsnitt som heter RANGES specificerar dubbla ojämlikheter, på ett något kontraintuitivt sätt som inte beskrivs här. Sätt att markera heltalsvariabler ligger också utanför ramen för denna artikel (sökord MARKER och eventuellt SOS är inblandade). Det sista kortet måste vara ENDATA (lägg märke till den udda stavningen).

Ett fåtal specialfall av MPS-standarden hanteras inte konsekvent av implementeringar. I avsnittet GRÄNSER, om en variabel ges en icke-positiv övre gräns men ingen nedre gräns, kan dess nedre gräns som standard vara noll eller till minus oändlighet (även, om den övre gränsen ges som noll, kan den nedre gränsen vara noll eller negativ oändlighet). Om en heltalsvariabel inte har någon övre gräns specificerad, kan dess övre gräns som standard vara ett snarare än till plus oändlighet.

Begränsningar

MPS har många begränsningar. Den specificerar inte optimeringsriktningen som hanteras olika av lösare. Numeriska fält har 12 teckens bredd vilket begränsar precisionen. Representationen är varken lätt för mänsklig tolkning eller kompakt (även om kolumn-/radordningsinformation reserveras, vilket ofta är fördelaktigt för reproducerbarheten av LP-lösarens beteende). Ett av alternativen till MPS som inte har sina begränsningar och som stöds av de flesta lösare är filformatet nl .

Tillägg

Många LP-produkter inkluderar tillägg till MPS-formatet. Det fria formatet MPS tillåter långa namn och mer exakta data genom att tillåta fält att överskrida kolumnerna definierade av den ursprungliga standarden, och använda blanksteg som avgränsare istället för fasta kolumnpositioner (observera att detta gör vissa MPS-filer som inkluderade blanksteg som en del av namnen inte längre är giltig). Vissa tillägg inkluderar att lägga till nya typer av data till MPS-filen (t.ex. sektioner för att inkludera objektiv känsla, integralitetskrav, kvadratisk data eller avancerade MIP-modelleringskonstruktioner). Det finns också ett komprimerat MPSC-filformat. SMPS är en specialiserad tillägg, designad för att representera med stokastiska programmeringsproblem , som används speciellt i forskningsmiljöer.

Även om vissa tillägg inte är standardiserade är formatet fortfarande i allmänt bruk.

Se även

Hämtad från " https://en.wikipedia.org/w/index.php?title=MPS_(format)&oldid=1058526517 "