001 package net.sf.cpsolver.studentsct;
002
003 import java.util.Enumeration;
004 import java.util.HashSet;
005 import java.util.Hashtable;
006 import java.util.Iterator;
007 import java.util.Set;
008 import java.util.Vector;
009
010 import org.apache.log4j.Logger;
011
012 import net.sf.cpsolver.ifs.model.Constraint;
013 import net.sf.cpsolver.ifs.model.ConstraintListener;
014 import net.sf.cpsolver.ifs.model.Model;
015 import net.sf.cpsolver.ifs.model.Value;
016 import net.sf.cpsolver.ifs.util.DataProperties;
017 import net.sf.cpsolver.ifs.util.EnumerableHashSet;
018 import net.sf.cpsolver.studentsct.constraint.SectionLimit;
019 import net.sf.cpsolver.studentsct.constraint.StudentConflict;
020 import net.sf.cpsolver.studentsct.extension.DistanceConflict;
021 import net.sf.cpsolver.studentsct.model.Config;
022 import net.sf.cpsolver.studentsct.model.CourseRequest;
023 import net.sf.cpsolver.studentsct.model.Enrollment;
024 import net.sf.cpsolver.studentsct.model.Offering;
025 import net.sf.cpsolver.studentsct.model.Request;
026 import net.sf.cpsolver.studentsct.model.Section;
027 import net.sf.cpsolver.studentsct.model.Student;
028 import net.sf.cpsolver.studentsct.model.Subpart;
029
030 /**
031 * Student sectioning model.
032 *
033 * <br><br>
034 *
035 * @version
036 * StudentSct 1.1 (Student Sectioning)<br>
037 * Copyright (C) 2007 Tomáš Müller<br>
038 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
039 * Lazenska 391, 76314 Zlin, Czech Republic<br>
040 * <br>
041 * This library is free software; you can redistribute it and/or
042 * modify it under the terms of the GNU Lesser General Public
043 * License as published by the Free Software Foundation; either
044 * version 2.1 of the License, or (at your option) any later version.
045 * <br><br>
046 * This library is distributed in the hope that it will be useful,
047 * but 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.
050 * <br><br>
051 * You should have received a copy of the GNU Lesser General Public
052 * License along with this library; if not, write to the Free Software
053 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
054 */
055 public class StudentSectioningModel extends Model {
056 private static Logger sLog = Logger.getLogger(StudentSectioningModel.class);
057 private Vector iStudents = new Vector();
058 private Vector iOfferings = new Vector();
059 private HashSet iCompleteStudents = new HashSet();
060 private double iTotalValue = 0.0;
061 private DataProperties iProperties;
062 private DistanceConflict iDistanceConflict = null;
063 private int iNrDummyStudents = 0, iNrDummyRequests = 0, iNrAssignedDummyRequests = 0, iNrCompleteDummyStudents = 0;
064
065 /**
066 * Constructor
067 * @param properties configuration
068 */
069 public StudentSectioningModel(DataProperties properties) {
070 super();
071 iAssignedVariables = new EnumerableHashSet();
072 iUnassignedVariables = new EnumerableHashSet();
073 iPerturbVariables = new EnumerableHashSet();
074 SectionLimit sectionLimit = new SectionLimit(properties);
075 addGlobalConstraint(sectionLimit);
076 sectionLimit.addConstraintListener(new ConstraintListener() {
077 public void constraintBeforeAssigned(long iteration, Constraint constraint, Value assigned, Set unassigned) {
078 Enrollment enrollment = (Enrollment)assigned;
079 if (enrollment.getStudent().isDummy())
080 for (Iterator i=unassigned.iterator();i.hasNext();) {
081 Enrollment conflict = (Enrollment)i.next();
082 if (!conflict.getStudent().isDummy()) {
083 sLog.warn("Enrolment of a real student "+conflict.getStudent()+" is unassigned "+
084 "\n -- "+conflict+
085 "\ndue to an enrollment of a dummy student "+enrollment.getStudent()+" " +
086 "\n -- "+enrollment);
087 }
088 }
089 }
090 public void constraintAfterAssigned(long iteration, Constraint constraint, Value assigned, Set unassigned) {}
091 });
092 iProperties = properties;
093 }
094
095 /**
096 * Students
097 */
098 public Vector getStudents() {
099 return iStudents;
100 }
101
102 /**
103 * Students with complete schedules (see {@link Student#isComplete()})
104 */
105 public Set getCompleteStudents() {
106 return iCompleteStudents;
107 }
108
109 /**
110 * Add a student into the model
111 */
112 public void addStudent(Student student) {
113 iStudents.addElement(student);
114 if (student.isDummy()) iNrDummyStudents++;
115 StudentConflict conflict = new StudentConflict();
116 for (Enumeration e=student.getRequests().elements();e.hasMoreElements();) {
117 Request request = (Request)e.nextElement();
118 conflict.addVariable(request);
119 addVariable(request);
120 if (student.isDummy()) iNrDummyRequests++;
121 }
122 addConstraint(conflict);
123 if (student.isComplete())
124 iCompleteStudents.add(student);
125 }
126
127 /**
128 * Remove a student from the model
129 */
130 public void removeStudent(Student student) {
131 iStudents.removeElement(student);
132 if (student.isDummy()) iNrDummyStudents--;
133 if (student.isComplete()) iCompleteStudents.remove(student);
134 StudentConflict conflict = null;
135 for (Enumeration e=student.getRequests().elements();e.hasMoreElements();) {
136 Request request = (Request)e.nextElement();
137 for (Enumeration f=request.constraints().elements();conflict==null && f.hasMoreElements();) {
138 Constraint c = (Constraint)f.nextElement();
139 if (c instanceof StudentConflict) conflict = (StudentConflict)c;
140 }
141 conflict.removeVariable(request);
142 removeVariable(request);
143 if (student.isDummy()) iNrDummyRequests--;
144 }
145 removeConstraint(conflict);
146 }
147
148 /**
149 * List of offerings
150 */
151 public Vector getOfferings() {
152 return iOfferings;
153 }
154
155 /**
156 * Add an offering into the model
157 */
158 public void addOffering(Offering offering) {
159 iOfferings.add(offering);
160 }
161
162 /**
163 * Number of students with complete schedule
164 */
165 public int nrComplete() {
166 return getCompleteStudents().size();
167 }
168
169 /**
170 * Model info
171 */
172 public Hashtable getInfo() {
173 Hashtable info = super.getInfo();
174 info.put("Students with complete schedule" ,
175 sDoubleFormat.format(100.0*nrComplete()/getStudents().size())+"% ("+nrComplete()+"/"+getStudents().size()+")");
176 if (getDistanceConflict()!=null)
177 info.put("Student distance conflicts", sDoubleFormat.format(getDistanceConflict().getTotalNrConflicts()));
178 return info;
179 }
180
181 /**
182 * Overall solution value
183 */
184 public double getTotalValue() {
185 return iTotalValue;
186 }
187
188 /**
189 * Called after an enrollment was assigned to a request. The list of complete students
190 * and the overall solution value are updated.
191 */
192 public void afterAssigned(long iteration, Value value) {
193 super.afterAssigned(iteration, value);
194 Enrollment enrollment = (Enrollment)value;
195 Student student = enrollment.getStudent();
196 if (student.isComplete())
197 iCompleteStudents.add(student);
198 iTotalValue += value.toDouble();
199 if (student.isDummy()) {
200 iNrAssignedDummyRequests++;
201 if (student.isComplete()) iNrCompleteDummyStudents++;
202 }
203 }
204
205 /**
206 * Called before an enrollment was unassigned from a request. The list of complete students
207 * and the overall solution value are updated.
208 */
209 public void afterUnassigned(long iteration, Value value) {
210 super.afterUnassigned(iteration, value);
211 Enrollment enrollment = (Enrollment)value;
212 Student student = enrollment.getStudent();
213 if (iCompleteStudents.contains(student) && !student.isComplete())
214 iCompleteStudents.remove(student);
215 iTotalValue -= value.toDouble();
216 if (student.isDummy()) {
217 iNrAssignedDummyRequests--;
218 if (student.isComplete()) iNrCompleteDummyStudents--;
219 }
220 }
221
222 /**
223 * Configuration
224 */
225 public DataProperties getProperties() {
226 return iProperties;
227 }
228
229 /**
230 * Empty online student sectioning infos for all sections (see {@link Section#getSpaceExpected()} and {@link Section#getSpaceHeld()}).
231 */
232 public void clearOnlineSectioningInfos() {
233 for (Enumeration e=iOfferings.elements();e.hasMoreElements();) {
234 Offering offering = (Offering)e.nextElement();
235 for (Enumeration f=offering.getConfigs().elements();f.hasMoreElements();) {
236 Config config = (Config)f.nextElement();
237 for (Enumeration g=config.getSubparts().elements();g.hasMoreElements();) {
238 Subpart subpart = (Subpart)g.nextElement();
239 for (Enumeration h=subpart.getSections().elements();h.hasMoreElements();) {
240 Section section = (Section)h.nextElement();
241 section.setSpaceExpected(0);
242 section.setSpaceHeld(0);
243 }
244 }
245 }
246 }
247 }
248
249 /**
250 * Compute online student sectioning infos for all sections (see {@link Section#getSpaceExpected()} and {@link Section#getSpaceHeld()}).
251 */
252 public void computeOnlineSectioningInfos() {
253 clearOnlineSectioningInfos();
254 for (Enumeration e=getStudents().elements();e.hasMoreElements();) {
255 Student student = (Student)e.nextElement();
256 if (!student.isDummy()) continue;
257 for (Enumeration f=student.getRequests().elements();f.hasMoreElements();) {
258 Request request = (Request)f.nextElement();
259 if (!(request instanceof CourseRequest)) continue;
260 CourseRequest courseRequest = (CourseRequest)request;
261 Enrollment enrollment = (Enrollment)courseRequest.getAssignment();
262 if (enrollment!=null) {
263 for (Iterator i=enrollment.getAssignments().iterator();i.hasNext();) {
264 Section section = (Section)i.next();
265 section.setSpaceHeld(courseRequest.getWeight()+section.getSpaceHeld());
266 }
267 }
268 Vector feasibleEnrollments = new Vector();
269 for (Enumeration g=courseRequest.values().elements();g.hasMoreElements();) {
270 Enrollment enrl = (Enrollment)g.nextElement();
271 boolean overlaps = false;
272 for (Enumeration h=student.getRequests().elements();h.hasMoreElements();) {
273 CourseRequest otherCourseRequest = (CourseRequest)h.nextElement();
274 if (otherCourseRequest.equals(courseRequest)) continue;
275 Enrollment otherErollment = (Enrollment)otherCourseRequest.getAssignment();
276 if (otherErollment==null) continue;
277 if (enrl.isOverlapping(otherErollment)) {
278 overlaps = true; break;
279 }
280 }
281 if (!overlaps)
282 feasibleEnrollments.add(enrl);
283 }
284 double increment = courseRequest.getWeight() / feasibleEnrollments.size();
285 for (Enumeration g=feasibleEnrollments.elements();g.hasMoreElements();) {
286 Enrollment feasibleEnrollment = (Enrollment)g.nextElement();
287 for (Iterator i=feasibleEnrollment.getAssignments().iterator();i.hasNext();) {
288 Section section = (Section)i.next();
289 section.setSpaceExpected(section.getSpaceExpected()+increment);
290 }
291 }
292 }
293 }
294 }
295
296 /**
297 * Sum of weights of all requests that are not assigned (see {@link Request#getWeight()}).
298 */
299 public double getUnassignedRequestWeight() {
300 double weight = 0.0;
301 for (Enumeration e=unassignedVariables().elements();e.hasMoreElements();) {
302 Request request = (Request)e.nextElement();
303 weight += request.getWeight();
304 }
305 return weight;
306 }
307
308 /**
309 * Sum of weights of all requests (see {@link Request#getWeight()}).
310 */
311 public double getTotalRequestWeight() {
312 double weight = 0.0;
313 for (Enumeration e=variables().elements();e.hasMoreElements();) {
314 Request request = (Request)e.nextElement();
315 weight += request.getWeight();
316 }
317 return weight;
318 }
319
320 /**
321 * Set distance conflict extension
322 */
323 public void setDistanceConflict(DistanceConflict dc) {
324 iDistanceConflict = dc;
325 }
326
327 /**
328 * Return distance conflict extension
329 */
330 public DistanceConflict getDistanceConflict() {
331 return iDistanceConflict;
332 }
333
334 /**
335 * Average priority of unassigned requests (see {@link Request#getPriority()})
336 */
337 public double avgUnassignPriority() {
338 double totalPriority = 0.0;
339 for (Enumeration e=unassignedVariables().elements();e.hasMoreElements();) {
340 Request request = (Request)e.nextElement();
341 if (request.isAlternative()) continue;
342 totalPriority += request.getPriority();
343 }
344 return 1.0 + totalPriority / unassignedVariables().size();
345 }
346
347 /**
348 * Average number of requests per student (see {@link Student#getRequests()})
349 */
350 public double avgNrRequests() {
351 double totalRequests = 0.0;
352 int totalStudents = 0;
353 for (Enumeration e=getStudents().elements();e.hasMoreElements();) {
354 Student student = (Student)e.nextElement();
355 if (student.nrRequests()==0) continue;
356 totalRequests += student.nrRequests();
357 totalStudents ++;
358 }
359 return totalRequests / totalStudents;
360 }
361
362 /** Number of last like ({@link Student#isDummy()} equals true) students. */
363 public int getNrLastLikeStudents(boolean precise) {
364 if (!precise) return iNrDummyStudents;
365 int nrLastLikeStudents = 0;
366 for (Enumeration e=getStudents().elements();e.hasMoreElements();) {
367 Student student = (Student)e.nextElement();
368 if (student.isDummy()) nrLastLikeStudents++;
369 }
370 return nrLastLikeStudents;
371 }
372
373 /** Number of real ({@link Student#isDummy()} equals false) students. */
374 public int getNrRealStudents(boolean precise) {
375 if (!precise) return getStudents().size()-iNrDummyStudents;
376 int nrRealStudents = 0;
377 for (Enumeration e=getStudents().elements();e.hasMoreElements();) {
378 Student student = (Student)e.nextElement();
379 if (!student.isDummy()) nrRealStudents++;
380 }
381 return nrRealStudents;
382 }
383
384 /** Number of last like ({@link Student#isDummy()} equals true) students with a complete schedule ({@link Student#isComplete()} equals true). */
385 public int getNrCompleteLastLikeStudents(boolean precise) {
386 if (!precise) return iNrCompleteDummyStudents;
387 int nrLastLikeStudents = 0;
388 for (Iterator i=getCompleteStudents().iterator();i.hasNext();) {
389 Student student = (Student)i.next();
390 if (student.isDummy()) nrLastLikeStudents++;
391 }
392 return nrLastLikeStudents;
393 }
394
395 /** Number of real ({@link Student#isDummy()} equals false) students with a complete schedule ({@link Student#isComplete()} equals true). */
396 public int getNrCompleteRealStudents(boolean precise) {
397 if (!precise) return getCompleteStudents().size()-iNrCompleteDummyStudents;
398 int nrRealStudents = 0;
399 for (Iterator i=getCompleteStudents().iterator();i.hasNext();) {
400 Student student = (Student)i.next();
401 if (!student.isDummy()) nrRealStudents++;
402 }
403 return nrRealStudents;
404 }
405
406 /** Number of requests from last-like ({@link Student#isDummy()} equals true) students. */
407 public int getNrLastLikeRequests(boolean precise) {
408 if (!precise) return iNrDummyRequests;
409 int nrLastLikeRequests = 0;
410 for (Enumeration e=variables().elements();e.hasMoreElements();) {
411 Request request = (Request)e.nextElement();
412 if (request.getStudent().isDummy()) nrLastLikeRequests++;
413 }
414 return nrLastLikeRequests;
415 }
416
417 /** Number of requests from real ({@link Student#isDummy()} equals false) students. */
418 public int getNrRealRequests(boolean precise) {
419 if (!precise) return variables().size()-iNrDummyRequests;
420 int nrRealRequests = 0;
421 for (Enumeration e=variables().elements();e.hasMoreElements();) {
422 Request request = (Request)e.nextElement();
423 if (!request.getStudent().isDummy()) nrRealRequests++;
424 }
425 return nrRealRequests;
426 }
427
428 /** Number of requests from last-like ({@link Student#isDummy()} equals true) students that are assigned. */
429 public int getNrAssignedLastLikeRequests(boolean precise) {
430 if (!precise) return iNrAssignedDummyRequests;
431 int nrLastLikeRequests = 0;
432 for (Enumeration e=assignedVariables().elements();e.hasMoreElements();) {
433 Request request = (Request)e.nextElement();
434 if (request.getStudent().isDummy()) nrLastLikeRequests++;
435 }
436 return nrLastLikeRequests;
437 }
438
439 /** Number of requests from real ({@link Student#isDummy()} equals false) students that are assigned. */
440 public int getNrAssignedRealRequests(boolean precise) {
441 if (!precise) return assignedVariables().size()-iNrAssignedDummyRequests;
442 int nrRealRequests = 0;
443 for (Enumeration e=assignedVariables().elements();e.hasMoreElements();) {
444 Request request = (Request)e.nextElement();
445 if (!request.getStudent().isDummy()) nrRealRequests++;
446 }
447 return nrRealRequests;
448 }
449
450 /**
451 * Model extended info. Some more information (that is more expensive to compute) is added to an ordinary {@link Model#getInfo()}.
452 */
453 public Hashtable getExtendedInfo() {
454 Hashtable info = getInfo();
455 int nrLastLikeStudents = getNrLastLikeStudents(true);
456 if (nrLastLikeStudents!=0 && nrLastLikeStudents!=getStudents().size()) {
457 int nrRealStudents = getStudents().size() - nrLastLikeStudents;
458 int nrLastLikeCompleteStudents = getNrCompleteLastLikeStudents(true);
459 int nrRealCompleteStudents = getCompleteStudents().size()-nrLastLikeCompleteStudents;
460 info.put("Last-like students with complete schedule" ,
461 sDoubleFormat.format(100.0*nrLastLikeCompleteStudents/nrLastLikeStudents)+"% ("+nrLastLikeCompleteStudents+"/"+nrLastLikeStudents+")");
462 info.put("Real students with complete schedule" ,
463 sDoubleFormat.format(100.0*nrRealCompleteStudents/nrRealStudents)+"% ("+nrRealCompleteStudents+"/"+nrRealStudents+")");
464 int nrLastLikeRequests = getNrLastLikeRequests(true);
465 int nrRealRequests = variables().size()-nrLastLikeRequests;
466 int nrLastLikeAssignedRequests = getNrAssignedLastLikeRequests(true);
467 int nrRealAssignedRequests = assignedVariables().size()-nrLastLikeAssignedRequests;
468 info.put("Last-like assigned requests" ,
469 sDoubleFormat.format(100.0*nrLastLikeAssignedRequests/nrLastLikeRequests)+"% ("+nrLastLikeAssignedRequests+"/"+nrLastLikeRequests+")");
470 info.put("Real assigned requests" ,
471 sDoubleFormat.format(100.0*nrRealAssignedRequests/nrRealRequests)+"% ("+nrRealAssignedRequests+"/"+nrRealRequests+")");
472 }
473 info.put("Average unassigned priority", sDoubleFormat.format(avgUnassignPriority()));
474 info.put("Average number of requests", sDoubleFormat.format(avgNrRequests()));
475 info.put("Unassigned request weight", sDoubleFormat.format(getUnassignedRequestWeight())+" / "+sDoubleFormat.format(getTotalRequestWeight()));
476 return info;
477 }
478
479 }