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