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 }