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