001package org.cpsolver.coursett.sectioning; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.Comparator; 006import java.util.HashSet; 007import java.util.List; 008import java.util.Set; 009import java.util.TreeSet; 010 011import org.cpsolver.coursett.constraint.JenrlConstraint; 012import org.cpsolver.coursett.criteria.StudentConflict; 013import org.cpsolver.coursett.custom.DeterministicStudentSectioning.DeterministicInitialSectioning; 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.TimetableModel; 021import org.cpsolver.coursett.sectioning.SctModel.SctSolution; 022import org.cpsolver.ifs.assignment.Assignment; 023import org.cpsolver.ifs.criteria.Criterion; 024import org.cpsolver.ifs.model.InfoProvider; 025import org.cpsolver.ifs.solution.Solution; 026import org.cpsolver.ifs.termination.TerminationCondition; 027import org.cpsolver.ifs.util.Progress; 028 029/** 030 * 031 * Student sectioning implementation based on branch & bound. This sectioning takes 032 * each offering one by one and it is using a branch & bound algorithm to find 033 * the best possible enrollment of all students into the given course. The sectioning 034 * considers both student conflict weights and student groups. 035 * 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 SctSectioning extends DefaultStudentSectioning implements InfoProvider<Lecture, Placement> { 056 private boolean iUseCriteria = true; 057 private int iNrRounds = 3; 058 private List<StudentConflict> iStudentConflictCriteria = null; 059 060 public SctSectioning(TimetableModel model) { 061 super(model); 062 iUseCriteria = model.getProperties().getPropertyBoolean("SctSectioning.UseCriteria", true); 063 iNrRounds = model.getProperties().getPropertyInt("SctSectioning.NrRounds", 3); 064 } 065 066 @Override 067 public boolean hasFinalSectioning() { 068 return true; 069 } 070 071 /** 072 * List of student conflict criteria 073 */ 074 protected List<StudentConflict> getStudentConflictCriteria() { 075 if (!iUseCriteria) return null; 076 if (iStudentConflictCriteria == null && iModel != null) { 077 iStudentConflictCriteria = new ArrayList<StudentConflict>(); 078 for (Criterion<Lecture, Placement> criterion: iModel.getCriteria()) 079 if (criterion instanceof StudentConflict) 080 iStudentConflictCriteria.add((StudentConflict)criterion); 081 } 082 return iStudentConflictCriteria; 083 } 084 085 /** 086 * Student conflict weight for the given solution 087 */ 088 protected double value(Solution<Lecture, Placement> solution) { 089 List<StudentConflict> criteria = getStudentConflictCriteria(); 090 091 if (criteria == null) { 092 double value = 0.0; 093 for (JenrlConstraint constraint: ((TimetableModel)solution.getModel()).getJenrlConstraints()) { 094 if (constraint.isInConflict(solution.getAssignment())) value += constraint.jenrl(); 095 } 096 return value; 097 } 098 099 double value = 0.0; 100 for (StudentConflict criterion: criteria) 101 value += criterion.getWeightedValue(solution.getAssignment()); 102 return value; 103 } 104 105 @Override 106 public void switchStudents(Solution<Lecture, Placement> solution, TerminationCondition<Lecture, Placement> termination) { 107 getProgress().setStatus("Student Sectioning..."); 108 getProgress().info("Student Conflicts: " + sDF2.format(value(solution)) + " (group: " + sDF2.format(StudentSwapSectioning.gp(solution)) + "%)"); 109 110 for (int i = 1; i <= iNrRounds; i++) { 111 getProgress().setPhase("Swapping students [" + i + "]...", iModel.variables().size()); 112 Set<Long> offeringIds = new HashSet<Long>(); 113 for (Lecture lecture: iModel.variables()) { 114 getProgress().incProgress(); 115 if (lecture.students().isEmpty() || lecture.isSingleSection()) continue; 116 if (termination != null && !termination.canContinue(solution)) return; 117 if (offeringIds.add(lecture.getConfiguration().getOfferingId())) { 118 SctModel model = new SctModel(iModel, solution.getAssignment()); 119 model.setConfiguration(lecture.getConfiguration()); 120 SctSolution s1 = model.currentSolution(); 121 SctSolution s2 = model.computeSolution(); 122 if (model.isTimeOutReached()) 123 getProgress().info("Timeout reached for " + lecture.getName()); 124 if (s2.isBetter(s1)) { 125 model.unassign(); 126 model.assign(s2); 127 getProgress().info("Student Conflicts: " + sDF2.format(value(solution)) + " (group: " + sDF2.format(StudentSwapSectioning.gp(solution)) + "%)"); 128 } 129 } 130 } 131 getProgress().info("Student Conflicts: " + sDF2.format(value(solution)) + " (group: " + sDF2.format(StudentSwapSectioning.gp(solution)) + "%)"); 132 } 133 } 134 135 @Override 136 public void resection(Assignment<Lecture, Placement> assignment, Lecture lecture, boolean recursive, boolean configAsWell) { 137 SctModel model = new SctModel(iModel, assignment); 138 model.setConfiguration(lecture.getConfiguration()); 139 SctSolution s1 = model.currentSolution(); 140 SctSolution s2 = model.computeSolution(); 141 if (s2.isBetter(s1)) { 142 model.unassign(); 143 model.assign(s2); 144 } 145 } 146 147 protected boolean hasStudentGroups(Collection<Student> students) { 148 for (Student student: students) 149 if (!student.getGroups().isEmpty()) return true; 150 return false; 151 } 152 153 @Override 154 protected Group[] studentsToConfigurations(Long offeringId, Collection<Student> students, Collection<Configuration> configurations) { 155 if (hasStudentGroups(students)) { 156 GroupBasedInitialSectioning sect = new GroupBasedInitialSectioning(getProgress(), offeringId, configurations, students); 157 return sect.getGroups(); 158 } else { 159 return super.studentsToConfigurations(offeringId, students, configurations); 160 } 161 } 162 163 @Override 164 protected Group[] studentsToLectures(Long offeringId, Collection<Student> students, Collection<Lecture> lectures) { 165 if (hasStudentGroups(students)) { 166 Set<Lecture> sortedLectures = new TreeSet<Lecture>(new Comparator<Lecture>() { 167 @Override 168 public int compare(Lecture l1, Lecture l2) { 169 return l1.getClassId().compareTo(l2.getClassId()); 170 } 171 }); 172 sortedLectures.addAll(lectures); 173 GroupBasedInitialSectioning sect = new GroupBasedInitialSectioning(getProgress(), offeringId, sortedLectures, students); 174 return sect.getGroups(); 175 } else { 176 return super.studentsToLectures(offeringId, students, lectures); 177 } 178 } 179 180 protected static class GroupBasedInitialSectioning extends DeterministicInitialSectioning { 181 public GroupBasedInitialSectioning(Progress progress, Long offeringId, Collection<?> lectureOrConfigurations, Collection<Student> students) { 182 super(progress, offeringId, lectureOrConfigurations, students); 183 } 184 185 @Override 186 public int compare(Student s1, Student s2) { 187 int cmp = s1.getGroupNames().compareToIgnoreCase(s2.getGroupNames()); 188 if (cmp != 0) return cmp; 189 return super.compare(s1, s2); 190 } 191 } 192}