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