001package net.sf.cpsolver.exam.heuristics; 002 003import java.util.HashSet; 004import java.util.Set; 005 006import net.sf.cpsolver.exam.model.Exam; 007import net.sf.cpsolver.exam.model.ExamModel; 008import net.sf.cpsolver.exam.model.ExamPeriodPlacement; 009import net.sf.cpsolver.exam.model.ExamPlacement; 010import net.sf.cpsolver.exam.model.ExamRoomPlacement; 011import net.sf.cpsolver.exam.neighbours.ExamSimpleNeighbour; 012import net.sf.cpsolver.ifs.heuristics.NeighbourSelection; 013import net.sf.cpsolver.ifs.model.Neighbour; 014import net.sf.cpsolver.ifs.solution.Solution; 015import net.sf.cpsolver.ifs.solver.Solver; 016import net.sf.cpsolver.ifs.util.DataProperties; 017import net.sf.cpsolver.ifs.util.Progress; 018 019/** 020 * Initial solution construction heuristics. <br> 021 * <br> 022 * While there are exams that are still not assigned: 023 * <ul> 024 * <li>The worst unassigned exam is selected (using {@link Exam#compareTo(Exam)}) 025 * <li>The best period that does not break any hard constraint and for which 026 * there is a room assignment available is selected together with the set the 027 * best available rooms for the exam in the best period (computed using 028 * {@link Exam#findBestAvailableRooms(ExamPeriodPlacement)}). 029 * </ul> 030 * <br> 031 * <br> 032 * If problem property ExamConstruction.CheckLocalOptimality is true, local 033 * (time) optimality is enforced at the end of this phase. During this 034 * procedure, for each exam, it tries to change the period of the exam so that 035 * the time cost is lower (see {@link ExamPlacement#getTimeCost()}), but no hard 036 * constraint is violated. The problem is considered locally optimal if there is 037 * no such move. <br> 038 * <br> 039 * 040 * @version ExamTT 1.2 (Examination Timetabling)<br> 041 * Copyright (C) 2008 - 2010 Tomáš Müller<br> 042 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 043 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 044 * <br> 045 * This library is free software; you can redistribute it and/or modify 046 * it under the terms of the GNU Lesser General Public License as 047 * published by the Free Software Foundation; either version 3 of the 048 * License, or (at your option) any later version. <br> 049 * <br> 050 * This library is distributed in the hope that it will be useful, but 051 * WITHOUT ANY WARRANTY; without even the implied warranty of 052 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 053 * Lesser General Public License for more details. <br> 054 * <br> 055 * You should have received a copy of the GNU Lesser General Public 056 * License along with this library; if not see 057 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 058 */ 059public class ExamConstruction implements NeighbourSelection<Exam, ExamPlacement> { 060 private HashSet<String> iAssignments = new HashSet<String>(); 061 private boolean iCheckLocalOptimality = false; 062 private HashSet<Exam> iSkip = new HashSet<Exam>(); 063 private Progress iProgress = null; 064 private boolean iActive; 065 066 /** 067 * Constructor 068 * 069 * @param properties 070 * problem properties 071 */ 072 public ExamConstruction(DataProperties properties) { 073 iCheckLocalOptimality = properties.getPropertyBoolean("ExamConstruction.CheckLocalOptimality", 074 iCheckLocalOptimality); 075 } 076 077 /** 078 * Initialization 079 */ 080 @Override 081 public void init(Solver<Exam, ExamPlacement> solver) { 082 iSkip.clear(); 083 solver.setUpdateProgress(false); 084 iProgress = Progress.getInstance(solver.currentSolution().getModel()); 085 iActive = false; 086 } 087 088 /** 089 * Find a new assignment of one of the assigned exams that improves the time 090 * cost {@link ExamPlacement#getTimeCost()} and for which there is a set of 091 * available rooms {@link Exam#findBestAvailableRooms(ExamPeriodPlacement)}. 092 * Return null, if there is no such assignment (the problem is considered 093 * locally optimal). 094 */ 095 public Neighbour<Exam, ExamPlacement> checkLocalOptimality(ExamModel model) { 096 if (iCheckLocalOptimality) { 097 for (Exam exam : model.assignedVariables()) { 098 ExamPlacement current = exam.getAssignment(); 099 if (current.getTimeCost() <= 0) 100 continue; 101 ExamPlacement best = null; 102 for (ExamPeriodPlacement period : exam.getPeriodPlacements()) { 103 if (exam.countStudentConflicts(period) > 0) { 104 if (iAssignments.contains(exam.getId() + ":" + period.getIndex())) 105 continue; 106 } 107 if (!exam.checkDistributionConstraints(period)) 108 continue; 109 ExamPlacement placement = new ExamPlacement(exam, period, null); 110 if (best == null || best.getTimeCost() > placement.getTimeCost()) { 111 Set<ExamRoomPlacement> rooms = exam.findBestAvailableRooms(period); 112 if (rooms != null) 113 best = new ExamPlacement(exam, period, rooms); 114 } 115 } 116 if (best != null && best.getTimeCost() < current.getTimeCost()) 117 return new ExamSimpleNeighbour(best); 118 } 119 } 120 iActive = false; 121 return null; 122 } 123 124 /** 125 * Select a neighbour. While there are exams that are still not assigned: 126 * <ul> 127 * <li>The worst unassigned exam is selected (using 128 * {@link Exam#compareTo(Exam)}) 129 * <li>The best period that does not break any hard constraint and for which 130 * there is a room assignment available is selected together with the set 131 * the best available rooms for the exam in the best period (computed using 132 * {@link Exam#findBestAvailableRooms(ExamPeriodPlacement)}). 133 * </ul> 134 * Return null when done (all variables are assigned and the problem is 135 * locally optimal). 136 */ 137 @Override 138 public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) { 139 ExamModel model = (ExamModel) solution.getModel(); 140 if (!iActive) { 141 iActive = true; 142 iProgress.setPhase("Construction ...", model.variables().size()); 143 } 144 iProgress.setProgress(model.nrAssignedVariables()); 145 if (model.nrUnassignedVariables() <= iSkip.size()) 146 return checkLocalOptimality(model); 147 Exam bestExam = null; 148 for (Exam exam : model.unassignedVariables()) { 149 if (iSkip.contains(exam)) 150 continue; 151 if (bestExam == null || exam.compareTo(bestExam) < 0) 152 bestExam = exam; 153 } 154 ExamPlacement best = null; 155 for (ExamPeriodPlacement period : bestExam.getPeriodPlacements()) { 156 if (bestExam.countStudentConflicts(period) > 0) { 157 if (iAssignments.contains(bestExam.getId() + ":" + period.getIndex())) 158 continue; 159 } 160 if (!bestExam.checkDistributionConstraints(period)) 161 continue; 162 ExamPlacement placement = new ExamPlacement(bestExam, period, null); 163 if (best == null || best.getTimeCost() > placement.getTimeCost()) { 164 Set<ExamRoomPlacement> rooms = bestExam.findBestAvailableRooms(period); 165 if (rooms != null) 166 best = new ExamPlacement(bestExam, period, rooms); 167 } 168 } 169 if (best != null) { 170 iAssignments.add(bestExam.getId() + ":" + best.getPeriod().getIndex()); 171 return new ExamSimpleNeighbour(best); 172 } /* 173 * else { for (Enumeration 174 * e=bestExam.getPeriodPlacements().elements();e.hasMoreElements();) { 175 * ExamPeriodPlacement period = (ExamPeriodPlacement)e.nextElement(); 176 * ExamPlacement placement = new ExamPlacement(bestExam, period, 177 * null); if (best==null || 178 * best.getTimeCost()>placement.getTimeCost()) { Set rooms = 179 * bestExam.findBestAvailableRooms(period); if (rooms!=null) best = 180 * new ExamPlacement(bestExam, period, rooms); } } if (best!=null) { 181 * bestExam.allowAllStudentConflicts(best.getPeriod()); 182 * iAssignments.add(bestExam.getId()+":"+best.getPeriod().getIndex()); 183 * return new ExamSimpleNeighbour(best); } } 184 */ 185 if (!iSkip.contains(bestExam)) { 186 iSkip.add(bestExam); 187 return selectNeighbour(solution); 188 } 189 return checkLocalOptimality(model); 190 } 191 192}