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