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