001package org.cpsolver.exam.neighbours; 002 003import java.text.DecimalFormat; 004import java.util.Collection; 005import java.util.HashMap; 006import java.util.HashSet; 007import java.util.Iterator; 008import java.util.Map; 009import java.util.Set; 010 011import org.cpsolver.exam.model.Exam; 012import org.cpsolver.exam.model.ExamPlacement; 013import org.cpsolver.exam.model.ExamRoomPlacement; 014import org.cpsolver.ifs.assignment.Assignment; 015import org.cpsolver.ifs.model.Neighbour; 016 017 018/** 019 * Swap a room between two assigned exams. <br> 020 * <br> 021 * 022 * @version ExamTT 1.3 (Examination Timetabling)<br> 023 * Copyright (C) 2008 - 2014 Tomáš Müller<br> 024 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 025 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 026 * <br> 027 * This library is free software; you can redistribute it and/or modify 028 * it under the terms of the GNU Lesser General Public License as 029 * published by the Free Software Foundation; either version 3 of the 030 * License, or (at your option) any later version. <br> 031 * <br> 032 * This library is distributed in the hope that it will be useful, but 033 * WITHOUT ANY WARRANTY; without even the implied warranty of 034 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 035 * Lesser General Public License for more details. <br> 036 * <br> 037 * You should have received a copy of the GNU Lesser General Public 038 * License along with this library; if not see 039 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 040 */ 041public class ExamRoomSwapNeighbour implements Neighbour<Exam, ExamPlacement> { 042 private double iValue = 0; 043 private ExamPlacement iX1, iX2 = null; 044 private ExamRoomPlacement iR1, iR2 = null; 045 046 public ExamRoomSwapNeighbour(Assignment<Exam, ExamPlacement> assignment, ExamPlacement placement, ExamRoomPlacement current, ExamRoomPlacement swap) { 047 if (placement.getRoomPlacements().contains(swap)) 048 return; // not an actual swap 049 if (!checkParents(placement.getRoomPlacements(), current, swap)) 050 return; // room partition violation 051 Exam exam = placement.variable(); 052 if (!swap.isAvailable(placement.getPeriod())) 053 return; // room not available 054 if (!exam.checkDistributionConstraints(assignment, swap)) 055 return; // a distribution constraint is violated 056 int size = 0; 057 for (ExamRoomPlacement r : placement.getRoomPlacements()) 058 size += r.getSize(exam.hasAltSeating()); 059 size -= current.getSize(exam.hasAltSeating()); 060 size += swap.getSize(exam.hasAltSeating()); 061 if (size < exam.getSize()) 062 return; // new room is too small 063 ExamPlacement conflict = null; 064 Set<ExamPlacement> conf = new HashSet<ExamPlacement>(); 065 swap.getRoom().computeConflicts(assignment, exam, placement.getPeriod(), conf); 066 if (conf.size() > 1) return; 067 else if (conf.size() == 1) conflict = conf.iterator().next(); 068 if (conflict == null) { 069 Set<ExamRoomPlacement> newRooms = new HashSet<ExamRoomPlacement>(placement.getRoomPlacements()); 070 newRooms.remove(current); 071 newRooms.add(swap); 072 for (Iterator<ExamRoomPlacement> i = newRooms.iterator(); i.hasNext();) { 073 ExamRoomPlacement r = i.next(); 074 if (r.equals(swap)) 075 continue; 076 if (size - r.getSize(exam.hasAltSeating()) >= exam.getSize()) { 077 i.remove(); 078 size -= r.getSize(exam.hasAltSeating()); 079 } 080 } 081 iX1 = new ExamPlacement(exam, placement.getPeriodPlacement(), newRooms); 082 ExamPlacement p = assignment.getValue(exam); 083 iValue = iX1.toDouble(assignment) - (p == null ? 0.0 : p.toDouble(assignment)); 084 } else { 085 Exam x = conflict.variable(); 086 ExamRoomPlacement xNew = x.getRoomPlacement(current.getRoom()); 087 if (xNew == null) 088 return; // conflicting exam cannot be assigned in the current 089 // room 090 if (!conflict.contains(current.getRoom())) 091 return; // conflict due to the room partitioning 092 if (swap.getRoom().equals(current.getRoom().getParentRoom()) || current.getRoom().equals(swap.getRoom().getParentRoom())) 093 return; // conflict due to the room partitioning 094 if (!x.checkDistributionConstraints(assignment, xNew)) 095 return; // conflicting exam has a distribution constraint 096 // violated 097 if (!checkParents(placement.getRoomPlacements(), swap, xNew)) 098 return; // room partition violation 099 int xSize = 0; 100 for (ExamRoomPlacement r : conflict.getRoomPlacements()) { 101 xSize += r.getSize(x.hasAltSeating()); 102 } 103 xSize -= swap.getSize(x.hasAltSeating()); 104 xSize += current.getSize(x.hasAltSeating()); 105 if (xSize < x.getSize()) 106 return; // current room is too small for the conflicting exam 107 Set<ExamPlacement> otherConf = new HashSet<ExamPlacement>(); otherConf.add(placement); 108 current.getRoom().computeConflicts(assignment, x, placement.getPeriod(), otherConf); 109 if (otherConf.size() > 1) 110 return; // other placements are conflicting than the current one 111 Set<ExamRoomPlacement> newRooms = new HashSet<ExamRoomPlacement>(placement.getRoomPlacements()); 112 newRooms.remove(current); 113 newRooms.add(swap); 114 for (Iterator<ExamRoomPlacement> i = newRooms.iterator(); i.hasNext();) { 115 ExamRoomPlacement r = i.next(); 116 if (r.equals(swap)) 117 continue; 118 if (size - r.getSize(exam.hasAltSeating()) >= exam.getSize()) { 119 i.remove(); 120 size -= r.getSize(exam.hasAltSeating()); 121 } 122 } 123 iX1 = new ExamPlacement(exam, placement.getPeriodPlacement(), newRooms); 124 Set<ExamRoomPlacement> xRooms = new HashSet<ExamRoomPlacement>(conflict.getRoomPlacements()); 125 xRooms.remove(x.getRoomPlacement(swap.getRoom())); 126 xRooms.add(xNew); 127 for (Iterator<ExamRoomPlacement> i = xRooms.iterator(); i.hasNext();) { 128 ExamRoomPlacement r = i.next(); 129 if (r.equals(swap)) 130 continue; 131 if (xSize - r.getSize(x.hasAltSeating()) >= x.getSize()) { 132 i.remove(); 133 xSize -= r.getSize(x.hasAltSeating()); 134 } 135 } 136 iX2 = new ExamPlacement(x, conflict.getPeriodPlacement(), xRooms); 137 ExamPlacement p = assignment.getValue(exam); 138 iValue = iX1.toDouble(assignment) - (p == null ? 0.0 : p.toDouble(assignment)) + iX2.toDouble(assignment) - conflict.toDouble(assignment); 139 } 140 iR1 = current; 141 iR2 = swap; 142 } 143 144 public boolean canDo() { 145 return iX1 != null; 146 } 147 148 @Override 149 public void assign(Assignment<Exam, ExamPlacement> assignment, long iteration) { 150 if (iX2 == null) { 151 assignment.assign(iteration, iX1); 152 } else { 153 assignment.unassign(iteration, iX1.variable()); 154 assignment.unassign(iteration, iX2.variable()); 155 assignment.assign(iteration, iX1); 156 assignment.assign(iteration, iX2); 157 } 158 } 159 160 @Override 161 public String toString() { 162 if (iX2 == null) { 163 return iX1.variable() + " := " + iX1.toString() + " / " + " (value:" + value(null) + ")"; 164 } else { 165 return iX1.variable().getName() + ": " + iR1.getRoom() + " <-> " + iR2.getRoom() + " (w " + iX2.variable().getName() + ", value:" + value(null) + ")"; 166 } 167 } 168 169 protected static String toString(double[] x, double[] y) { 170 DecimalFormat df = new DecimalFormat("0.00"); 171 StringBuffer s = new StringBuffer(); 172 for (int i = 0; i < x.length; i++) { 173 if (i > 0) 174 s.append(","); 175 s.append(df.format(x[i] - y[i])); 176 } 177 return "[" + s.toString() + "]"; 178 } 179 180 @Override 181 public double value(Assignment<Exam, ExamPlacement> assignment) { 182 return iValue; 183 } 184 185 @Override 186 public Map<Exam, ExamPlacement> assignments() { 187 Map<Exam, ExamPlacement> ret = new HashMap<Exam, ExamPlacement>(); 188 ret.put(iX1.variable(), iX1); 189 if (iX2 != null) 190 ret.put(iX2.variable(), iX2); 191 return ret; 192 } 193 194 private static boolean checkParents(Collection<ExamRoomPlacement> rooms, ExamRoomPlacement current, ExamRoomPlacement swap) { 195 if (swap.getRoom().getParentRoom() != null) { 196 // check if already lists the parent 197 for (ExamRoomPlacement r: rooms) 198 if (!r.equals(current) && r.getRoom().equals(swap.getRoom().getParentRoom())) return false; 199 } 200 if (swap.getRoom().getPartitions() != null) { 201 // check if has any of the partitions 202 for (ExamRoomPlacement r: rooms) 203 if (!r.equals(current) && swap.getRoom().getPartitions().contains(r.getRoom())) return false; 204 } 205 return true; 206 } 207}