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}