Specialbeställt set

I diskret optimering är en specialordnad uppsättning (SOS) en ordnad uppsättning variabler som används som ett ytterligare sätt att specificera integralitetsvillkor i en optimeringsmodell. Specialorderuppsättningar är i grund och botten en enhet eller ett verktyg som används i förgrenade och bundna metoder för att förgrena sig på uppsättningar av variabler, snarare än enskilda variabler, som i vanlig programmering med blandade heltal . Att veta att en variabel är en del av en uppsättning och att den är ordnad ger gren- och bunden algoritm ett mer intelligent sätt att hantera optimeringsproblemet, vilket hjälper till att påskynda sökproceduren. Medlemmarna i en specialordnad uppsättning individuellt kan vara kontinuerliga eller diskreta variabler i valfri kombination. Men även när alla medlemmar själva är kontinuerliga, blir en modell som innehåller en eller flera specialordnade uppsättningar ett diskret optimeringsproblem som kräver en blandad heltalsoptimerare för sin lösning.

Den "enda" fördelen med att använda specialbeställda uppsättningar jämfört med att endast använda begränsningar är att sökproceduren i allmänhet blir märkbart snabbare. Enligt JA Tomlin tillhandahåller specialbeställningsuppsättningar ett kraftfullt sätt att modellera icke-konvexa funktioner och diskreta krav, även om det har funnits en tendens att tänka på dem endast i termer av flervals-noll-ett-programmering.

Ansökningarnas sammanhang

• Flervalsprogrammering
• Global optimering med kontinuerliga separerbara funktioner.

Historia

Upprinnelsen till konceptet var i Beales papper med titeln "Två transportproblem" (1963) där han presenterade en modell för budutvärdering. Termen introducerades emellertid först uttryckligen av Beale och Tomlin (1970). Specialorderuppsättningen implementerades först i Scicons matematiska programmeringssystem UMPIRE.

Specialorderuppsättningar var ett viktigt och återkommande tema i Martin Beales arbete, och deras värde kom att uppmärksammas till den punkt där nästan alla produktionsmatematiska programmeringssystem (MPS) implementerar någon version, eller delmängd, av SOS.

Typer av SOS

Det finns två sorters specialbeställda set:

1. Specialordnade uppsättningar av typ 1 (SOS1 eller S1): är en uppsättning variabler, varav högst en kan ha ett värde som inte är noll, alla andra är på 0. De gäller oftast där en uppsättning variabler faktiskt är 0- 1 variabler: med andra ord, vi måste välja högst en från en uppsättning möjligheter. Dessa kan uppstå till exempel när vi bestämmer vilken storlek på fabriken som ska byggas, när vi har en uppsättning alternativ, kanske liten, medelstor, stor eller ingen fabrik alls, och om vi väljer att bygga en fabrik måste vi välja en och bara en storlek.
2. Specialordnade uppsättningar av typ 2 (SOS2 eller S2): en ordnad uppsättning icke-negativa variabler, av vilka högst två kan vara icke-noll, och om två är icke-noll måste dessa vara på varandra följande i sin ordning. Specialordnade uppsättningar av typ 2 används vanligtvis för att modellera icke-linjära funktioner för en variabel i en linjär modell. De är den naturliga förlängningen av begreppen Separable Programming, men när de är inbäddade i en Branch and Bound-kod kan verkligt globala optima hittas, och inte bara lokala optima.

Ytterligare exempel

• Exempel på storlek på ett lager (exempel för SOS typ 1 från manualen för ILOG CPLEX 11.2)

Anteckningar

• Begreppet specialbeställda set introducerades av EML Beale och JA Tomlin. Särskilda faciliteter i ett allmänt matematiskt programmeringssystem för icke-konvexa problem med hjälp av ordnade uppsättningar av variabler. I J. Lawrence, redaktör, Operational Research 69, sidorna 447–454. Tavistock Publishing, London, 1970.
• EML Beale och JJH Forrest. Global optimering med specialbeställda set. Matematisk programmering, 10(1):52–69, 1976.
• "Specialbeställda set och en applikation för driftplanering av gasförsörjning", JA Tomlin, Ketron Management Science, Inc., Mountain View, CA 94040-1266, USA
•   Christelle Gueret, Christian Prins, Marc Sevaus, "Applications of optimization with Xpress-MP" , Editions Eyrolles, Paris, France (2000), ISBN 0-9543503-0-8 , pag 39-42