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 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 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 List<Enrollment> values = (iMaxValues > 0 ? request.computeRandomEnrollments(assignment, iMaxValues) : request.computeEnrollments(assignment)); 093 Collections.sort(values, new Comparator<Enrollment>() { 094 private HashMap<Enrollment, Double> iValues = new HashMap<Enrollment, Double>(); 095 private Double value(Enrollment e) { 096 Double value = iValues.get(e); 097 if (value == null) { 098 if (model.getStudentQuality() != null) 099 value = model.getStudentWeights().getWeight(assignment, e, model.getStudentQuality().conflicts(e)); 100 else 101 value = model.getStudentWeights().getWeight(assignment, e, 102 (model.getDistanceConflict() == null ? null : model.getDistanceConflict().conflicts(e)), 103 (model.getTimeOverlaps() == null ? null : model.getTimeOverlaps().conflicts(e))); 104 iValues.put(e, value); 105 } 106 return value; 107 } 108 @Override 109 public int compare(Enrollment e1, Enrollment e2) { 110 if (e1.equals(assignment.getValue(request))) return -1; 111 if (e2.equals(assignment.getValue(request))) return 1; 112 Double v1 = value(e1), v2 = value(e2); 113 return v1.equals(v2) ? e1.compareTo(assignment, e2) : v2.compareTo(v1); 114 } 115 }); 116 return values.iterator(); 117 } else { 118 return variable.computeEnrollments(context.getAssignment()).iterator(); 119 } 120 } 121 122 /** 123 * Check if the given conflicting enrollment can be unassigned 124 * @param conflict given enrollment 125 * @return if running MPP, do not unassign initial enrollments 126 */ 127 public boolean canUnassign(Enrollment enrollment, Enrollment conflict, Assignment<Request, Enrollment> assignment) { 128 if (conflict.getRequest().isMPP() && conflict.equals(conflict.getRequest().getInitialAssignment()) && 129 !enrollment.equals(enrollment.getRequest().getInitialAssignment())) return false; 130 if (conflict.getRequest() instanceof CourseRequest && ((CourseRequest)conflict.getRequest()).getFixedValue() != null) return false; 131 if (conflict.getRequest().getStudent().hasMinCredit()) { 132 float credit = conflict.getRequest().getStudent().getAssignedCredit(assignment) - conflict.getCredit(); 133 if (credit < conflict.getRequest().getStudent().getMinCredit()) return false; 134 } 135 if (!conflict.getRequest().isAlternative() && conflict.getRequest().getRequestPriority().isHigher(enrollment.getRequest())) return false; 136 if (iPreferPriorityStudents || conflict.getRequest().getRequestPriority().isSame(enrollment.getRequest())) { 137 if (conflict.getStudent().getPriority().isHigher(enrollment.getStudent())) return false; 138 } 139 return true; 140 } 141 142 @Override 143 protected boolean checkBound(List<Request> variables2resolve, int idx, int depth, Enrollment value, Set<Enrollment> conflicts) { 144 for (Enrollment conflict: conflicts) 145 if (!canUnassign(value, conflict, getContext().getAssignment())) return false; 146 return super.checkBound(variables2resolve, idx, depth, value, conflicts); 147 } 148}