Värdesatt begränsningsproblem (VCSP) är ett generiskt optimeringsproblem som definieras av ett nätverk av lokala kostnadsfunktioner som definieras över diskreta variabler. Den har tillämpningar inom artificiell intelligens, operativ forskning, bioinformatik och har använts för att hantera optimeringsproblem i andra grafiska modeller (inklusive diskreta Markov Random Fields och Bayesian Networks). De inkrementella nedre gränserna som produceras genom lokal konsistensfiltrering används för beskärning inne i Branch och Bound sökning. I detta dokument utvidgar vi begreppet bågkonsistens genom att tillåta fraktionerade vikter och genom att tillåta att flera bågkonsistenser tillämpas samtidigt. Över rationella och tillåter samtidiga operationer, visar vi att en optimal båge konsistens stängning teoretiskt kan bestämmas i polynom tid genom minskning till linjär programmering. Detta definierar Optimal Soft Arc-konsistens (OSAC). För att nå en mer praktisk algoritm, visar vi att förekomsten av en sekvens av bågkonsistens operationer som ökar den nedre gränsen kan upptäckas genom att etablera båge konsistens i en klassisk Restrikt tillfredsställelse problem (CSP) som härrör från den ursprungliga kostnadsfunktionsnätverket. Detta leder till en ny mjuk båge konsistens metod, kallas,Virtual Arc konsekvens som producerar förbättrade lägre gränser jämfört med tidigare tekniker och som kan lösa submodulära kostnadsfunktioner. Dessa algoritmer har implementerats och utvärderats på en mängd olika problem, bland annat två svåra frekvenstilldelningsproblem som är lösta till optimalitet för första gången. Vår implementation finns tillgänglig i plattformen open source toulbar2.
Anpassningsvikter för att förbättra utbredningen har också tillämpats inom ramen för värdesatt begränsningsproblem REF.
Soft arc consistency revisited
{'venue': 'Artificial Intelligence', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}