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