001 package net.sf.cpsolver.exam.neighbours; 002 003 import java.text.DecimalFormat; 004 import java.util.HashSet; 005 import java.util.Iterator; 006 import java.util.Set; 007 008 import net.sf.cpsolver.exam.model.Exam; 009 import net.sf.cpsolver.exam.model.ExamPlacement; 010 import net.sf.cpsolver.exam.model.ExamRoomPlacement; 011 import net.sf.cpsolver.ifs.model.Neighbour; 012 013 /** 014 * Swap a room between two assigned exams. <br> 015 * <br> 016 * 017 * @version ExamTT 1.2 (Examination Timetabling)<br> 018 * Copyright (C) 2008 - 2010 Tomas Muller<br> 019 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 020 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 021 * <br> 022 * This library is free software; you can redistribute it and/or modify 023 * it under the terms of the GNU Lesser General Public License as 024 * published by the Free Software Foundation; either version 3 of the 025 * License, or (at your option) any later version. <br> 026 * <br> 027 * This library is distributed in the hope that it will be useful, but 028 * WITHOUT ANY WARRANTY; without even the implied warranty of 029 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 030 * Lesser General Public License for more details. <br> 031 * <br> 032 * You should have received a copy of the GNU Lesser General Public 033 * License along with this library; if not see 034 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 035 */ 036 public class ExamRoomSwapNeighbour extends Neighbour<Exam, ExamPlacement> { 037 private double iValue = 0; 038 private ExamPlacement iX1, iX2 = null; 039 private ExamRoomPlacement iR1, iR2 = null; 040 041 public ExamRoomSwapNeighbour(ExamPlacement placement, ExamRoomPlacement current, ExamRoomPlacement swap) { 042 if (placement.getRoomPlacements().contains(swap)) 043 return; // not an actual swap 044 Exam exam = placement.variable(); 045 if (!swap.isAvailable(placement.getPeriod())) 046 return; // room not available 047 if (!exam.checkDistributionConstraints(swap)) 048 return; // a distribution constraint is violated 049 int size = 0; 050 for (ExamRoomPlacement r : placement.getRoomPlacements()) 051 size += r.getSize(exam.hasAltSeating()); 052 size -= current.getSize(exam.hasAltSeating()); 053 size += swap.getSize(exam.hasAltSeating()); 054 if (size < exam.getSize()) 055 return; // new room is too small 056 ExamPlacement conflict = swap.getRoom().getPlacement(placement.getPeriod()); 057 if (conflict == null) { 058 Set<ExamRoomPlacement> newRooms = new HashSet<ExamRoomPlacement>(placement.getRoomPlacements()); 059 newRooms.remove(current); 060 newRooms.add(swap); 061 for (Iterator<ExamRoomPlacement> i = newRooms.iterator(); i.hasNext();) { 062 ExamRoomPlacement r = i.next(); 063 if (r.equals(swap)) 064 continue; 065 if (size - r.getSize(exam.hasAltSeating()) >= exam.getSize()) { 066 i.remove(); 067 size -= r.getSize(exam.hasAltSeating()); 068 } 069 } 070 iX1 = new ExamPlacement(exam, placement.getPeriodPlacement(), newRooms); 071 iValue = iX1.toDouble() - (exam.getAssignment() == null ? 0.0 : exam.getAssignment().toDouble()); 072 } else { 073 Exam x = conflict.variable(); 074 ExamRoomPlacement xNew = x.getRoomPlacement(current.getRoom()); 075 if (xNew == null) 076 return; // conflicting exam cannot be assigned in the current 077 // room 078 if (!x.checkDistributionConstraints(xNew)) 079 return; // conflicting exam has a distribution constraint 080 // violated 081 int xSize = 0; 082 for (ExamRoomPlacement r : conflict.getRoomPlacements()) { 083 xSize += r.getSize(x.hasAltSeating()); 084 } 085 xSize -= swap.getSize(x.hasAltSeating()); 086 xSize += current.getSize(x.hasAltSeating()); 087 if (xSize < x.getSize()) 088 return; // current room is too small for the conflicting exam 089 Set<ExamRoomPlacement> newRooms = new HashSet<ExamRoomPlacement>(placement.getRoomPlacements()); 090 newRooms.remove(current); 091 newRooms.add(swap); 092 for (Iterator<ExamRoomPlacement> i = newRooms.iterator(); i.hasNext();) { 093 ExamRoomPlacement r = i.next(); 094 if (r.equals(swap)) 095 continue; 096 if (size - r.getSize(exam.hasAltSeating()) >= exam.getSize()) { 097 i.remove(); 098 size -= r.getSize(exam.hasAltSeating()); 099 } 100 } 101 iX1 = new ExamPlacement(exam, placement.getPeriodPlacement(), newRooms); 102 Set<ExamRoomPlacement> xRooms = new HashSet<ExamRoomPlacement>(conflict.getRoomPlacements()); 103 xRooms.remove(x.getRoomPlacement(swap.getRoom())); 104 xRooms.add(xNew); 105 for (Iterator<ExamRoomPlacement> i = xRooms.iterator(); i.hasNext();) { 106 ExamRoomPlacement r = i.next(); 107 if (r.equals(swap)) 108 continue; 109 if (xSize - r.getSize(x.hasAltSeating()) >= x.getSize()) { 110 i.remove(); 111 xSize -= r.getSize(x.hasAltSeating()); 112 } 113 } 114 iX2 = new ExamPlacement(x, conflict.getPeriodPlacement(), xRooms); 115 iValue = iX1.toDouble() - (exam.getAssignment() == null ? 0.0 : exam.getAssignment().toDouble()) 116 + iX2.toDouble() - conflict.toDouble(); 117 } 118 iR1 = current; 119 iR2 = swap; 120 } 121 122 public boolean canDo() { 123 return iX1 != null; 124 } 125 126 @Override 127 public void assign(long iteration) { 128 if (iX2 == null) { 129 iX1.variable().assign(iteration, iX1); 130 } else { 131 if (iX1.variable().getAssignment() != null) 132 iX1.variable().unassign(iteration); 133 iX2.variable().unassign(iteration); 134 iX1.variable().assign(iteration, iX1); 135 iX2.variable().assign(iteration, iX2); 136 } 137 } 138 139 @Override 140 public String toString() { 141 if (iX2 == null) { 142 return iX1.variable().getAssignment() + " -> " + iX1.toString() + " / " + " (value:" + value() + ")"; 143 } else { 144 return iX1.variable().getName() + ": " + iR1.getRoom() + " <-> " + iR2.getRoom() + " (w " 145 + iX2.variable().getName() + ", value:" + value() + ")"; 146 } 147 } 148 149 protected static String toString(double[] x, double[] y) { 150 DecimalFormat df = new DecimalFormat("0.00"); 151 StringBuffer s = new StringBuffer(); 152 for (int i = 0; i < x.length; i++) { 153 if (i > 0) 154 s.append(","); 155 s.append(df.format(x[i] - y[i])); 156 } 157 return "[" + s.toString() + "]"; 158 } 159 160 @Override 161 public double value() { 162 return iValue; 163 } 164 }