Vi anser att en bred klass av stokastiska dynamiska programmeringsproblem som är mottagliga för avslappning via nedbrytning. Dessa problem omfattar flera underproblem som är oberoende av varandra, med undantag för en samling av kopplingsbegränsningar på åtgärdsområdet. Vi passar en additivt separat värde funktion approximation med hjälp av två tekniker, nämligen Lagrangian avkoppling och linjär programmering (LP) för att ungefärlig dynamisk programmering. Vi visar olika resultat som jämför avkopplingarna med varandra och det optimala problemvärdet. Vi tillhandahåller också en kolumngenereringsalgoritm för att lösa LP-baserad avslappning till önskad optimalitetstolerans, och vi rapporterar om numeriska experiment på banditliknande problem. Våra resultat ger insikt i komplexitet kontra kvalitet kompromiss när du väljer vilken av dessa avkopplingar att genomföra.  Ett klassiskt resultat i heltal programmering, på grund av Geoffrion (1974), relaterar det optimala objektiva värdet av Lagrangian dual med den linjära programmering (LP) avkoppling. Överväga ett heltal program som maximerar en linjär objektiv funktion över linjära begränsningar som kan delas in i två grupper: så kallade "lätta" begränsningar, och "kompletterande" begränsningar. Idén med Lagrangian avkoppling är att dubblera de komplicerande begränsningar med en straff vektor, dvs lägga till termer till den objektiva funktionen bestraffa begränsningar överträdelser, och sedan optimera den resulterande objektiva funktionen över de återstående "lätta" begränsningar. För alla straff vektor, detta ger en övre gräns på det optimala objektiva värdet av heltalsprogrammet, z IP. Den Lagrangian dubbla minimerar över för att hitta den minsta övre gränsen, z LD. Ett resultat av Geoffrion (1974) innebär att där z LP är det optimala objektiva värdet av LP avslappning av heltalsprogrammet. Detta resultat ger en viktig motivering för att överväga Lagrangian avkopplingar av heltalsprogram, och Geoffrion's (1974) arbete banade vägen för många papper (Fisher 1981 ) som använde Lagrangian strategi. Under de senaste åren har det funnits ett stort forskningsintresse för att lösa stokastiska dynamiska optimeringsproblem. Eftersom statiska, deterministiska speciella fall av dessa problem kan verkligen vara heltal program, klassen av stokastiska dynamiska optimeringsproblem är minst lika svårt att lösa som klassen av heltal program. Även om dynamiska optimeringsproblem i teorin kan lösas med hjälp av exakt dynamisk programmering (Bellman 1957), visar detta sig vara svåråtkomligt för många problem i praktiken, på grund av den så kallade "dimensionalitetens förbannelse". Även om problemen på detta område är av stort praktiskt intresse, finns det för närvarande en brist på teori för att vägleda utövaren. Konkurrerande tekniker finns i överflöd, och praktisk dynamisk optimering kräver ofta problemspecifika metoder. Olika förslag har lagts fram för att bryta förbannelsen, som alla faller under rubriken "tillnärmelsevis dynamiska programplaneringsmetoder". Men hittills finns det inget resultat som (1) som jämför avkopplingar. Syftet med denna uppsats är att undersöka ett liknande resultat för två avkopplingar av en särskild klass av sådana stokastiska, dynamiska optimeringsproblem, som kallas svagt kopplade dynamiska program. 1 Sådana problem bryts ner i oberoende dynamiska program, eller subproblem, med undantag för en uppsättning länkande begränsningar för åtgärderna. När dessa begränsningar är svaga, förväntar vi oss att avkopplingarna är nära det ursprungliga problemet. Hawkins (2003) beskriver många praktiska problem som passar denna struktur, bland annat de som uppstår i supply chain management, flerklassiga könät, auktioner och andra. Exempel på detta är: • Multiarmade och rastlösa banditproblem. Det rastlösa banditproblemet (Wistle 1988) är en klassisk resurs 712
REF fokuserar på stokastiska dynamiska programmeringsproblem som är lämpliga för avkoppling via nedbrytning.
Relaxations of Weakly Coupled Stochastic Dynamic Programs
{'venue': 'Oper. Res.', 'journal': 'Oper. Res.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}