Vi överväger olika stokastiska modeller som införlivar begreppet risk-aversitet i standard 2-stegs utväg modell, och utveckla nya tekniker för att lösa de algoritmiska problem som uppstår i dessa modeller. En viktig egenskap i vårt arbete som skiljer det från arbete i några andra relaterade modeller, såsom (standard) budgetmodellen och (efterfrågan) robust modell, är att vi får resultat i svart-box-inställningen, det vill säga där man bara ges ett urval tillgång till den underliggande distributionen. Vår första modell, som vi kallar den riskaverse budgetmodellen, införlivar begreppet riskaversitet genom en probabilistisk begränsning som begränsar sannolikheten (enligt den underliggande fördelningen) med vilken den andra etappens kostnad kan överstiga en viss budget B till högst ett givet tröskelvärde ρ. Vi tar också hänsyn till en nära relaterad modell som vi kallar den riskaverse robusta modellen, där vi försöker minimera den första etappens kostnad och (1 − ρ)-kvantilen (enligt fördelningen) av den andra etappens kostnad. Vi får approximationsalgoritmer för en mängd olika kombinatoriska optimeringsproblem, inklusive set cover, vertex cover, multicut på träd, min cut, och anläggning plats problem, i risk-averse budget och robusta modeller med svart-box distributioner. Först utformar vi ett helt polynomiskt approximationssystem för att lösa LP-avslappningen av en stor variation av risk-averse budgeterade problem. Som komplement till detta ger vi ett avrundningsförfarande som låter oss använda befintliga LP-baserade approximationsalgoritmer för den 2-stegs stokastiska och/eller deterministiska motsvarigheten till problemet för att runda den fraktionerade lösningen. Därför får vi nära nog optimala lösningar på riskrelaterade problem som innebär att budgeten bevaras ungefärligt och att sannolikhetströskeln blir mindre hög (vilka båda är oundvikliga). Såvitt vi vet är detta de första approximativa resultaten för problem med probabilistiska begränsningar och black-box distributioner. Våra resultat sträcker sig till inställningen med icke-uniforma scenario-budgetar, och till en generalisering av risk-averse robust modell, där målet är att minimera summan av den första etappen kostnaden och en viktad kombination av förväntan och (1 − ρ)-kvantil av den andra etappen kostnaden.
I motsats till resultaten i REF har vi inte någon approximation i den probabilistiska begränsningen, och drifttiden för våra algoritmer är oberoende av ingångströskeln ρ.
Algorithms for Probabilistically-Constrained Models of Risk-Averse Stochastic Optimization with Black-Box Distributions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}