Utvärdering av ´lazy clause generation´ för konfigureringsproblem

Syfte och mål

Nyligen har en ny teknik för att effektivisera sökning presenterats som har givit imponerade resultat på problem som liknar de konfigureringsproblem som kräver prestandatrimning idag. Tanken med projektet var att testa den nya tekniken på riktiga konfigureringsproblem för att se om resultaten blir lika imponerade där.

Resultat och förväntade effekter

Tyvärr pekade testerna på att huvuddelen av tekniken inte är lämplig för konfigureringsproblem pga den extra OH den skapar. Däremot identifierade vi delar av tekniken som ger effekt utan OH och som ganska enkelt kan införas. Prestandaförbättringarna blev inte så stora men även mindre förbättringar är värdefulla för Tacton.

Upplägg och genomförande

Följande steg genomfördes: 1. Problemanalys. Identifikation av typiska scenarios i TC där sökningen är en beräkningsmässig flaskhals. Urval av representativa instanser av dessa scenarios för experimenten. 2. Dataanpassning. Utveckling av en översättare från delproblem av Tactons modeller till MiniZinc. övrig anpassning till G12 och/eller lazy clause generation. 3. Experimentfas. Experimentell utvärdering av G12 med lazy clause generation på de valda instanserna av scenarios för TC. Utvärderingen m.a.p. (a) effekt på svarstider, (b) möjlighet att återanvända nogood.