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 Tomas Muller<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                    offeringIds.add(lecture.getConfiguration().getOfferingId());
144                    Match m = match.get(lecture.getSchedulingSubpartId());
145                    if (m == null) { m = new Match(group, lecture.getConfiguration()); match.put(lecture.getSchedulingSubpartId(), m); }
146                    m.inc(lecture);
147                }
148            double value = 0.0;
149            for (Match m: match.values())
150                value += m.value();
151            ret += value / offeringIds.size();
152        }
153        return ret;
154    }
155    
156    /**
157     * Student group percentage of a solution subset
158     */
159    public static double gp(TimetableModel model, Collection<Lecture> variables) {
160        if (model.getStudentGroups().isEmpty()) return 0.0;
161        double ret = 0; int count = 0;
162        for (StudentGroup group: model.getStudentGroups()) {
163            Map<Long, Match> match = new HashMap<Long, Match>();
164            Set<Long> offeringIds = new HashSet<Long>();
165            for (Student student: group.getStudents())
166                for (Lecture lecture: student.getLectures()) {
167                    if (variables != null && !variables.contains(lecture)) continue;
168                    offeringIds.add(lecture.getConfiguration().getOfferingId());
169                    Match m = match.get(lecture.getSchedulingSubpartId());
170                    if (m == null) { m = new Match(group, lecture.getConfiguration()); match.put(lecture.getSchedulingSubpartId(), m); }
171                    m.inc(lecture);
172                }
173            if (match.isEmpty()) continue;
174            double value = 0.0;
175            for (Match m: match.values())
176                value += m.value();
177            ret += value / offeringIds.size();
178            count ++;
179        }
180        return 100.0 * ret / count;
181    }
182    
183    /**
184     * Student group percentage of a solution
185     */
186    public static double gp(TimetableModel model) {
187        if (model.getStudentGroups().isEmpty()) return 0.0;
188        return 100.0 * group(model) / model.getStudentGroups().size();
189    }
190    
191    /**
192     * Student group percentage of a solution
193     */
194    public static double gp(Solution<Lecture, Placement> solution) {
195        return gp((TimetableModel)solution.getModel());
196    }
197    
198    /**
199     * Combined weight of a solution 
200     */
201    protected double value(Solution<Lecture, Placement> solution) {
202        return objective(solution) + iGroupWeight * (iModel.getStudentGroups().size() - group(iModel));
203    }
204
205    @Override
206    public void switchStudents(Solution<Lecture, Placement> solution, TerminationCondition<Lecture, Placement> termination) {
207        long it = 0, lastImp = 0;
208        double t0 = JProf.currentTimeMillis();
209        DataProperties cfg = ((TimetableModel)solution.getModel()).getProperties(); 
210        long maxIdle = cfg.getPropertyInt("StudentSwaps.MaxIdle", 100000);
211        
212        getProgress().setStatus("Student Sectioning...");
213        getProgress().info("Student Conflicts: " + sDF2.format(objective(solution)) + " (group: " + sDF2.format(gp(solution)) + "%)");
214        getProgress().setPhase("Swapping students [HC]...", 1000);
215        StudentSwapGenerator g = new StudentSwapGenerator();
216        while ((it - lastImp) < maxIdle && (termination == null || termination.canContinue(solution))) {
217            it ++;
218            if ((it % 1000) == 0) {
219                long prg = Math.round(1000.0 * (it - lastImp) / maxIdle);
220                if (getProgress().getProgress() < prg)
221                    getProgress().setProgress(prg);
222                if ((it % 10000) == 0)
223                    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" +
224                            ", Value=" + sDF2.format(value(solution)) + ", Objective=" + sDF2.format(objective(solution)) + ", Group=" + sDF2.format(gp(solution)) + "%");
225            }
226            Neighbour<Lecture, Placement> n = g.selectNeighbour(solution);
227            if (n == null) continue;
228            double v = value(n, solution.getAssignment());
229            if (v < -sEps) { lastImp = it; }
230            if (v <= 0) { n.assign(solution.getAssignment(), it); }
231        }
232        getProgress().info("Student Conflicts: " + sDF2.format(objective(solution)) + " (group: " + sDF2.format(gp(solution)) + "%)");
233        
234        double f = cfg.getPropertyDouble("StudentSwaps.Deluge.Factor", 0.9999999);
235        double ub = cfg.getPropertyDouble("StudentSwaps.Deluge.UpperBound", 1.10);
236        double lb = cfg.getPropertyDouble("StudentSwaps.Deluge.LowerBound", 0.90);
237        double total = value(solution);
238        double bound = ub * total;
239        double best = total;
240        
241        it = 0; lastImp = 0; t0 = JProf.currentTimeMillis();
242        getProgress().setPhase("Swapping students [GD]...", 1000);
243        while (bound > lb * total && total > 0 && (termination == null || termination.canContinue(solution))) {
244            Neighbour<Lecture, Placement> n = g.selectNeighbour(solution);
245            if (n != null) {
246                double value = value(n, solution.getAssignment());
247                if (value < 0) { lastImp = it; }
248                if (value <= 0.0 || total + value < bound) {
249                    n.assign(solution.getAssignment(), it);
250                    if (total + value < best) {
251                        best = total + value;
252                    }
253                    total += value;
254                }
255            }
256            bound *= f;
257            it++;
258            if ((it % 1000) == 0) {
259                long prg = 1000 - Math.round(1000.0 * (bound - lb * best) / (ub * best - lb * best));
260                if (getProgress().getProgress() < prg)
261                    getProgress().setProgress(prg);
262                if ((it % 10000) == 0) {
263                    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" +
264                            ", Value=" + sDF2.format(value(solution)) + ", Objective=" + sDF2.format(objective(solution)) + ", Group=" + sDF2.format(gp(solution)) + "%");
265                    getProgress().info("Bound is " + sDF2.format(bound) + ", " + "best value is " + sDF2.format(best) + " (" + sDF2.format(100.0 * bound / best) + "%), " +
266                            "current value is " + sDF2.format(total) + " (" + sDF2.format(100.0 * bound / total) + "%)");
267                }
268            }
269        }
270        getProgress().info("Student Conflicts: " + sDF2.format(objective(solution)) + " (group: " + sDF2.format(gp(solution)) + "%)");
271    }
272
273    @Override
274    public void resection(Assignment<Lecture, Placement> assignment, Lecture lecture, boolean recursive, boolean configAsWell) {
275        if (lecture.students().isEmpty()) return;
276        StudentSwapGenerator g = new StudentSwapGenerator();
277        long nrIdle = 0, it = 0;
278        while (nrIdle < iMaxIdleResection) {
279            nrIdle ++; it ++;
280            Neighbour<Lecture, Placement> n = g.selectNeighbour(assignment, lecture);
281            if (n == null) continue;
282            double v = value(n, assignment);
283            if (v < -sEps) nrIdle = 0;
284            if (v <= 0.0) n.assign(assignment, it);
285        }
286    }
287    
288    /**
289     * Matching students within a scheduling subpart (for student group weight computation)
290     */
291    private static class Match {
292        private int iTotal = 0;
293        private double iFraction = 1.0;
294        private Map<Long, Integer> iMatch = new HashMap<Long, Integer>();
295        
296        /**
297         * Constructor
298         * @param group student group
299         * @param offeringId offering id
300         */
301        Match(StudentGroup group, Configuration config) {
302            iTotal = group.countStudents(config.getOfferingId());
303            iFraction = 1.0 / config.countSubparts();
304        }
305        
306        /**
307         * Increment given lecture
308         */
309        void inc(Lecture lecture) {
310            Integer val = iMatch.get(lecture.getClassId());
311            iMatch.put(lecture.getClassId(), 1 + (val == null ? 0 : val.intValue()));
312        }
313        
314        /**
315         * Value (an overall probability of two students being in the same lecture) 
316         */
317        double value() {
318            if (iTotal <= 1) return iFraction;
319            double value = 0.0;
320            for (Integer m: iMatch.values())
321                if (m > 1)
322                    value += (m * (m - 1.0)) / (iTotal * (iTotal - 1.0));
323            return iFraction * value;
324        }
325        
326        @Override
327        public String toString() {
328            return iTotal + "/" + iMatch;
329        }
330    }
331    
332    protected boolean hasStudentGroups(Collection<Student> students) {
333        for (Student student: students)
334            if (!student.getGroups().isEmpty()) return true;
335        return false;
336    }
337    
338    @Override
339    protected Group[] studentsToConfigurations(Long offeringId, Collection<Student> students, Collection<Configuration> configurations) {
340        if (hasStudentGroups(students)) {
341            GroupBasedInitialSectioning sect = new GroupBasedInitialSectioning(getProgress(), offeringId, configurations, students);
342            return sect.getGroups();
343        } else {
344            return super.studentsToConfigurations(offeringId, students, configurations);
345        }
346    }
347    
348    @Override
349    protected Group[] studentsToLectures(Long offeringId, Collection<Student> students, Collection<Lecture> lectures) {
350        if (hasStudentGroups(students)) {
351            Set<Lecture> sortedLectures = new TreeSet<Lecture>(new Comparator<Lecture>() {
352                @Override
353                public int compare(Lecture l1, Lecture l2) {
354                    return l1.getClassId().compareTo(l2.getClassId());
355                }
356            });
357            sortedLectures.addAll(lectures);
358            GroupBasedInitialSectioning sect = new GroupBasedInitialSectioning(getProgress(), offeringId, sortedLectures, students);
359            return sect.getGroups();
360        } else {
361            return super.studentsToLectures(offeringId, students, lectures);
362        }
363    }
364}