001package org.cpsolver.coursett; 002 003import org.cpsolver.coursett.heuristics.FixCompleteSolutionNeighbourSelection; 004import org.cpsolver.coursett.heuristics.NeighbourSelectionWithSuggestions; 005import org.cpsolver.coursett.model.Lecture; 006import org.cpsolver.coursett.model.Placement; 007import org.cpsolver.coursett.model.TimetableModel; 008import org.cpsolver.ifs.assignment.Assignment; 009import org.cpsolver.ifs.model.Neighbour; 010import org.cpsolver.ifs.solution.Solution; 011import org.cpsolver.ifs.solver.Solver; 012import org.cpsolver.ifs.util.DataProperties; 013import org.cpsolver.ifs.util.JProf; 014import org.cpsolver.ifs.util.Progress; 015 016/** 017 * University course timetabling solver. <br> 018 * <br> 019 * When a complete solution is found, it is improved by limited depth 020 * backtracking search. This way it is ensured that the fund solution is at 021 * least locally optimal.<br> 022 * <br> 023 * Deprecated: use {@link FixCompleteSolutionNeighbourSelection} instead. 024 * 025 * @version CourseTT 1.3 (University Course Timetabling)<br> 026 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 027 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 028 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 029 * <br> 030 * This library is free software; you can redistribute it and/or modify 031 * it under the terms of the GNU Lesser General Public License as 032 * published by the Free Software Foundation; either version 3 of the 033 * License, or (at your option) any later version. <br> 034 * <br> 035 * This library is distributed in the hope that it will be useful, but 036 * WITHOUT ANY WARRANTY; without even the implied warranty of 037 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 038 * Lesser General Public License for more details. <br> 039 * <br> 040 * You should have received a copy of the GNU Lesser General Public 041 * License along with this library; if not see 042 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 043 */ 044 045@Deprecated 046public class TimetableSolver extends Solver<Lecture, Placement> { 047 private long iLastCompleteSolutionFixIteration = -1; 048 private long iLastIncompleteSolutionFixIteration = -1; 049 private long iCompleteSolutionFixInterval = 1; 050 private long iIncompleteSolutionFixInterval = 5000; 051 052 public TimetableSolver(DataProperties properties) { 053 super(properties); 054 } 055 056 @Override 057 public void initSolver() { 058 super.initSolver(); 059 iCompleteSolutionFixInterval = getProperties().getPropertyLong("General.CompleteSolutionFixInterval", iCompleteSolutionFixInterval); 060 iIncompleteSolutionFixInterval = getProperties().getPropertyLong("General.IncompleteSolutionFixInterval", iIncompleteSolutionFixInterval); 061 } 062 063 @Override 064 protected void onAssigned(double startTime, Solution<Lecture, Placement> solution) { 065 if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) == 0) { 066 // complete solution was found 067 if (iCompleteSolutionFixInterval < 0) { 068 // feature disabled 069 return; 070 } else if (iCompleteSolutionFixInterval == 0) { 071 // only run first time a complete solution is found 072 if (iLastCompleteSolutionFixIteration >= 0) return; 073 } else { 074 // run first time and if not run for a given number of iterations 075 if (iLastCompleteSolutionFixIteration >= 0 && solution.getIteration() - iLastCompleteSolutionFixIteration < iCompleteSolutionFixInterval) return; 076 } 077 if (getSolutionComparator().isBetterThanBestSolution(solution)) { 078 fixCompleteSolution(solution, startTime); 079 iLastCompleteSolutionFixIteration = solution.getIteration(); 080 } 081 } else if (solution.getBestInfo() == null) { 082 // complete solution has not been found yet 083 if (iIncompleteSolutionFixInterval < 0) { 084 // feature disabled 085 return; 086 } else if (iIncompleteSolutionFixInterval == 0) { 087 // only run first time a complete solution is found 088 if (iLastIncompleteSolutionFixIteration >= 0) return; 089 } else { 090 // run first time and if not run for a given number of iterations 091 if (iLastIncompleteSolutionFixIteration >= 0 && solution.getIteration() - iLastIncompleteSolutionFixIteration < iIncompleteSolutionFixInterval) return; 092 } 093 if (getSolutionComparator().isBetterThanBestSolution(solution)) { 094 fixCompleteSolution(solution, startTime); 095 iLastIncompleteSolutionFixIteration = solution.getIteration(); 096 } 097 } 098 } 099 100 /** 101 * Try to improve existing solution by backtracking search of very limited 102 * depth. See {@link NeighbourSelectionWithSuggestions} for more details. 103 * @param solution current solution 104 * @param startTime start time 105 */ 106 protected void fixCompleteSolution(Solution<Lecture, Placement> solution, double startTime) { 107 Progress progress = Progress.getInstance(solution.getModel()); 108 109 TimetableModel model = (TimetableModel) solution.getModel(); 110 Assignment<Lecture, Placement> assignment = solution.getAssignment(); 111 solution.saveBest(); 112 progress.save(); 113 double solutionValue = 0.0, newSolutionValue = model.getTotalValue(assignment); 114 do { 115 solutionValue = newSolutionValue; 116 progress.setPhase("Fixing solution", model.variables().size()); 117 for (Lecture variable : model.variables()) { 118 Placement bestValue = null; 119 double bestVal = 0.0; 120 Placement currentValue = assignment.getValue(variable); 121 if (currentValue == null) 122 continue; 123 double currentVal = currentValue.toDouble(assignment); 124 for (Placement value : variable.values()) { 125 if (value.equals(currentValue)) 126 continue; 127 if (model.conflictValues(assignment, value).isEmpty()) { 128 double val = value.toDouble(assignment); 129 if (bestValue == null || val < bestVal) { 130 bestValue = value; 131 bestVal = val; 132 } 133 } 134 } 135 if (bestValue != null && bestVal < currentVal) 136 assignment.assign(0, bestValue); 137 solution.update(JProf.currentTimeSec() - startTime); 138 progress.incProgress(); 139 if (iStop) 140 break; 141 } 142 newSolutionValue = model.getTotalValue(assignment); 143 if (newSolutionValue < solutionValue) { 144 progress.debug("New solution value is " + newSolutionValue); 145 } 146 } while (!iStop && newSolutionValue < solutionValue && getTerminationCondition().canContinue(solution)); 147 progress.restore(); 148 149 if (!solution.getModel().unassignedVariables(assignment).isEmpty()) 150 return; 151 progress.save(); 152 try { 153 progress.setPhase("Fixing solution [2]", model.variables().size()); 154 NeighbourSelectionWithSuggestions ns = new NeighbourSelectionWithSuggestions(this); 155 for (Lecture lecture : model.variables()) { 156 Neighbour<Lecture, Placement> n = ns.selectNeighbourWithSuggestions(solution, lecture, 2); 157 if (n != null && n.value(assignment) <= 0.0) 158 n.assign(assignment, 0); 159 solution.update(JProf.currentTimeSec() - startTime); 160 progress.incProgress(); 161 if (iStop) 162 break; 163 } 164 } catch (Exception e) { 165 sLogger.debug(e.getMessage(), e); 166 } finally { 167 progress.restore(); 168 } 169 } 170}