001package org.cpsolver.studentsct.heuristics.selection; 002 003import org.cpsolver.ifs.assignment.Assignment; 004import org.cpsolver.ifs.model.Neighbour; 005import org.cpsolver.ifs.solution.Solution; 006import org.cpsolver.ifs.solver.Solver; 007import org.cpsolver.ifs.util.DataProperties; 008import org.cpsolver.ifs.util.Progress; 009import org.cpsolver.studentsct.heuristics.studentord.StudentChoiceOrder; 010import org.cpsolver.studentsct.model.CourseRequest; 011import org.cpsolver.studentsct.model.Enrollment; 012import org.cpsolver.studentsct.model.Request; 013import org.cpsolver.studentsct.model.Student; 014import org.cpsolver.studentsct.model.Request.RequestPriority; 015 016/** 017 * This selection is very much like {@link BranchBoundSelection}, but only critical 018 * course requests are assigned (see {@link CourseRequest#isCritical()}. 019 * Students that do not have any unassigned critical courses are skipped. 020 * 021 * <br> 022 * <br> 023 * Parameters: <br> 024 * <table border='1' summary='Related Solver Parameters'> 025 * <tr> 026 * <th>Parameter</th> 027 * <th>Type</th> 028 * <th>Comment</th> 029 * </tr> 030 * <tr> 031 * <td>Neighbour.CriticalCoursesBranchAndBoundTimeout</td> 032 * <td>{@link Integer}</td> 033 * <td>Timeout for each neighbour selection (in milliseconds).</td> 034 * </tr> 035 * <tr> 036 * <td>Neighbour.BranchAndBoundMinimizePenalty</td> 037 * <td>{@link Boolean}</td> 038 * <td>If true, section penalties (instead of section values) are minimized: 039 * overall penalty is minimized together with the maximization of the number of 040 * assigned requests and minimization of distance conflicts -- this variant is 041 * to better mimic the case when students can choose their sections (section 042 * times).</td> 043 * </tr> 044 * </table> 045 * <br> 046 * <br> 047 * 048 * @version StudentSct 1.3 (Student Sectioning)<br> 049 * Copyright (C) 2007 - 2014 Tomáš Müller<br> 050 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 051 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 052 * <br> 053 * This library is free software; you can redistribute it and/or modify 054 * it under the terms of the GNU Lesser General Public License as 055 * published by the Free Software Foundation; either version 3 of the 056 * License, or (at your option) any later version. <br> 057 * <br> 058 * This library is distributed in the hope that it will be useful, but 059 * WITHOUT ANY WARRANTY; without even the implied warranty of 060 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 061 * Lesser General Public License for more details. <br> 062 * <br> 063 * You should have received a copy of the GNU Lesser General Public 064 * License along with this library; if not see 065 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 066 */ 067public class CriticalCoursesBranchAndBoundSelection extends BranchBoundSelection { 068 protected boolean iMPP = false; 069 private RequestPriority iPriority; 070 071 public CriticalCoursesBranchAndBoundSelection(DataProperties properties, RequestPriority priority) { 072 super(properties); 073 iMPP = properties.getPropertyBoolean("General.MPP", false); 074 iTimeout = properties.getPropertyInt("Neighbour.CriticalCoursesBranchAndBoundTimeout", 10000); 075 iPriority = priority; 076 if (iOrder instanceof StudentChoiceOrder) { 077 ((StudentChoiceOrder)iOrder).setCriticalOnly(true); 078 ((StudentChoiceOrder)iOrder).setRequestPriority(iPriority); 079 } 080 } 081 082 public CriticalCoursesBranchAndBoundSelection(DataProperties properties) { 083 this(properties, RequestPriority.Critical); 084 } 085 086 @Override 087 public void init(Solver<Request, Enrollment> solver) { 088 init(solver, iPriority.name() + " Courses B&B" + (iFilter == null ? "" : " (" + iFilter.getName().toLowerCase() + " students)") + "..."); 089 } 090 091 @Override 092 public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) { 093 Student student = null; 094 while ((student = nextStudent()) != null) { 095 Progress.getInstance(solution.getModel()).incProgress(); 096 if (student.hasUnassignedCritical(solution.getAssignment(), iPriority)) { 097 // only consider students that have some unassigned critical course requests 098 Neighbour<Request, Enrollment> neighbour = getSelection(solution.getAssignment(), student).select(); 099 if (neighbour != null) return neighbour; 100 } 101 } 102 return null; 103 } 104 105 @Override 106 public Selection getSelection(Assignment<Request, Enrollment> assignment, Student student) { 107 return new CriticalCoursesSelection(student, assignment); 108 } 109 110 public class CriticalCoursesSelection extends Selection { 111 112 public CriticalCoursesSelection(Student student, Assignment<Request, Enrollment> assignment) { 113 super(student, assignment); 114 } 115 116 public boolean isCritical(int idx) { 117 for (int i = idx; i < iStudent.getRequests().size(); i++) { 118 Request r = iStudent.getRequests().get(i); 119 if (!r.isAlternative() && iPriority.isCritical(r)) return true; 120 } 121 return false; 122 } 123 124 @Override 125 public void backTrack(int idx) { 126 if (!isCritical(idx)) { 127 if (iMinimizePenalty) { 128 if (getBestAssignment() == null || (getNrAssigned() > getBestNrAssigned() || (getNrAssigned() == getBestNrAssigned() && getPenalty() < getBestValue()))) 129 saveBest(); 130 } else { 131 if (getBestAssignment() == null || getValue() < getBestValue()) 132 saveBest(); 133 } 134 return; 135 } 136 if (idx < iAssignment.length && !iPriority.isCritical(iStudent.getRequests().get(idx)) && (!iMPP || iStudent.getRequests().get(idx).getInitialAssignment() == null)) { 137 // not done yet && not critical && not initial >> leave unassigned 138 backTrack(idx + 1); 139 } else { 140 super.backTrack(idx); 141 } 142 } 143 } 144}