001package org.cpsolver.coursett.sectioning;
002
003import java.util.Collection;
004import java.util.Comparator;
005import java.util.HashMap;
006import java.util.HashSet;
007import java.util.List;
008import java.util.Map;
009import java.util.Set;
010import java.util.TreeSet;
011
012import org.cpsolver.coursett.constraint.JenrlConstraint;
013import org.cpsolver.coursett.criteria.StudentConflict;
014import org.cpsolver.coursett.model.Configuration;
015import org.cpsolver.coursett.model.DefaultStudentSectioning;
016import org.cpsolver.coursett.model.InitialSectioning.Group;
017import org.cpsolver.coursett.model.Lecture;
018import org.cpsolver.coursett.model.Placement;
019import org.cpsolver.coursett.model.Student;
020import org.cpsolver.coursett.model.StudentGroup;
021import org.cpsolver.coursett.model.TimetableModel;
022import org.cpsolver.coursett.sectioning.SctSectioning.GroupBasedInitialSectioning;
023import org.cpsolver.ifs.assignment.Assignment;
024import org.cpsolver.ifs.model.InfoProvider;
025import org.cpsolver.ifs.model.Neighbour;
026import org.cpsolver.ifs.solution.Solution;
027import org.cpsolver.ifs.termination.TerminationCondition;
028import org.cpsolver.ifs.util.DataProperties;
029import org.cpsolver.ifs.util.JProf;
030
031/**
032 * Student sectioning implementation based on local search. A student swap is
033 * generated in each iteration using Hill Climbing and Great Deluge algorithms.
034 * 
035 * @version CourseTT 1.3 (University Course Timetabling)<br>
036 *          Copyright (C) 2017 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 StudentSwapSectioning extends DefaultStudentSectioning implements InfoProvider<Lecture, Placement> {
055    private static double sEps = 0.0001;
056    private double iGroupWeight = 0.1;
057    private int iMaxIdleResection = 1000;
058
059    public StudentSwapSectioning(TimetableModel model) {
060        super(model);
061        iGroupWeight = model.getProperties().getPropertyDouble("StudentSwaps.GroupWeight", 10.0);
062        iMaxIdleResection = model.getProperties().getPropertyInt("StudentSwaps.MaxIdleResection", 1000);
063    }
064    
065    protected List<StudentConflict> getStudentConflictCriteria() {
066        if (iModel != null) return iModel.getStudentConflictCriteria();
067        return null;
068    }
069    
070    @Override
071    public boolean hasFinalSectioning() {
072        return true;
073    }
074    
075    /**
076     * Student conflict weight change of a student swap 
077     */
078    protected double objective(Neighbour<Lecture, Placement> n, Assignment<Lecture, Placement> assignment) {
079        if (n instanceof StudentMove)
080            return ((StudentMove)n).value(getStudentConflictCriteria(), assignment);
081        return n.value(assignment);
082    }
083    
084    /**
085     * Student group weight change of a student swap 
086     */
087    protected double group(Neighbour<Lecture, Placement> n, Assignment<Lecture, Placement> assignment) {
088        if (n instanceof StudentMove)
089            return ((StudentMove)n).group(getStudentConflictCriteria(), assignment);
090        return 0.0;
091    }
092    
093    /**
094     * Combined weight change of a student swap 
095     */
096    protected double value(Neighbour<Lecture, Placement> n, Assignment<Lecture, Placement> assignment) {
097        if (n instanceof StudentMove)
098            return ((StudentMove)n).value(getStudentConflictCriteria(), assignment) - iGroupWeight * ((StudentMove)n).group(getStudentConflictCriteria(), assignment);
099        return n.value(assignment);
100    }
101    
102    /**
103     * Student conflict weight of a solution 
104     */
105    protected double objective(Solution<Lecture, Placement> solution) {
106        List<StudentConflict> criteria = getStudentConflictCriteria();
107        
108        if (criteria == null) {
109            double value = 0.0;
110            for (JenrlConstraint constraint: ((TimetableModel)solution.getModel()).getJenrlConstraints()) {
111                if (constraint.isInConflict(solution.getAssignment())) value += constraint.jenrl();
112            }
113            return value;
114        }
115        
116        double value = 0.0;
117        for (StudentConflict criterion: criteria)
118            value += criterion.getWeightedValue(solution.getAssignment());
119        return value;
120    }
121    
122    /**
123     * Student group weight of a solution 
124     */
125    public static double group(TimetableModel model) {
126        double ret = 0;
127        for (StudentGroup group: model.getStudentGroups()) {
128            Map<Long, Match> match = new HashMap<Long, Match>();
129            Set<Long> offeringIds = new HashSet<Long>();
130            for (Student student: group.getStudents())
131                for (Lecture lecture: student.getLectures()) {
132                    if (lecture.getConfiguration() == null) continue;
133                    offeringIds.add(lecture.getConfiguration().getOfferingId());
134                    Match m = match.get(lecture.getSchedulingSubpartId());
135                    if (m == null) { m = new Match(group, lecture.getConfiguration()); match.put(lecture.getSchedulingSubpartId(), m); }
136                    m.inc(lecture);
137                }
138            double value = 0.0;
139            for (Match m: match.values())
140                value += m.value();
141            ret += value / offeringIds.size();
142        }
143        return ret;
144    }
145    
146    /**
147     * Student group percentage of a solution subset
148     */
149    public static double gp(TimetableModel model, Collection<Lecture> variables) {
150        if (model.getStudentGroups().isEmpty()) return 0.0;
151        double ret = 0; int count = 0;
152        for (StudentGroup group: model.getStudentGroups()) {
153            Map<Long, Match> match = new HashMap<Long, Match>();
154            Set<Long> offeringIds = new HashSet<Long>();
155            for (Student student: group.getStudents())
156                for (Lecture lecture: student.getLectures()) {
157                    if (lecture.getConfiguration() == null) continue;
158                    if (variables != null && !variables.contains(lecture)) continue;
159                    offeringIds.add(lecture.getConfiguration().getOfferingId());
160                    Match m = match.get(lecture.getSchedulingSubpartId());
161                    if (m == null) { m = new Match(group, lecture.getConfiguration()); match.put(lecture.getSchedulingSubpartId(), m); }
162                    m.inc(lecture);
163                }
164            if (match.isEmpty()) continue;
165            double value = 0.0;
166            for (Match m: match.values())
167                value += m.value();
168            ret += value / offeringIds.size();
169            count ++;
170        }
171        return 100.0 * ret / count;
172    }
173    
174    /**
175     * Student group percentage of a solution
176     */
177    public static double gp(TimetableModel model) {
178        if (model.getStudentGroups().isEmpty()) return 0.0;
179        return 100.0 * group(model) / model.getStudentGroups().size();
180    }
181    
182    /**
183     * Student group percentage of a solution
184     */
185    public static double gp(Solution<Lecture, Placement> solution) {
186        return gp((TimetableModel)solution.getModel());
187    }
188    
189    /**
190     * Combined weight of a solution 
191     */
192    protected double value(Solution<Lecture, Placement> solution) {
193        return objective(solution) + iGroupWeight * (iModel.getStudentGroups().size() - group(iModel));
194    }
195
196    @Override
197    public void switchStudents(Solution<Lecture, Placement> solution, TerminationCondition<Lecture, Placement> termination) {
198        long it = 0, lastImp = 0;
199        double t0 = JProf.currentTimeMillis();
200        DataProperties cfg = ((TimetableModel)solution.getModel()).getProperties(); 
201        long maxIdle = cfg.getPropertyInt("StudentSwaps.MaxIdle", 100000);
202        
203        getProgress().setStatus("Student Sectioning...");
204        getProgress().info("Student Conflicts: " + sDF2.format(objective(solution)) + " (group: " + sDF2.format(gp(solution)) + "%)");
205        getProgress().setPhase("Swapping students [HC]...", 1000);
206        StudentSwapGenerator g = new StudentSwapGenerator();
207        while ((it - lastImp) < maxIdle && (termination == null || termination.canContinue(solution))) {
208            it ++;
209            if ((it % 1000) == 0) {
210                long prg = Math.round(1000.0 * (it - lastImp) / maxIdle);
211                if (getProgress().getProgress() < prg)
212                    getProgress().setProgress(prg);
213                if ((it % 10000) == 0)
214                    getProgress().info("Iter=" + (it / 1000)+"k, Idle=" + sDF2.format((it - lastImp)/1000.0)+"k, Speed=" + sDF2.format(1000.0 * it / (JProf.currentTimeMillis() - t0))+" it/s" +
215                            ", Value=" + sDF2.format(value(solution)) + ", Objective=" + sDF2.format(objective(solution)) + ", Group=" + sDF2.format(gp(solution)) + "%");
216            }
217            Neighbour<Lecture, Placement> n = g.selectNeighbour(solution);
218            if (n == null) continue;
219            double v = value(n, solution.getAssignment());
220            if (v < -sEps) { lastImp = it; }
221            if (v <= 0) { n.assign(solution.getAssignment(), it); }
222        }
223        getProgress().info("Student Conflicts: " + sDF2.format(objective(solution)) + " (group: " + sDF2.format(gp(solution)) + "%)");
224        
225        double f = cfg.getPropertyDouble("StudentSwaps.Deluge.Factor", 0.9999999);
226        double ub = cfg.getPropertyDouble("StudentSwaps.Deluge.UpperBound", 1.10);
227        double lb = cfg.getPropertyDouble("StudentSwaps.Deluge.LowerBound", 0.90);
228        double total = value(solution);
229        double bound = ub * total;
230        double best = total;
231        
232        it = 0; lastImp = 0; t0 = JProf.currentTimeMillis();
233        getProgress().setPhase("Swapping students [GD]...", 1000);
234        while (bound > lb * total && total > 0 && (termination == null || termination.canContinue(solution))) {
235            Neighbour<Lecture, Placement> n = g.selectNeighbour(solution);
236            if (n != null) {
237                double value = value(n, solution.getAssignment());
238                if (value < 0) { lastImp = it; }
239                if (value <= 0.0 || total + value < bound) {
240                    n.assign(solution.getAssignment(), it);
241                    if (total + value < best) {
242                        best = total + value;
243                    }
244                    total += value;
245                }
246            }
247            bound *= f;
248            it++;
249            if ((it % 1000) == 0) {
250                long prg = 1000 - Math.round(1000.0 * (bound - lb * best) / (ub * best - lb * best));
251                if (getProgress().getProgress() < prg)
252                    getProgress().setProgress(prg);
253                if ((it % 10000) == 0) {
254                    getProgress().info("Iter=" + (it / 1000)+"k, Idle=" + sDF2.format((it - lastImp)/1000.0)+"k, Speed=" + sDF2.format(1000.0 * it / (JProf.currentTimeMillis() - t0))+" it/s" +
255                            ", Value=" + sDF2.format(value(solution)) + ", Objective=" + sDF2.format(objective(solution)) + ", Group=" + sDF2.format(gp(solution)) + "%");
256                    getProgress().info("Bound is " + sDF2.format(bound) + ", " + "best value is " + sDF2.format(best) + " (" + sDF2.format(100.0 * bound / best) + "%), " +
257                            "current value is " + sDF2.format(total) + " (" + sDF2.format(100.0 * bound / total) + "%)");
258                }
259            }
260        }
261        getProgress().info("Student Conflicts: " + sDF2.format(objective(solution)) + " (group: " + sDF2.format(gp(solution)) + "%)");
262    }
263
264    @Override
265    public void resection(Assignment<Lecture, Placement> assignment, Lecture lecture, boolean recursive, boolean configAsWell) {
266        if (lecture.students().isEmpty()) return;
267        StudentSwapGenerator g = new StudentSwapGenerator();
268        long nrIdle = 0, it = 0;
269        while (nrIdle < iMaxIdleResection) {
270            nrIdle ++; it ++;
271            Neighbour<Lecture, Placement> n = g.selectNeighbour(assignment, lecture);
272            if (n == null) continue;
273            double v = value(n, assignment);
274            if (v < -sEps) nrIdle = 0;
275            if (v <= 0.0) n.assign(assignment, it);
276        }
277    }
278    
279    /**
280     * Matching students within a scheduling subpart (for student group weight computation)
281     */
282    private static class Match {
283        private int iTotal = 0;
284        private double iFraction = 1.0;
285        private Map<Long, Integer> iMatch = new HashMap<Long, Integer>();
286        
287        /**
288         * Constructor
289         * @param group student group
290         * @param offeringId offering id
291         */
292        Match(StudentGroup group, Configuration config) {
293            iTotal = group.countStudents(config.getOfferingId());
294            iFraction = 1.0 / config.countSubparts();
295        }
296        
297        /**
298         * Increment given lecture
299         */
300        void inc(Lecture lecture) {
301            Integer val = iMatch.get(lecture.getClassId());
302            iMatch.put(lecture.getClassId(), 1 + (val == null ? 0 : val.intValue()));
303        }
304        
305        /**
306         * Value (an overall probability of two students being in the same lecture) 
307         */
308        double value() {
309            if (iTotal <= 1) return iFraction;
310            double value = 0.0;
311            for (Integer m: iMatch.values())
312                if (m > 1)
313                    value += (m * (m - 1.0)) / (iTotal * (iTotal - 1.0));
314            return iFraction * value;
315        }
316        
317        @Override
318        public String toString() {
319            return iTotal + "/" + iMatch;
320        }
321    }
322    
323    protected boolean hasStudentGroups(Collection<Student> students) {
324        for (Student student: students)
325            if (!student.getGroups().isEmpty()) return true;
326        return false;
327    }
328    
329    @Override
330    protected Group[] studentsToConfigurations(Long offeringId, Collection<Student> students, Collection<Configuration> configurations) {
331        if (hasStudentGroups(students)) {
332            GroupBasedInitialSectioning sect = new GroupBasedInitialSectioning(getProgress(), offeringId, configurations, students);
333            return sect.getGroups();
334        } else {
335            return super.studentsToConfigurations(offeringId, students, configurations);
336        }
337    }
338    
339    @Override
340    protected Group[] studentsToLectures(Long offeringId, Collection<Student> students, Collection<Lecture> lectures) {
341        if (hasStudentGroups(students)) {
342            Set<Lecture> sortedLectures = new TreeSet<Lecture>(new Comparator<Lecture>() {
343                @Override
344                public int compare(Lecture l1, Lecture l2) {
345                    return l1.getClassId().compareTo(l2.getClassId());
346                }
347            });
348            sortedLectures.addAll(lectures);
349            GroupBasedInitialSectioning sect = new GroupBasedInitialSectioning(getProgress(), offeringId, sortedLectures, students);
350            return sect.getGroups();
351        } else {
352            return super.studentsToLectures(offeringId, students, lectures);
353        }
354    }
355}