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; 008 009import org.cpsolver.ifs.assignment.Assignment; 010import org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection; 011import org.cpsolver.ifs.util.DataProperties; 012import org.cpsolver.studentsct.StudentSectioningModel; 013import org.cpsolver.studentsct.model.CourseRequest; 014import org.cpsolver.studentsct.model.Enrollment; 015import org.cpsolver.studentsct.model.Request; 016 017 018/** 019 * Randomized backtracking-based neighbour selection. This class extends 020 * {@link RandomizedBacktrackNeighbourSelection}, however, only a randomly 021 * selected subset of enrollments of each request is considered ( 022 * {@link CourseRequest#computeRandomEnrollments(Assignment, int)} with the given limit is 023 * used). 024 * 025 * <br> 026 * <br> 027 * Parameters: <br> 028 * <table border='1' summary='Related Solver Parameters'> 029 * <tr> 030 * <th>Parameter</th> 031 * <th>Type</th> 032 * <th>Comment</th> 033 * </tr> 034 * <tr> 035 * <td>Neighbour.MaxValues</td> 036 * <td>{@link Integer}</td> 037 * <td>Limit on the number of enrollments to be visited of each 038 * {@link CourseRequest}.</td> 039 * </tr> 040 * </table> 041 * <br> 042 * <br> 043 * 044 * @version StudentSct 1.3 (Student Sectioning)<br> 045 * Copyright (C) 2007 - 2014 Tomas Muller<br> 046 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 047 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 048 * <br> 049 * This library is free software; you can redistribute it and/or modify 050 * it under the terms of the GNU Lesser General Public License as 051 * published by the Free Software Foundation; either version 3 of the 052 * License, or (at your option) any later version. <br> 053 * <br> 054 * This library is distributed in the hope that it will be useful, but 055 * WITHOUT ANY WARRANTY; without even the implied warranty of 056 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 057 * Lesser General Public License for more details. <br> 058 * <br> 059 * You should have received a copy of the GNU Lesser General Public 060 * License along with this library; if not see 061 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 062 */ 063public class RandomizedBacktrackNeighbourSelection extends BacktrackNeighbourSelection<Request, Enrollment> { 064 private int iMaxValues = 100; 065 066 /** 067 * Constructor 068 * 069 * @param properties 070 * configuration 071 * @throws Exception thrown when the initialization fails 072 */ 073 public RandomizedBacktrackNeighbourSelection(DataProperties properties) throws Exception { 074 super(properties); 075 iMaxValues = properties.getPropertyInt("Neighbour.MaxValues", iMaxValues); 076 } 077 078 /** 079 * List of values of a variable. 080 * {@link CourseRequest#computeRandomEnrollments(Assignment, int)} with the provided 081 * limit is used for a {@link CourseRequest}. 082 */ 083 @Override 084 protected Iterator<Enrollment> values(BacktrackNeighbourSelection<Request, Enrollment>.BacktrackNeighbourSelectionContext context, Request variable) { 085 if (variable instanceof CourseRequest) { 086 final CourseRequest request = (CourseRequest)variable; 087 final StudentSectioningModel model = (StudentSectioningModel)context.getModel(); 088 final Assignment<Request, Enrollment> assignment = context.getAssignment(); 089 List<Enrollment> values = (iMaxValues > 0 ? request.computeRandomEnrollments(assignment, iMaxValues) : request.computeEnrollments(assignment)); 090 Collections.sort(values, new Comparator<Enrollment>() { 091 private HashMap<Enrollment, Double> iValues = new HashMap<Enrollment, Double>(); 092 private Double value(Enrollment e) { 093 Double value = iValues.get(e); 094 if (value == null) { 095 value = model.getStudentWeights().getWeight(assignment, e, 096 (model.getDistanceConflict() == null ? null : model.getDistanceConflict().conflicts(e)), 097 (model.getTimeOverlaps() == null ? null : model.getTimeOverlaps().freeTimeConflicts(e))); 098 iValues.put(e, value); 099 } 100 return value; 101 } 102 @Override 103 public int compare(Enrollment e1, Enrollment e2) { 104 if (e1.equals(assignment.getValue(request))) return -1; 105 if (e2.equals(assignment.getValue(request))) return 1; 106 Double v1 = value(e1), v2 = value(e2); 107 return v1.equals(v2) ? e1.compareTo(assignment, e2) : v2.compareTo(v1); 108 } 109 }); 110 return values.iterator(); 111 } else { 112 return variable.computeEnrollments(context.getAssignment()).iterator(); 113 } 114 } 115}