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