001package net.sf.cpsolver.coursett; 002 003import net.sf.cpsolver.coursett.heuristics.NeighbourSelectionWithSuggestions; 004import net.sf.cpsolver.coursett.model.Lecture; 005import net.sf.cpsolver.coursett.model.Placement; 006import net.sf.cpsolver.coursett.model.TimetableModel; 007import net.sf.cpsolver.ifs.model.Neighbour; 008import net.sf.cpsolver.ifs.solver.Solver; 009import net.sf.cpsolver.ifs.util.DataProperties; 010import net.sf.cpsolver.ifs.util.JProf; 011import 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 Tomáš Müller<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 040public class TimetableSolver extends Solver<Lecture, Placement> { 041 private long iLastCompleteSolutionFixIteration = -1; 042 private long iLastIncompleteSolutionFixIteration = -1; 043 private long iCompleteSolutionFixInterval = 1; 044 private long iIncompleteSolutionFixInterval = 5000; 045 046 public TimetableSolver(DataProperties properties) { 047 super(properties); 048 } 049 050 @Override 051 public void initSolver() { 052 super.initSolver(); 053 iCompleteSolutionFixInterval = getProperties().getPropertyLong("General.CompleteSolutionFixInterval", iCompleteSolutionFixInterval); 054 iIncompleteSolutionFixInterval = getProperties().getPropertyLong("General.IncompleteSolutionFixInterval", iIncompleteSolutionFixInterval); 055 } 056 057 @Override 058 protected void onAssigned(double startTime) { 059 if (iCurrentSolution.getModel().nrUnassignedVariables() == 0) { 060 // complete solution was found 061 if (iCompleteSolutionFixInterval < 0) { 062 // feature disabled 063 return; 064 } else if (iCompleteSolutionFixInterval == 0) { 065 // only run first time a complete solution is found 066 if (iLastCompleteSolutionFixIteration >= 0) return; 067 } else { 068 // run first time and if not run for a given number of iterations 069 if (iLastCompleteSolutionFixIteration >= 0 && iCurrentSolution.getIteration() - iLastCompleteSolutionFixIteration < iCompleteSolutionFixInterval) return; 070 } 071 if (getSolutionComparator().isBetterThanBestSolution(iCurrentSolution)) { 072 fixCompleteSolution(startTime); 073 iLastCompleteSolutionFixIteration = iCurrentSolution.getIteration(); 074 } 075 } else if (iCurrentSolution.getBestInfo() == null) { 076 // complete solution has not been found yet 077 if (iIncompleteSolutionFixInterval < 0) { 078 // feature disabled 079 return; 080 } else if (iIncompleteSolutionFixInterval == 0) { 081 // only run first time a complete solution is found 082 if (iLastIncompleteSolutionFixIteration >= 0) return; 083 } else { 084 // run first time and if not run for a given number of iterations 085 if (iLastIncompleteSolutionFixIteration >= 0 && iCurrentSolution.getIteration() - iLastIncompleteSolutionFixIteration < iIncompleteSolutionFixInterval) return; 086 } 087 if (getSolutionComparator().isBetterThanBestSolution(iCurrentSolution)) { 088 fixCompleteSolution(startTime); 089 iLastIncompleteSolutionFixIteration = iCurrentSolution.getIteration(); 090 } 091 } 092 } 093 094 /** 095 * Try to improve existing solution by backtracking search of very limited 096 * depth. See {@link NeighbourSelectionWithSuggestions} for more details. 097 */ 098 protected void fixCompleteSolution(double startTime) { 099 Progress progress = Progress.getInstance(currentSolution().getModel()); 100 101 TimetableModel model = (TimetableModel) iCurrentSolution.getModel(); 102 iCurrentSolution.saveBest(); 103 progress.save(); 104 double solutionValue = 0.0, newSolutionValue = model.getTotalValue(); 105 do { 106 solutionValue = newSolutionValue; 107 progress.setPhase("Fixing solution", model.variables().size()); 108 for (Lecture variable : model.variables()) { 109 Placement bestValue = null; 110 double bestVal = 0.0; 111 Placement currentValue = variable.getAssignment(); 112 if (currentValue == null) 113 continue; 114 double currentVal = currentValue.toDouble(); 115 for (Placement value : variable.values()) { 116 if (value.equals(currentValue)) 117 continue; 118 if (model.conflictValues(value).isEmpty()) { 119 double val = value.toDouble(); 120 if (bestValue == null || val < bestVal) { 121 bestValue = value; 122 bestVal = val; 123 } 124 } 125 } 126 if (bestValue != null && bestVal < currentVal) 127 variable.assign(0, bestValue); 128 iCurrentSolution.update(JProf.currentTimeSec() - startTime); 129 progress.incProgress(); 130 if (iStop) 131 break; 132 } 133 newSolutionValue = model.getTotalValue(); 134 if (newSolutionValue < solutionValue) { 135 progress.debug("New solution value is " + newSolutionValue); 136 } 137 } while (!iStop && newSolutionValue < solutionValue && getTerminationCondition().canContinue(iCurrentSolution)); 138 progress.restore(); 139 140 if (!iCurrentSolution.getModel().unassignedVariables().isEmpty()) 141 return; 142 progress.save(); 143 try { 144 progress.setPhase("Fixing solution [2]", model.variables().size()); 145 NeighbourSelectionWithSuggestions ns = new NeighbourSelectionWithSuggestions(this); 146 for (Lecture lecture : model.variables()) { 147 Neighbour<Lecture, Placement> n = ns.selectNeighbourWithSuggestions(iCurrentSolution, lecture, 2); 148 if (n != null && n.value() <= 0.0) 149 n.assign(0); 150 iCurrentSolution.update(JProf.currentTimeSec() - startTime); 151 progress.incProgress(); 152 if (iStop) 153 break; 154 } 155 } catch (Exception e) { 156 sLogger.debug(e.getMessage(), e); 157 } finally { 158 progress.restore(); 159 } 160 } 161}