Det har allmänt observerats att det inte finns någon enda "dominant" SAT-lösare; istället presterar olika lösare bäst på olika instanser. I stället för att följa den traditionella metoden att välja den bästa lösaren för en viss klass av instanser, förespråkar vi att detta beslut görs online på en per-intance basis. Med utgångspunkt i tidigare arbeten beskriver vi SATzilla, ett automatiserat tillvägagångssätt för att konstruera algoritmportföljer för SAT som använder så kallade empiriska hårdhetsmodeller för att välja bland sina konstituerande lösare. Detta tillvägagångssätt tar som ingång en distribution av problematik och en uppsättning av komponentlösare, och konstruerar en portfölj optimerar en given objektiv funktion (såsom genomsnittlig körtid, procent av fall löst, eller poäng i en tävling). SATzillas utmärkta prestanda verifierades självständigt i SAT-tävlingen 2007, där våra SAtzilla07-lösare vann tre guld, ett silver och en bronsmedalj. I den här artikeln går vi långt utöver SAtzilla07 genom att göra portföljkonstruktionen skalbar och helt automatiserad, och förbättra den genom att integrera lokala söklösare som kandidatlösare, genom att förutsäga prestandapoäng istället för körtid, och genom att använda hierarkiska hårdhetsmodeller som tar hänsyn till olika typer av SAT-fall. Vi demonstrerar effektiviteten av dessa nya tekniker i omfattande experimentella resultat på datamängder inklusive exempel från den senaste SAT-tävlingen.
När det gäller SAT, författare till REF, har föreslagit en portföljbaserad strategi, kallad SAtzilla, där en distribution av problematik och en uppsättning av komponentlösare tas som input för att skapa en portfölj som optimerar en given objektiv funktion, såsom, genomsnittlig körtid eller antal instans löst.
SATzilla: Portfolio-based Algorithm Selection for SAT
{'venue': 'Journal Of Artificial Intelligence Research, Volume 32, pages 565-606, 2008', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}