Decomposition, reformulation,anddivinginuniversitycoursetimetabling

In manyreal-lifeoptimisationproblems,therearemultipleinteractingcomponentsinasolution.For example, differentcomponentsmightspecifyassignmentstodifferentkindsofresource.Often,each component isassociatedwithdifferentsetsofsoftconstraints,andsowithdifferentmeasuresofsoft constraint violation.Thegoalisthentominimisealinearcombinationofsuchmeasures.Thispaper studies anapproachtosuchproblems,whichcanbethoughtofasmultiphaseexploitationofmultiple objective-/value-restricted submodels.Inthisapproach,onlyonecomputationallydifficultcomponent of aproblemandtheassociatedsubsetofobjectivesisconsideredatfirst.Thisproducespartialsolu- tions, whichdefineinterestingneighbourhoodsinthesearchspaceofthecompleteproblem.Often,itis possible topicktheinitialcomponentsothatvariableaggregationcanbeperformedatthefirststage, and theneighbourhoodstobeexplorednextareguaranteedtocontainfeasiblesolutions.Usinginteger programming, itistheneasytoimplementheuristicsproducingsolutionswithboundsontheirquality. Our studyisperformedonauniversitycoursetimetablingproblemusedinthe2007International Timetabling Competition(ITC),alsoknownastheUdineCourseTimetablingproblem.Thegoalisto find anassignmentofeventstoperiodsandrooms,sothattheassignmentofeventstoperiodsisa feasible boundedcolouringofanassociatedconflictgraphandthelinearcombinationofthenumbersof violations offoursoftconstraintsisminimised.Intheproposedheuristic,anobjective-restrictedneigh- bourhood generatorproducesassignmentsofperiodstoevents,withdecreasingnumbersofviolationsof two period-relatedsoftconstraints.Thosearerelaxedintoassignmentsofeventstodays,whichdefine neighbourhoods thatareeasiertosearchwithrespecttoallfoursoftconstraints.Integerprogramming formulations forallsubproblemsaregivenandevaluatedusingILOGCPLEX11.Thewiderapplicability of thisapproachisanalysedanddiscussed.