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