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