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.Request.RequestPriority; 012import org.cpsolver.studentsct.model.Student; 013 014/** 015 * This selection is very much like {@link BranchBoundSelection}, but only enough 016 * courses to a student is assigned to reach the min credit (see {@link Student#getMinCredit()}). 017 * Students that do not have the min credit set or have it set to zero 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.MinCreditBranchAndBoundTimeout</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 Tomáš Müller<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 MinCreditBranchAndBoundSelection extends BranchBoundSelection { 066 protected boolean iMPP = false; 067 private RequestPriority iPriority; 068 069 public MinCreditBranchAndBoundSelection(DataProperties properties, RequestPriority priority) { 070 super(properties); 071 iMPP = properties.getPropertyBoolean("General.MPP", false); 072 iTimeout = properties.getPropertyInt("Neighbour.MinCreditBranchAndBoundTimeout", 10000); 073 iPriority = priority; 074 } 075 076 public MinCreditBranchAndBoundSelection(DataProperties properties) { 077 this(properties, RequestPriority.Important); 078 } 079 080 @Override 081 public void init(Solver<Request, Enrollment> solver) { 082 init(solver, "Min Credit B&B..."); 083 } 084 085 @Override 086 public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) { 087 Student student = null; 088 while ((student = nextStudent()) != null) { 089 Progress.getInstance(solution.getModel()).incProgress(); 090 if (student.getMinCredit() > 0f && student.getAssignedCredit(solution.getAssignment()) < student.getMinCredit()) { 091 // only consider students with less than min credit assigned 092 Neighbour<Request, Enrollment> neighbour = getSelection(solution.getAssignment(), student).select(); 093 if (neighbour != null) return neighbour; 094 } 095 } 096 return null; 097 } 098 099 @Override 100 public Selection getSelection(Assignment<Request, Enrollment> assignment, Student student) { 101 return new MinCreditSelection(student, assignment); 102 } 103 104 public class MinCreditSelection extends Selection { 105 106 public MinCreditSelection(Student student, Assignment<Request, Enrollment> assignment) { 107 super(student, assignment); 108 } 109 110 public double getCredit(int idx) { 111 float credit = 0f; 112 for (int i = 0; i < idx; i++) 113 if (iAssignment[i] != null) 114 credit += iAssignment[i].getCredit(); 115 return credit; 116 } 117 118 public boolean isCritical(int idx) { 119 for (int i = idx; i < iStudent.getRequests().size(); i++) { 120 Request r = iStudent.getRequests().get(i); 121 if (!r.isAlternative() && iPriority.isCritical(r)) return true; 122 } 123 return false; 124 } 125 126 @Override 127 public void backTrack(int idx) { 128 if (getCredit(idx) >= iStudent.getMinCredit() && !isCritical(idx)) { 129 if (iMinimizePenalty) { 130 if (getBestAssignment() == null || (getNrAssigned() > getBestNrAssigned() || (getNrAssigned() == getBestNrAssigned() && getPenalty() < getBestValue()))) 131 saveBest(); 132 } else { 133 if (getBestAssignment() == null || getValue() < getBestValue()) 134 saveBest(); 135 } 136 return; 137 } 138 if (idx < iAssignment.length && getCredit(idx) >= iStudent.getMinCredit() && !iPriority.isCritical(iStudent.getRequests().get(idx)) && (!iMPP || iStudent.getRequests().get(idx).getInitialAssignment() == null)) { 139 // not done yet, over min credit but not critical >> leave unassigned 140 backTrack(idx + 1); 141 } else { 142 super.backTrack(idx); 143 } 144 } 145 } 146}