001package org.cpsolver.coursett.heuristics; 002 003import java.util.ArrayList; 004import java.util.Enumeration; 005import java.util.Iterator; 006 007import org.cpsolver.coursett.model.Lecture; 008import org.cpsolver.coursett.model.Placement; 009import org.cpsolver.ifs.assignment.Assignment; 010import org.cpsolver.ifs.assignment.context.AssignmentContext; 011import org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext; 012import org.cpsolver.ifs.heuristics.NeighbourSelection; 013import org.cpsolver.ifs.model.Neighbour; 014import org.cpsolver.ifs.model.SimpleNeighbour; 015import org.cpsolver.ifs.solution.Solution; 016import org.cpsolver.ifs.solver.Solver; 017import org.cpsolver.ifs.util.DataProperties; 018import org.cpsolver.ifs.util.Progress; 019 020 021/** 022 * University course timetabling neighbour selection. <br> 023 * <br> 024 * When a complete solution is found, it is improved by limited depth 025 * backtracking search. This way it is ensured that the fund solution is at 026 * least locally optimal. 027 * 028 * @version CourseTT 1.3 (University Course Timetabling)<br> 029 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 030 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 031 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 032 * <br> 033 * This library is free software; you can redistribute it and/or modify 034 * it under the terms of the GNU Lesser General Public License as 035 * published by the Free Software Foundation; either version 3 of the 036 * License, or (at your option) any later version. <br> 037 * <br> 038 * This library is distributed in the hope that it will be useful, but 039 * WITHOUT ANY WARRANTY; without even the implied warranty of 040 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 041 * Lesser General Public License for more details. <br> 042 * <br> 043 * You should have received a copy of the GNU Lesser General Public 044 * License along with this library; if not see 045 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 046 */ 047public class FixCompleteSolutionNeighbourSelection extends NeighbourSelectionWithContext<Lecture, Placement, FixCompleteSolutionNeighbourSelection.FixCompleteSolutionNeighbourContext> { 048 private NeighbourSelection<Lecture, Placement> iParent = null; 049 private long iLastCompleteSolutionFixIteration = -1; 050 private long iLastIncompleteSolutionFixIteration = -1; 051 private long iCompleteSolutionFixInterval = 1; 052 private long iIncompleteSolutionFixInterval = 5000; 053 private NeighbourSelectionWithSuggestions iSuggestions = null; 054 private Progress iProgress = null; 055 private Solver<Lecture, Placement> iSolver = null; 056 057 public FixCompleteSolutionNeighbourSelection(DataProperties config, NeighbourSelection<Lecture, Placement> parent) throws Exception { 058 iParent = parent; 059 iSuggestions = new NeighbourSelectionWithSuggestions(config); 060 } 061 062 public FixCompleteSolutionNeighbourSelection(DataProperties config) throws Exception { 063 this(config, new NeighbourSelectionWithSuggestions(config)); 064 } 065 066 @Override 067 public void init(Solver<Lecture, Placement> solver) { 068 super.init(solver); 069 iCompleteSolutionFixInterval = solver.getProperties().getPropertyLong("General.CompleteSolutionFixInterval", iCompleteSolutionFixInterval); 070 iIncompleteSolutionFixInterval = solver.getProperties().getPropertyLong("General.IncompleteSolutionFixInterval", iIncompleteSolutionFixInterval); 071 iSuggestions.init(solver); 072 iParent.init(solver); 073 iProgress = Progress.getInstance(solver.currentSolution().getModel()); 074 iLastIncompleteSolutionFixIteration = -1; 075 iLastCompleteSolutionFixIteration = -1; 076 iSolver = solver; 077 } 078 079 /** 080 * Try to improve existing solution by backtracking search of very limited 081 * depth. See {@link NeighbourSelectionWithSuggestions} for more details. 082 */ 083 @Override 084 public Neighbour<Lecture, Placement> selectNeighbour(Solution<Lecture, Placement> solution) { 085 FixCompleteSolutionNeighbourContext context = getContext(solution.getAssignment()); 086 if (context.getPhase() == 0) { 087 if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) == 0) { 088 // complete solution was found 089 if (iCompleteSolutionFixInterval < 0) { 090 // feature disabled 091 return iParent.selectNeighbour(solution); 092 } else if (iCompleteSolutionFixInterval == 0) { 093 // only run first time a complete solution is found 094 if (iLastCompleteSolutionFixIteration >= 0) return iParent.selectNeighbour(solution); 095 } else { 096 // run first time and if not run for a given number of iterations 097 if (iLastCompleteSolutionFixIteration >= 0 && solution.getIteration() - iLastCompleteSolutionFixIteration < iCompleteSolutionFixInterval) 098 return iParent.selectNeighbour(solution); 099 } 100 if (solution.getBestIteration() == solution.getIteration()) 101 context.incPhase(solution); 102 } else if (!solution.isBestComplete()) { 103 // complete solution has not been found yet 104 if (iIncompleteSolutionFixInterval < 0) { 105 // feature disabled 106 return iParent.selectNeighbour(solution); 107 } else if (iIncompleteSolutionFixInterval == 0) { 108 // only run first time a complete solution is found 109 if (iLastIncompleteSolutionFixIteration >= 0) 110 return iParent.selectNeighbour(solution); 111 } else { 112 // run first time and if not run for a given number of iterations 113 if (solution.getIteration() - iLastIncompleteSolutionFixIteration < iIncompleteSolutionFixInterval) 114 return iParent.selectNeighbour(solution); 115 } 116 if (solution.getBestIteration() == solution.getIteration()) 117 context.incPhase(solution); 118 } 119 } 120 121 while (context.getPhase() > 0 && !iSolver.isStop()) { 122 if (context.hasMoreElements()) { 123 Lecture variable = context.nextElement(); 124 // iProgress.incProgress(); 125 if (context.getPhase() == 1) { 126 Placement bestValue = null; 127 double bestVal = 0.0; 128 Placement currentValue = solution.getAssignment().getValue(variable); 129 if (currentValue == null) 130 continue; 131 double currentVal = currentValue.toDouble(solution.getAssignment()); 132 for (Placement value : variable.values(solution.getAssignment())) { 133 if (value.equals(currentValue)) 134 continue; 135 if (solution.getModel().conflictValues(solution.getAssignment(), value).isEmpty()) { 136 double val = value.toDouble(solution.getAssignment()); 137 if (bestValue == null || val < bestVal) { 138 bestValue = value; 139 bestVal = val; 140 } 141 } 142 } 143 if (bestValue != null && bestVal < currentVal) 144 return new SimpleNeighbour<Lecture, Placement>(variable, bestValue); 145 } else { 146 Neighbour<Lecture, Placement> n = iSuggestions.selectNeighbourWithSuggestions(solution, variable, 2); 147 if (n != null && n.value(solution.getAssignment()) <= solution.getModel().getTotalValue(solution.getAssignment())) 148 return n; 149 } 150 } else { 151 context.incPhase(solution); 152 } 153 } 154 return iParent.selectNeighbour(solution); 155 } 156 157 @Override 158 public FixCompleteSolutionNeighbourContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 159 return new FixCompleteSolutionNeighbourContext(assignment); 160 } 161 162 public class FixCompleteSolutionNeighbourContext implements AssignmentContext, Enumeration<Lecture> { 163 private int iPhase = 0; 164 private Iterator<Lecture> iLectures = null; 165 166 public FixCompleteSolutionNeighbourContext(Assignment<Lecture, Placement> assignment) {} 167 168 public int getPhase() { return iPhase; } 169 170 public void incPhase(Solution<Lecture, Placement> solution) { 171 // Progress progress = Progress.getInstance(solution.getModel()); 172 if (iPhase == 0) { 173 // iSolver.setUpdateProgress(false); 174 iPhase = 1; 175 solution.saveBest(); 176 // progress.setPhase("Fixing solution", solution.getModel().countVariables()); 177 iProgress.info("[" + Thread.currentThread().getName() + "] Fixing solution..."); 178 iLectures = new ArrayList<Lecture>(solution.getModel().variables()).iterator(); 179 } else if (iPhase == 1 && solution.isComplete()) { 180 iPhase = 2; 181 iProgress.info("[" + Thread.currentThread().getName() + "] Fixing complete solution..."); 182 // progress.setPhase("Fixing solution [2]", solution.getModel().countVariables()); 183 iLectures = new ArrayList<Lecture>(solution.getModel().variables()).iterator(); 184 } else { 185 if (iPhase == 1) 186 iLastIncompleteSolutionFixIteration = solution.getIteration(); 187 else 188 iLastCompleteSolutionFixIteration = solution.getIteration(); 189 // iSolver.setUpdateProgress(true); 190 // if (solution.isBestComplete()) 191 // iProgress.setPhase("Improving found solution ..."); 192 // else 193 // iProgress.setPhase("Searching for initial solution ...", solution.getModel().countVariables()); 194 iPhase = 0; 195 // progress.restore(); 196 iLectures = null; 197 } 198 } 199 200 @Override 201 public boolean hasMoreElements() { 202 return iLectures != null && iLectures.hasNext(); 203 } 204 205 @Override 206 public Lecture nextElement() { 207 return iLectures.next(); 208 } 209 210 } 211}