001package net.sf.cpsolver.coursett.neighbourhoods; 002 003import java.util.ArrayList; 004import java.util.HashMap; 005import java.util.List; 006import java.util.Map; 007import java.util.Set; 008 009import net.sf.cpsolver.coursett.model.Lecture; 010import net.sf.cpsolver.coursett.model.Placement; 011import net.sf.cpsolver.coursett.model.RoomLocation; 012import net.sf.cpsolver.coursett.model.TimeLocation; 013import net.sf.cpsolver.coursett.model.TimetableModel; 014import net.sf.cpsolver.ifs.algorithms.neighbourhoods.RandomSwapMove; 015import net.sf.cpsolver.ifs.model.Neighbour; 016import net.sf.cpsolver.ifs.model.SimpleNeighbour; 017import net.sf.cpsolver.ifs.solution.Solution; 018import net.sf.cpsolver.ifs.solver.Solver; 019import net.sf.cpsolver.ifs.util.DataProperties; 020import net.sf.cpsolver.ifs.util.JProf; 021import net.sf.cpsolver.ifs.util.ToolBox; 022 023/** 024 * Try to assign a class with a new time. A class is selected randomly, a 025 * different time is randomly selected for the class -- the class is 026 * assigned into the new time. If the time is used or there is some other conflict, 027 * it tries to resolve these conflicts by assigning conflicting classes to other 028 * times as well. 029 * <br> 030 * 031 * @version IFS 1.2 (Iterative Forward Search)<br> 032 * Copyright (C) 2014 Tomáš Müller<br> 033 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 034 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 035 * <br> 036 * This library is free software; you can redistribute it and/or modify 037 * it under the terms of the GNU Lesser General Public License as 038 * published by the Free Software Foundation; either version 3 of the 039 * License, or (at your option) any later version. <br> 040 * <br> 041 * This library is distributed in the hope that it will be useful, but 042 * WITHOUT ANY WARRANTY; without even the implied warranty of 043 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 044 * Lesser General Public License for more details. <br> 045 * <br> 046 * You should have received a copy of the GNU Lesser General Public 047 * License along with this library; if not see 048 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 049 */ 050public class TimeSwap extends RandomSwapMove<Lecture, Placement> { 051 052 public TimeSwap(DataProperties config) { 053 super(config); 054 } 055 056 @Override 057 public void init(Solver<Lecture, Placement> solver) { 058 } 059 060 @Override 061 public Neighbour<Lecture, Placement> selectNeighbour(Solution<Lecture, Placement> solution) { 062 TimetableModel model = (TimetableModel)solution.getModel(); 063 double total = model.getTotalValue(); 064 int varIdx = ToolBox.random(model.variables().size()); 065 for (int i = 0; i < model.variables().size(); i++) { 066 Lecture lecture = model.variables().get((i + varIdx) % model.variables().size()); 067 Placement old = lecture.getAssignment(); 068 if (old == null) continue; 069 070 List<TimeLocation> values = lecture.timeLocations(); 071 if (values.isEmpty()) continue; 072 073 int attempts = 0; 074 long startTime = JProf.currentTimeMillis(); 075 int valIdx = ToolBox.random(values.size()); 076 for (int j = 0; j < values.size(); j++) { 077 TimeLocation time = values.get((j + valIdx) % values.size()); 078 if (time.getPreference() > 50) continue; 079 if (time.equals(old.getTimeLocation())) continue; 080 081 Placement placement = null; 082 if (lecture.getNrRooms() == 0) 083 placement = new Placement(lecture, time, (RoomLocation) null); 084 else if (lecture.getNrRooms() == 1) 085 placement = new Placement(lecture, time, old.getRoomLocation()); 086 else 087 placement = new Placement(lecture, time, old.getRoomLocations()); 088 if (!placement.isValid()) continue; 089 090 Set<Placement> conflicts = model.conflictValues(placement); 091 if (conflicts.contains(placement)) continue; 092 if (conflicts.isEmpty()) { 093 SimpleNeighbour<Lecture, Placement> n = new SimpleNeighbour<Lecture, Placement>(lecture, placement); 094 if (!iHC || n.value() <= 0) return n; 095 else continue; 096 } 097 098 Map<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 099 assignments.put(lecture, placement); 100 101 for (Placement conflict: conflicts) 102 conflict.variable().unassign(solution.getIteration()); 103 lecture.assign(solution.getIteration(), placement); 104 105 Double v = resolve(solution, total, startTime, assignments, new ArrayList<Placement>(conflicts), 0); 106 if (!conflicts.isEmpty()) 107 attempts ++; 108 109 lecture.unassign(solution.getIteration()); 110 for (Placement conflict: conflicts) 111 conflict.variable().assign(solution.getIteration(), conflict); 112 lecture.assign(solution.getIteration(), old); 113 114 if (v != null) 115 return new SwapNeighbour(assignments.values(), v); 116 117 if (attempts >= iMaxAttempts) break; 118 } 119 } 120 return null; 121 } 122 123 124 @Override 125 public Double resolve(Solution<Lecture, Placement> solution, double total, long startTime, Map<Lecture, Placement> assignments, List<Placement> conflicts, int index) { 126 if (index == conflicts.size()) return solution.getModel().getTotalValue() - total; 127 Placement conflict = conflicts.get(index); 128 Lecture variable = conflict.variable(); 129 130 List<TimeLocation> values = variable.timeLocations(); 131 if (values.isEmpty()) return null; 132 133 int valIdx = ToolBox.random(values.size()); 134 int attempts = 0; 135 for (int i = 0; i < values.size(); i++) { 136 TimeLocation time = values.get((i + valIdx) % values.size()); 137 if (time.getPreference() > 50) continue; 138 if (time.equals(conflict.getTimeLocation())) continue; 139 140 Placement value = null; 141 if (variable.getNrRooms() == 0) 142 value = new Placement(variable, time, (RoomLocation) null); 143 else if (variable.getNrRooms() == 1) 144 value = new Placement(variable, time, conflict.getRoomLocation()); 145 else 146 value = new Placement(variable, time, conflict.getRoomLocations()); 147 if (!value.isValid() || solution.getModel().inConflict(value)) continue; 148 149 variable.assign(solution.getIteration(), value); 150 Double v = resolve(solution, total, startTime, assignments, conflicts, 1 + index); 151 variable.unassign(solution.getIteration()); 152 attempts ++; 153 154 if (v != null && (!iHC || v <= 0)) { 155 assignments.put(variable, value); 156 return v; 157 } 158 if (attempts >= iMaxAttempts || isTimeLimitReached(startTime)) break; 159 } 160 161 return null; 162 } 163}