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