I många verkliga optimeringsproblem finns det flera samverkande komponenter i en lösning. Till exempel kan olika komponenter specificera uppdrag till olika typer av resurser. Ofta förknippas varje komponent med olika uppsättningar av mjuka begränsningar, och så med olika åtgärder för mjuk begränsning överträdelse. Målet är då att minimera en linjär kombination av sådana åtgärder. I detta dokument studeras en strategi för sådana problem, som kan ses som en flerfasexploatering av flera objektiva/värdebegränsade delmodeller. I detta tillvägagångssätt beaktas först endast en beräkningsmässigt svår komponent i ett problem och den tillhörande undergruppen av mål. Detta producerar partiella lösningar, som definierar intressanta områden i sökområdet för hela problemet. Ofta är det möjligt att välja den ursprungliga komponenten så att variabel aggregering kan utföras i det första skedet, och de områden som ska utforskas härnäst garanteras att innehålla genomförbara lösningar. Med hjälp av heltal programmering, är det sedan lätt att genomföra heuristik producerar lösningar med gränser på deras kvalitet. Vår studie genomförs på en kurstidtagningsproblem som används i 2007 års internationella tidtagningstävling, även känd som Udine Course Tidtagningsproblem. Målet är att hitta en tilldelning av händelser till perioder och rum, så att tilldelningen av händelser till perioder är en möjlig avgränsad färgning av en tillhörande konfliktgraf och den linjära kombinationen av antalet överträdelser av fyra mjuka begränsningar minimeras. I den föreslagna heurismen producerar en objektiv begränsad kvartersgenerator uppgifter om perioder till händelser, med minskande antal överträdelser av två periodrelaterade mjuka begränsningar. Dessa är avslappnade i uppdrag av händelser till dagar, som definierar stadsdelar som är lättare att söka med avseende på alla fyra mjuka begränsningar. Integer programmering formuleringar för alla subproblem ges och utvärderas med hjälp av ILOG CPLEX 11. Den vidare tillämpligheten av detta tillvägagångssätt analyseras och diskuteras.
I REF utförs experiment på att inaktivera olika kombinationer av mjuka-fasta påföljder av Udine Course Tidtagningsproblem, inklusive en där alla rumspåföljder för rumstilldelning är inaktiverade.
Decomposition, Reformulation, and Diving in University Course Timetabling
{'venue': 'Computers and Operations Research (2010) 37(3), 582-597', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}