001package org.cpsolver.studentsct.online.selection; 002 003import java.util.ArrayList; 004import java.util.Hashtable; 005import java.util.List; 006import java.util.Map; 007import java.util.Set; 008 009import org.cpsolver.ifs.assignment.Assignment; 010import org.cpsolver.ifs.util.DataProperties; 011import org.cpsolver.studentsct.extension.DistanceConflict; 012import org.cpsolver.studentsct.extension.TimeOverlapsCounter; 013import org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection; 014import org.cpsolver.studentsct.model.Config; 015import org.cpsolver.studentsct.model.CourseRequest; 016import org.cpsolver.studentsct.model.Enrollment; 017import org.cpsolver.studentsct.model.FreeTimeRequest; 018import org.cpsolver.studentsct.model.Request; 019import org.cpsolver.studentsct.model.Section; 020import org.cpsolver.studentsct.model.Student; 021import org.cpsolver.studentsct.model.Subpart; 022import org.cpsolver.studentsct.online.OnlineSectioningModel; 023 024/** 025 * Online student sectioning algorithm based on the {@link BranchBoundSelection} of the batch solver. The 026 * selections adds the ability to provide required free times and sections and to prefer certain sections. 027 * If a course request has preferred sections, StudentWeights.PreferenceFactor parameter is used 028 * to penalize selection of a non-preferred section. 029 * 030 * @version StudentSct 1.3 (Student Sectioning)<br> 031 * Copyright (C) 2014 Tomáš Müller<br> 032 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 033 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 034 * <br> 035 * This library is free software; you can redistribute it and/or modify 036 * it under the terms of the GNU Lesser General Public License as 037 * published by the Free Software Foundation; either version 3 of the 038 * License, or (at your option) any later version. <br> 039 * <br> 040 * This library is distributed in the hope that it will be useful, but 041 * WITHOUT ANY WARRANTY; without even the implied warranty of 042 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 043 * Lesser General Public License for more details. <br> 044 * <br> 045 * You should have received a copy of the GNU Lesser General Public 046 * License along with this library; if not see <a 047 * href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>. 048 * 049 */ 050public class SuggestionSelection extends BranchBoundSelection implements OnlineSectioningSelection { 051 protected Set<FreeTimeRequest> iRequiredFreeTimes; 052 protected Hashtable<CourseRequest, Config> iRequiredConfig = null; 053 protected Hashtable<CourseRequest, Hashtable<Subpart, Section>> iRequiredSection = null; 054 protected Hashtable<CourseRequest, Set<Section>> iPreferredSections = null; 055 protected Set<CourseRequest> iRequiredUnassinged = null; 056 /** add up to 50% for preferred sections */ 057 private double iPreferenceFactor = 0.500; 058 private double iMaxOverExpected = -1.0; 059 060 public SuggestionSelection(DataProperties properties) { 061 super(properties); 062 iPreferenceFactor = properties.getPropertyDouble("StudentWeights.PreferenceFactor", iPreferenceFactor); 063 } 064 065 @Override 066 public void setPreferredSections(Hashtable<CourseRequest, Set<Section>> preferredSections) { 067 iPreferredSections = preferredSections; 068 } 069 070 @Override 071 public void setRequiredSections(Hashtable<CourseRequest, Set<Section>> requiredSections) { 072 iRequiredConfig = new Hashtable<CourseRequest, Config>(); 073 iRequiredSection = new Hashtable<CourseRequest, Hashtable<Subpart, Section>>(); 074 if (requiredSections != null) { 075 for (Map.Entry<CourseRequest, Set<Section>> entry : requiredSections.entrySet()) { 076 Hashtable<Subpart, Section> subSection = new Hashtable<Subpart, Section>(); 077 iRequiredSection.put(entry.getKey(), subSection); 078 for (Section section : entry.getValue()) { 079 if (subSection.isEmpty()) 080 iRequiredConfig.put(entry.getKey(), section.getSubpart().getConfig()); 081 subSection.put(section.getSubpart(), section); 082 } 083 } 084 } 085 } 086 087 @Override 088 public void setRequiredFreeTimes(Set<FreeTimeRequest> requiredFreeTimes) { 089 iRequiredFreeTimes = requiredFreeTimes; 090 } 091 092 @Override 093 public BranchBoundNeighbour select(Assignment<Request, Enrollment> assignment, Student student) { 094 return new Selection(student, assignment).select(); 095 } 096 097 @Override 098 public void setModel(OnlineSectioningModel model) { 099 super.setModel(model); 100 } 101 102 /** 103 * Extension of {@link org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection.Selection} including checking of 104 * required free times and sections. 105 * 106 */ 107 public class Selection extends BranchBoundSelection.Selection { 108 public Selection(Student student, Assignment<Request, Enrollment> assignment) { 109 super(student, assignment); 110 } 111 112 /** 113 * Check if the given enrollment is allowed 114 * @param idx enrollment index 115 * @param enrollment enrollment 116 * @return true if allowed (there is no conflict with required sections or free times) 117 */ 118 public boolean isAllowed(int idx, Enrollment enrollment) { 119 if (enrollment.isCourseRequest()) { 120 CourseRequest request = (CourseRequest) enrollment.getRequest(); 121 if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request)) return false; 122 Config reqConfig = iRequiredConfig.get(request); 123 if (reqConfig != null) { 124 if (!reqConfig.equals(enrollment.getConfig())) 125 return false; 126 Hashtable<Subpart, Section> reqSections = iRequiredSection.get(request); 127 for (Section section : enrollment.getSections()) { 128 Section reqSection = reqSections.get(section.getSubpart()); 129 if (reqSection == null) 130 continue; 131 if (!section.equals(reqSection)) 132 return false; 133 } 134 } 135 } else if (iRequiredFreeTimes.contains(enrollment.getRequest())) { 136 if (enrollment.getAssignments() == null || enrollment.getAssignments().isEmpty()) 137 return false; 138 } 139 return true; 140 } 141 142 @Override 143 public boolean inConflict(int idx, Enrollment enrollment) { 144 if (iMaxOverExpected >= 0.0 && iModel instanceof OnlineSectioningModel) { 145 double penalty = 0.0; 146 for (int i = 0; i < idx; i++) { 147 if (iAssignment[i] != null && iAssignment[i].getAssignments() != null && iAssignment[i].isCourseRequest()) 148 for (Section section: iAssignment[i].getSections()) 149 penalty += ((OnlineSectioningModel)iModel).getOverExpected(iCurrentAssignment, iAssignment, i, section, iAssignment[i].getRequest()); 150 } 151 if (enrollment.isCourseRequest()) 152 for (Section section: enrollment.getSections()) 153 penalty += ((OnlineSectioningModel)iModel).getOverExpected(iCurrentAssignment, iAssignment, idx, section, enrollment.getRequest()); 154 if (penalty > iMaxOverExpected) return true; 155 } 156 return super.inConflict(idx, enrollment) || !isAllowed(idx, enrollment); 157 } 158 159 @Override 160 public Enrollment firstConflict(int idx, Enrollment enrollment) { 161 Enrollment conflict = super.firstConflict(idx, enrollment); 162 if (conflict != null) 163 return conflict; 164 return (isAllowed(idx, enrollment) ? null : enrollment); 165 } 166 167 @Override 168 protected boolean canLeaveUnassigned(Request request) { 169 if (request instanceof CourseRequest) { 170 if (iRequiredConfig.get(request) != null) 171 return false; 172 } else if (iRequiredFreeTimes.contains(request)) 173 return false; 174 return true; 175 } 176 177 @Override 178 protected List<Enrollment> values(final CourseRequest request) { 179 if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request)) 180 return new ArrayList<Enrollment>(); 181 return super.values(request); 182 } 183 184 @Override 185 @Deprecated 186 protected double getWeight(Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts, 187 Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) { 188 double weight = super.getWeight(enrollment, distanceConflicts, timeOverlappingConflicts); 189 if (enrollment.isCourseRequest() && iPreferredSections != null) { 190 Set<Section> preferred = iPreferredSections.get(enrollment.getRequest()); 191 if (preferred != null && !preferred.isEmpty()) { 192 double nrPreferred = 0; 193 for (Section section : enrollment.getSections()) 194 if (preferred.contains(section)) 195 nrPreferred++; 196 double preferredFraction = nrPreferred / preferred.size(); 197 weight *= 1.0 + iPreferenceFactor * preferredFraction; 198 } 199 } 200 return weight; 201 } 202 203 @Override 204 protected double getBound(Request r) { 205 double bound = super.getBound(r); 206 if (r instanceof CourseRequest) { 207 Set<Section> preferred = iPreferredSections.get(r); 208 if (preferred != null && !preferred.isEmpty()) 209 bound *= (1.0 + iPreferenceFactor); 210 } 211 return bound; 212 } 213 214 } 215 216 @Override 217 public void setRequiredUnassinged(Set<CourseRequest> requiredUnassignedRequests) { 218 iRequiredUnassinged = requiredUnassignedRequests; 219 } 220 221 @Override 222 public void setMaxOverExpected(double maxOverExpected) { 223 iMaxOverExpected = maxOverExpected; 224 } 225}