001 package net.sf.cpsolver.studentsct.heuristics.selection;
002
003 import java.util.Enumeration;
004 import java.util.Iterator;
005 import java.util.Vector;
006
007 import org.apache.log4j.Logger;
008
009 import net.sf.cpsolver.ifs.solver.Solver;
010 import net.sf.cpsolver.ifs.util.DataProperties;
011 import net.sf.cpsolver.studentsct.StudentPreferencePenalties;
012 import net.sf.cpsolver.studentsct.model.Config;
013 import net.sf.cpsolver.studentsct.model.Course;
014 import net.sf.cpsolver.studentsct.model.CourseRequest;
015 import net.sf.cpsolver.studentsct.model.Enrollment;
016 import net.sf.cpsolver.studentsct.model.Request;
017 import net.sf.cpsolver.studentsct.model.Section;
018 import net.sf.cpsolver.studentsct.model.Student;
019 import net.sf.cpsolver.studentsct.model.Subpart;
020
021 /**
022 * Section given student using branch & bound algorithm with no unassignments allowed.
023 *
024 * <br><br>
025 * Parameters:
026 * <br>
027 * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
028 * <tr><td>Sectioning.UseStudentPreferencePenalties</td><td>{@link Boolean}</td><td>If true, {@link StudentPreferencePenalties} are used</td></tr>
029 * <tr><td>Sectioning.Distribution</td><td>{@link Integer}</td><td>When student preference penalties are used, defines which distribution is to be used (one
030 * of {@link StudentPreferencePenalties#sDistTypePreference}, {@link StudentPreferencePenalties#sDistTypePreferenceQuadratic}, {@link StudentPreferencePenalties#sDistTypePreferenceReverse},
031 * {@link StudentPreferencePenalties#sDistTypeUniform})</td></tr>
032 * <tr><td>Sectioning.UseOnlinePenalties</td><td>{@link Boolean}</td><td>If true, online sectioning penalties computed based on held/expected space are used.</td></tr>
033 * <tr><td>Sectioning.Epsilon</td><td>{@link Double}</td><td>When both online penalties and student preference penalties are used: a solution based on online penalties is computed first,
034 * this solution (and the given epsilon) is then used to setup bounds on online penalties for the solution that minimizes student preference penalties.
035 * Limit on online penalty is computed as (1+Section.Epsilon)*{@link Selection#getPenalty()}, i.e., only sections with penalty equal or below this limit can be used --
036 * among these the solution that minimizes student preference penalties is computed.</td></tr>
037 * </table>
038 * <br><br>
039 *
040 * @version
041 * StudentSct 1.1 (Student Sectioning)<br>
042 * Copyright (C) 2007 Tomáš Müller<br>
043 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
044 * Lazenska 391, 76314 Zlin, Czech Republic<br>
045 * <br>
046 * This library is free software; you can redistribute it and/or
047 * modify it under the terms of the GNU Lesser General Public
048 * License as published by the Free Software Foundation; either
049 * version 2.1 of the License, or (at your option) any later version.
050 * <br><br>
051 * This library is distributed in the hope that it will be useful,
052 * but WITHOUT ANY WARRANTY; without even the implied warranty of
053 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
054 * Lesser General Public License for more details.
055 * <br><br>
056 * You should have received a copy of the GNU Lesser General Public
057 * License along with this library; if not, write to the Free Software
058 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
059 */
060
061 public class OnlineSelection extends BranchBoundSelection {
062 private static Logger sLog = Logger.getLogger(OnlineSelection.class);
063 private int iDistributionType = -1;
064 private double iEpsilon = 0.05;
065 private boolean iUsePenalties = true;
066 private boolean iUseStudentPrefPenalties = false;
067 private BranchBoundSelection iBranchBound = null;
068
069 /**
070 * Constructor
071 * @param properties configuration
072 */
073 public OnlineSelection(DataProperties properties) {
074 super(properties);
075 iUseStudentPrefPenalties = properties.getPropertyBoolean("Sectioning.UseStudentPreferencePenalties", iUseStudentPrefPenalties);
076 iDistributionType = properties.getPropertyInt("Sectioning.Distribution", StudentPreferencePenalties.sDistTypePreference);
077 iEpsilon = properties.getPropertyDouble("Sectioning.Epsilon", iEpsilon);
078 iUsePenalties = properties.getPropertyBoolean("Sectioning.UseOnlinePenalties", iUsePenalties);
079 if (iUseStudentPrefPenalties && !properties.containsPropery("Sectioning.UseOnlinePenalties")) iUsePenalties = false;
080 if (iUsePenalties || !iUseStudentPrefPenalties)
081 iBranchBound = new BranchBoundSelection(properties);
082 iMinimizePenalty=true;
083 }
084
085 public void init(Solver solver) {
086 init(solver, "Online...");
087 }
088
089 /** Use student preference penalties */
090 public boolean isUseStudentPrefPenalties() {
091 return iUseStudentPrefPenalties;
092 }
093
094 /** Use online penalties */
095 public boolean isUsePenalties() {
096 return iUsePenalties;
097 }
098
099 /** Set online sectioning penalties to all sections of all courses of the given student */
100 private static void setPenalties(Student student) {
101 for (Enumeration e=student.getRequests().elements();e.hasMoreElements();) {
102 Request request = (Request)e.nextElement();
103 if (!(request instanceof CourseRequest)) continue;
104 CourseRequest courseRequest = (CourseRequest)request;
105 for (Enumeration f=courseRequest.getCourses().elements();f.hasMoreElements();) {
106 Course course = (Course)f.nextElement();
107 for (Enumeration g=course.getOffering().getConfigs().elements();g.hasMoreElements();) {
108 Config config = (Config)g.nextElement();
109 for (Enumeration h=config.getSubparts().elements();h.hasMoreElements();) {
110 Subpart subpart = (Subpart)h.nextElement();
111 for (Enumeration i=subpart.getSections().elements();i.hasMoreElements();) {
112 Section section = (Section)i.nextElement();
113 section.setPenalty(section.getOnlineSectioningPenalty());
114 }
115 }
116 }
117 }
118 courseRequest.clearCache();
119 }
120 }
121
122 /** Update online sectioning info after the given student is sectioned */
123 public void updateSpace(Student student) {
124 for (Enumeration e=student.getRequests().elements();e.hasMoreElements();) {
125 Request request = (Request)e.nextElement();
126 if (!(request instanceof CourseRequest)) continue;
127 CourseRequest courseRequest = (CourseRequest)request;
128 if (courseRequest.getAssignment()==null) return; //not enrolled --> no update
129 Enrollment enrollment = (Enrollment)courseRequest.getAssignment();
130 for (Iterator i=enrollment.getAssignments().iterator();i.hasNext();) {
131 Section section = (Section)i.next();
132 section.setSpaceHeld(section.getSpaceHeld()-courseRequest.getWeight());
133 //sLog.debug(" -- space held for "+section+" decreased by 1 (to "+section.getSpaceHeld()+")");
134 }
135 Vector feasibleEnrollments = new Vector();
136 for (Enumeration g=courseRequest.values().elements();g.hasMoreElements();) {
137 Enrollment enrl = (Enrollment)g.nextElement();
138 boolean overlaps = false;
139 for (Enumeration h=courseRequest.getStudent().getRequests().elements();h.hasMoreElements();) {
140 CourseRequest otherCourseRequest = (CourseRequest)h.nextElement();
141 if (otherCourseRequest.equals(courseRequest)) continue;
142 Enrollment otherErollment = (Enrollment)otherCourseRequest.getAssignment();
143 if (otherErollment==null) continue;
144 if (enrl.isOverlapping(otherErollment)) {
145 overlaps = true; break;
146 }
147 }
148 if (!overlaps)
149 feasibleEnrollments.add(enrl);
150 }
151 double decrement = courseRequest.getWeight() / feasibleEnrollments.size();
152 for (Enumeration g=feasibleEnrollments.elements();g.hasMoreElements();) {
153 Enrollment feasibleEnrollment = (Enrollment)g.nextElement();
154 for (Iterator i=feasibleEnrollment.getAssignments().iterator();i.hasNext();) {
155 Section section = (Section)i.next();
156 section.setSpaceExpected(section.getSpaceExpected()-decrement);
157 //sLog.debug(" -- space expected for "+section+" decreased by "+decrement+" (to "+section.getSpaceExpected()+")");
158 }
159 }
160 }
161 }
162
163 /**
164 * Branch & bound selection for a student
165 */
166 public Selection getSelection(Student student) {
167 if (iUsePenalties) setPenalties(student);
168 Selection selection = null;
169 if (iBranchBound!=null) selection = iBranchBound.getSelection(student);
170 if (iUseStudentPrefPenalties) selection = new EpsilonSelection(student, selection);
171 return selection;
172 }
173
174 /**
175 * Branch & bound selection for a student
176 */
177 public class EpsilonSelection extends BranchBoundSelection.Selection {
178 private StudentPreferencePenalties iPenalties = null;
179 private Selection iSelection = null;
180
181 /**
182 * Constructor
183 * @param student selected student
184 */
185 public EpsilonSelection(Student student, Selection selection) {
186 super(student);
187 iPenalties = new StudentPreferencePenalties(iDistributionType);
188 iSelection = selection;
189 }
190
191 /**
192 * Execute branch & bound, return the best found schedule for the selected student.
193 */
194 public BranchBoundNeighbour select() {
195 BranchBoundNeighbour onlineSelection = null;
196 if (iSelection!=null) {
197 onlineSelection = iSelection.select();
198 if (sDebug) sLog.debug("Online: "+onlineSelection);
199 }
200 BranchBoundNeighbour neighbour = super.select();
201 if (neighbour!=null) return neighbour;
202 if (onlineSelection!=null) return onlineSelection;
203 return null;
204 }
205
206 /** Assignment penalty */
207 protected double getAssignmentPenalty(int i) {
208 return iPenalties.getPenalty(iAssignment[i]) + iDistConfWeight*getNrDistanceConflicts(i);
209 }
210
211 public boolean isAllowed(int idx, Enrollment enrollment) {
212 if (iSelection==null || iSelection.getBestAssignment()==null || iSelection.getBestAssignment()[idx]==null) return true;
213 double bestPenalty = iSelection.getBestAssignment()[idx].getPenalty();
214 double limit = (iEpsilon<0?Math.max(0, bestPenalty):(bestPenalty<0?1-iEpsilon:1+iEpsilon)*bestPenalty);
215 if (enrollment.getPenalty()>limit) {
216 if (sDebug) sLog.debug(" -- enrollment "+enrollment+" was filtered out " +
217 "(penalty="+enrollment.getPenalty()+", best="+bestPenalty+", limit="+limit+")");
218 return false;
219 }
220 return true;
221 }
222
223 /** First conflicting enrollment */
224 public Enrollment firstConflict(int idx, Enrollment enrollment) {
225 Enrollment conflict = super.firstConflict(idx, enrollment);
226 if (conflict!=null) return conflict;
227 return (isAllowed(idx, enrollment)?null:enrollment);
228 }
229
230 /** Student preference penalties */
231 public StudentPreferencePenalties getPenalties() {
232 return iPenalties;
233 }
234 }
235 }