CPstrategier

CP-strategier är samlingsnamnet för metoder och heuristiker som används inom constraint programming (CP) för att lösa komplexa kombinatoriska problem. Målet är att effektivt pröva möjliga värden och styra sökprocessen så att antalet genererade delproblem minimeras och lösningar hittas snabbare. CP-strategier fokuserar också på hur domänerna för variabler begränsas genom constraint propagation och hur problem modelleras för att underlätta snabb heuristisk vägval.

Centrala komponenter i CP-strategier är problemmodellering, variabelval och värdeval, samt domänreducering genom constraints. Vid variabelval används heuristiker som prioriterar variabler med små domäner eller hög koppling till andra variabler. Värdeval genomförs ofta med principer som att prova värden i en ordning som snabbare leder till konfliktfria uppgifter. Detta kombineras med domänbegränsningar och propagationsregler som kontinuerligt reducerar möjliga värden när nya uppgifter fastställs.

Vanliga strategier är variabelordning (till exempel min-domain, hög koppling eller dynamisk ordning baserad på aktuella förhållanden), värdeordning (att försöka ofta mindre värden först eller utgå från stödvärden), samt användning av restarts och lärande (nogoods) för att undvika upprepade misstag. Symmetribekämpning genom brytning av symmetrier är också ett vanligt verktyg. Andra tekniker omfattar prövningstaktik som olika branching- och backtracking-strategier samt integrering av constraint propagation med andra lösningsmetoder.

CP-strategier används inom områden som schemaläggning, resursallokering, produktion och logistik, där komplexa begränsningar och många möjliga lösningar kräver effektiva sök- och filtreringsmetoder. Forskning fokuserar på adaptiva heuristiker, inlärning från tidigare sökningar och hybridisering med MILP eller SAT för att öka prestanda.