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}