001 package net.sf.cpsolver.coursett; 002 003 import net.sf.cpsolver.coursett.heuristics.NeighbourSelectionWithSuggestions; 004 import net.sf.cpsolver.coursett.model.Lecture; 005 import net.sf.cpsolver.coursett.model.Placement; 006 import net.sf.cpsolver.coursett.model.TimetableModel; 007 import net.sf.cpsolver.ifs.model.Neighbour; 008 import net.sf.cpsolver.ifs.solver.Solver; 009 import net.sf.cpsolver.ifs.util.DataProperties; 010 import net.sf.cpsolver.ifs.util.JProf; 011 import net.sf.cpsolver.ifs.util.Progress; 012 013 /** 014 * University course timetabling solver. <br> 015 * <br> 016 * When a complete solution is found, it is improved by limited depth 017 * backtracking search. This way it is ensured that the fund solution is at 018 * least locally optimal. 019 * 020 * @version CourseTT 1.2 (University Course Timetabling)<br> 021 * Copyright (C) 2006 - 2010 Tomas Muller<br> 022 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 023 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 024 * <br> 025 * This library is free software; you can redistribute it and/or modify 026 * it under the terms of the GNU Lesser General Public License as 027 * published by the Free Software Foundation; either version 3 of the 028 * License, or (at your option) any later version. <br> 029 * <br> 030 * This library is distributed in the hope that it will be useful, but 031 * WITHOUT ANY WARRANTY; without even the implied warranty of 032 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 033 * Lesser General Public License for more details. <br> 034 * <br> 035 * You should have received a copy of the GNU Lesser General Public 036 * License along with this library; if not see 037 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 038 */ 039 040 public class TimetableSolver extends Solver<Lecture, Placement> { 041 042 public TimetableSolver(DataProperties properties) { 043 super(properties); 044 } 045 046 @Override 047 protected void onAssigned(double startTime) { 048 // Check if the solution is the best ever found one 049 if (iCurrentSolution.getModel().unassignedVariables().isEmpty() 050 && getSolutionComparator().isBetterThanBestSolution(iCurrentSolution)) { 051 fixCompleteSolution(startTime); 052 } /* 053 * else { // If the solver is not able to improve solution in the last 054 * 5000 iterations, take the best one and try to fix it if 055 * (iCurrentSolution.getBestInfo()!=null && 056 * iCurrentSolution.getModel().getBestUnassignedVariables()>0 && 057 * iCurrentSolution 058 * .getIteration()==iCurrentSolution.getBestIteration()+5000) { 059 * iCurrentSolution.restoreBest(); fixCompleteSolution(startTime); } } 060 */ 061 } 062 063 /** 064 * Try to improve existing solution by backtracking search of very limited 065 * depth. See {@link NeighbourSelectionWithSuggestions} for more details. 066 */ 067 protected void fixCompleteSolution(double startTime) { 068 Progress progress = Progress.getInstance(currentSolution().getModel()); 069 070 TimetableModel model = (TimetableModel) iCurrentSolution.getModel(); 071 iCurrentSolution.saveBest(); 072 progress.save(); 073 double solutionValue = 0.0, newSolutionValue = model.getTotalValue(); 074 do { 075 solutionValue = newSolutionValue; 076 progress.setPhase("Fixing solution", model.variables().size()); 077 for (Lecture variable : model.variables()) { 078 Placement bestValue = null; 079 double bestVal = 0.0; 080 Placement currentValue = variable.getAssignment(); 081 if (currentValue == null) 082 continue; 083 double currentVal = currentValue.toDouble(); 084 for (Placement value : variable.values()) { 085 if (value.equals(currentValue)) 086 continue; 087 if (model.conflictValues(value).isEmpty()) { 088 double val = value.toDouble(); 089 if (bestValue == null || val < bestVal) { 090 bestValue = value; 091 bestVal = val; 092 } 093 } 094 } 095 if (bestValue != null && bestVal < currentVal) 096 variable.assign(0, bestValue); 097 iCurrentSolution.update(JProf.currentTimeSec() - startTime); 098 progress.incProgress(); 099 if (iStop) 100 break; 101 } 102 newSolutionValue = model.getTotalValue(); 103 if (newSolutionValue < solutionValue) { 104 progress.debug("New solution value is " + newSolutionValue); 105 } 106 } while (!iStop && newSolutionValue < solutionValue && getTerminationCondition().canContinue(iCurrentSolution)); 107 progress.restore(); 108 109 if (!iCurrentSolution.getModel().unassignedVariables().isEmpty()) 110 return; 111 progress.save(); 112 try { 113 progress.setPhase("Fixing solution [2]", model.variables().size()); 114 NeighbourSelectionWithSuggestions ns = new NeighbourSelectionWithSuggestions(this); 115 for (Lecture lecture : model.variables()) { 116 Neighbour<Lecture, Placement> n = ns.selectNeighbourWithSuggestions(iCurrentSolution, lecture, 2); 117 if (n != null && n.value() <= 0.0) 118 n.assign(0); 119 iCurrentSolution.update(JProf.currentTimeSec() - startTime); 120 progress.incProgress(); 121 if (iStop) 122 break; 123 } 124 } catch (Exception e) { 125 sLogger.debug(e.getMessage(), e); 126 } finally { 127 progress.restore(); 128 } 129 } 130 }