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 Tomas Muller<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 059 public SuggestionSelection(DataProperties properties) { 060 super(properties); 061 iPreferenceFactor = properties.getPropertyDouble("StudentWeights.PreferenceFactor", iPreferenceFactor); 062 } 063 064 @Override 065 public void setPreferredSections(Hashtable<CourseRequest, Set<Section>> preferredSections) { 066 iPreferredSections = preferredSections; 067 } 068 069 @Override 070 public void setRequiredSections(Hashtable<CourseRequest, Set<Section>> requiredSections) { 071 iRequiredConfig = new Hashtable<CourseRequest, Config>(); 072 iRequiredSection = new Hashtable<CourseRequest, Hashtable<Subpart, Section>>(); 073 if (requiredSections != null) { 074 for (Map.Entry<CourseRequest, Set<Section>> entry : requiredSections.entrySet()) { 075 Hashtable<Subpart, Section> subSection = new Hashtable<Subpart, Section>(); 076 iRequiredSection.put(entry.getKey(), subSection); 077 for (Section section : entry.getValue()) { 078 if (subSection.isEmpty()) 079 iRequiredConfig.put(entry.getKey(), section.getSubpart().getConfig()); 080 subSection.put(section.getSubpart(), section); 081 } 082 } 083 } 084 } 085 086 @Override 087 public void setRequiredFreeTimes(Set<FreeTimeRequest> requiredFreeTimes) { 088 iRequiredFreeTimes = requiredFreeTimes; 089 } 090 091 @Override 092 public BranchBoundNeighbour select(Assignment<Request, Enrollment> assignment, Student student) { 093 return new Selection(student, assignment).select(); 094 } 095 096 @Override 097 public void setModel(OnlineSectioningModel model) { 098 super.setModel(model); 099 } 100 101 /** 102 * Extension of {@link org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection.Selection} including checking of 103 * required free times and sections. 104 * 105 */ 106 public class Selection extends BranchBoundSelection.Selection { 107 public Selection(Student student, Assignment<Request, Enrollment> assignment) { 108 super(student, assignment); 109 } 110 111 /** 112 * Check if the given enrollment is allowed 113 * @param idx enrollment index 114 * @param enrollment enrollment 115 * @return true if allowed (there is no conflict with required sections or free times) 116 */ 117 public boolean isAllowed(int idx, Enrollment enrollment) { 118 if (enrollment.isCourseRequest()) { 119 CourseRequest request = (CourseRequest) enrollment.getRequest(); 120 if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request)) return false; 121 Config reqConfig = iRequiredConfig.get(request); 122 if (reqConfig != null) { 123 if (!reqConfig.equals(enrollment.getConfig())) 124 return false; 125 Hashtable<Subpart, Section> reqSections = iRequiredSection.get(request); 126 for (Section section : enrollment.getSections()) { 127 Section reqSection = reqSections.get(section.getSubpart()); 128 if (reqSection == null) 129 continue; 130 if (!section.equals(reqSection)) 131 return false; 132 } 133 } 134 } else if (iRequiredFreeTimes.contains(enrollment.getRequest())) { 135 if (enrollment.getAssignments() == null || enrollment.getAssignments().isEmpty()) 136 return false; 137 } 138 return true; 139 } 140 141 @Override 142 public boolean inConflict(int idx, Enrollment enrollment) { 143 return super.inConflict(idx, enrollment) || !isAllowed(idx, enrollment); 144 } 145 146 @Override 147 public Enrollment firstConflict(int idx, Enrollment enrollment) { 148 Enrollment conflict = super.firstConflict(idx, enrollment); 149 if (conflict != null) 150 return conflict; 151 return (isAllowed(idx, enrollment) ? null : enrollment); 152 } 153 154 @Override 155 protected boolean canLeaveUnassigned(Request request) { 156 if (request instanceof CourseRequest) { 157 if (iRequiredConfig.get(request) != null) 158 return false; 159 } else if (iRequiredFreeTimes.contains(request)) 160 return false; 161 return true; 162 } 163 164 @Override 165 protected List<Enrollment> values(final CourseRequest request) { 166 if (iRequiredUnassinged != null && iRequiredUnassinged.contains(request)) 167 return new ArrayList<Enrollment>(); 168 return super.values(request); 169 } 170 171 @Override 172 protected double getWeight(Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts, 173 Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) { 174 double weight = super.getWeight(enrollment, distanceConflicts, timeOverlappingConflicts); 175 if (enrollment.isCourseRequest() && iPreferredSections != null) { 176 Set<Section> preferred = iPreferredSections.get(enrollment.getRequest()); 177 if (preferred != null && !preferred.isEmpty()) { 178 double nrPreferred = 0; 179 for (Section section : enrollment.getSections()) 180 if (preferred.contains(section)) 181 nrPreferred++; 182 double preferredFraction = nrPreferred / preferred.size(); 183 weight *= 1.0 + iPreferenceFactor * preferredFraction; 184 } 185 } 186 return weight; 187 } 188 189 @Override 190 protected double getBound(Request r) { 191 double bound = super.getBound(r); 192 if (r instanceof CourseRequest) { 193 Set<Section> preferred = iPreferredSections.get(r); 194 if (preferred != null && !preferred.isEmpty()) 195 bound *= (1.0 + iPreferenceFactor); 196 } 197 return bound; 198 } 199 200 } 201 202 @Override 203 public void setRequiredUnassinged(Set<CourseRequest> requiredUnassignedRequests) { 204 iRequiredUnassinged = requiredUnassignedRequests; 205 } 206}