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