001package org.cpsolver.studentsct.heuristics; 002 003import java.util.Collections; 004import java.util.Comparator; 005import java.util.HashMap; 006import java.util.Iterator; 007import java.util.List; 008import java.util.Set; 009 010import org.cpsolver.ifs.assignment.Assignment; 011import org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection; 012import org.cpsolver.ifs.util.DataProperties; 013import org.cpsolver.studentsct.StudentSectioningModel; 014import org.cpsolver.studentsct.model.CourseRequest; 015import org.cpsolver.studentsct.model.Enrollment; 016import org.cpsolver.studentsct.model.Request; 017 018 019/** 020 * Randomized backtracking-based neighbour selection. This class extends 021 * {@link RandomizedBacktrackNeighbourSelection}, however, only a randomly 022 * selected subset of enrollments of each request is considered ( 023 * {@link CourseRequest#computeRandomEnrollments(Assignment, int)} with the given limit is 024 * used). 025 * 026 * <br> 027 * <br> 028 * Parameters: <br> 029 * <table border='1' summary='Related Solver Parameters'> 030 * <tr> 031 * <th>Parameter</th> 032 * <th>Type</th> 033 * <th>Comment</th> 034 * </tr> 035 * <tr> 036 * <td>Neighbour.MaxValues</td> 037 * <td>{@link Integer}</td> 038 * <td>Limit on the number of enrollments to be visited of each 039 * {@link CourseRequest}.</td> 040 * </tr> 041 * </table> 042 * <br> 043 * <br> 044 * 045 * @version StudentSct 1.3 (Student Sectioning)<br> 046 * Copyright (C) 2007 - 2014 Tomáš Müller<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 RandomizedBacktrackNeighbourSelection extends BacktrackNeighbourSelection<Request, Enrollment> { 065 private int iMaxValues = 100; 066 private boolean iPreferPriorityStudents = true; 067 068 /** 069 * Constructor 070 * 071 * @param properties 072 * configuration 073 * @throws Exception thrown when the initialization fails 074 */ 075 public RandomizedBacktrackNeighbourSelection(DataProperties properties) throws Exception { 076 super(properties); 077 iMaxValues = properties.getPropertyInt("Neighbour.MaxValues", iMaxValues); 078 iPreferPriorityStudents = properties.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection.AllIn", true); 079 } 080 081 /** 082 * List of values of a variable. 083 * {@link CourseRequest#computeRandomEnrollments(Assignment, int)} with the provided 084 * limit is used for a {@link CourseRequest}. 085 */ 086 @Override 087 protected Iterator<Enrollment> values(BacktrackNeighbourSelection<Request, Enrollment>.BacktrackNeighbourSelectionContext context, Request variable) { 088 if (variable instanceof CourseRequest) { 089 final CourseRequest request = (CourseRequest)variable; 090 final StudentSectioningModel model = (StudentSectioningModel)context.getModel(); 091 final Assignment<Request, Enrollment> assignment = context.getAssignment(); 092 final Enrollment current = assignment.getValue(request); 093 List<Enrollment> values = (iMaxValues > 0 ? request.computeRandomEnrollments(assignment, iMaxValues) : request.computeEnrollments(assignment)); 094 Collections.sort(values, new Comparator<Enrollment>() { 095 private HashMap<Enrollment, Double> iValues = new HashMap<Enrollment, Double>(); 096 private Double value(Enrollment e) { 097 Double value = iValues.get(e); 098 if (value == null) { 099 if (model.getStudentQuality() != null) 100 value = model.getStudentWeights().getWeight(assignment, e, model.getStudentQuality().conflicts(e)); 101 else 102 value = model.getStudentWeights().getWeight(assignment, e, 103 (model.getDistanceConflict() == null ? null : model.getDistanceConflict().conflicts(e)), 104 (model.getTimeOverlaps() == null ? null : model.getTimeOverlaps().conflicts(e))); 105 iValues.put(e, value); 106 } 107 return value; 108 } 109 @Override 110 public int compare(Enrollment e1, Enrollment e2) { 111 if (e1.equals(e2)) return 0; 112 if (e1.equals(current)) return -1; 113 if (e2.equals(current)) return 1; 114 Double v1 = value(e1), v2 = value(e2); 115 return v1.equals(v2) ? e1.compareTo(assignment, e2) : v2.compareTo(v1); 116 } 117 }); 118 return values.iterator(); 119 } else { 120 return variable.computeEnrollments(context.getAssignment()).iterator(); 121 } 122 } 123 124 /** 125 * Check if the given conflicting enrollment can be unassigned 126 * @param conflict given enrollment 127 * @return if running MPP, do not unassign initial enrollments 128 */ 129 public boolean canUnassign(Enrollment enrollment, Enrollment conflict, Assignment<Request, Enrollment> assignment) { 130 if (conflict.getRequest().isMPP() && conflict.equals(conflict.getRequest().getInitialAssignment()) && 131 !enrollment.equals(enrollment.getRequest().getInitialAssignment())) return false; 132 if (conflict.getRequest() instanceof CourseRequest && ((CourseRequest)conflict.getRequest()).getFixedValue() != null) return false; 133 if (conflict.getRequest().getStudent().hasMinCredit()) { 134 float credit = conflict.getRequest().getStudent().getAssignedCredit(assignment) - conflict.getCredit(); 135 if (credit < conflict.getRequest().getStudent().getMinCredit()) return false; 136 } 137 if (!conflict.getRequest().isAlternative() && conflict.getRequest().getRequestPriority().isHigher(enrollment.getRequest())) return false; 138 if (iPreferPriorityStudents || conflict.getRequest().getRequestPriority().isSame(enrollment.getRequest())) { 139 if (conflict.getStudent().getPriority().isHigher(enrollment.getStudent())) return false; 140 } 141 return true; 142 } 143 144 @Override 145 protected boolean checkBound(List<Request> variables2resolve, int idx, int depth, Enrollment value, Set<Enrollment> conflicts) { 146 for (Enrollment conflict: conflicts) 147 if (!canUnassign(value, conflict, getContext().getAssignment())) return false; 148 return super.checkBound(variables2resolve, idx, depth, value, conflicts); 149 } 150}