001package org.cpsolver.coursett.neighbourhoods; 002 003import java.util.Collection; 004import java.util.HashSet; 005import java.util.Map; 006import java.util.Set; 007 008import org.cpsolver.coursett.heuristics.NeighbourSelectionWithSuggestions; 009import org.cpsolver.coursett.model.Lecture; 010import org.cpsolver.coursett.model.Placement; 011import org.cpsolver.ifs.assignment.Assignment; 012import org.cpsolver.ifs.model.Constraint; 013import org.cpsolver.ifs.model.Neighbour; 014import org.cpsolver.ifs.model.SimpleNeighbour; 015import org.cpsolver.ifs.solution.Solution; 016import org.cpsolver.ifs.util.DataProperties; 017import org.cpsolver.ifs.util.ToolBox; 018 019/** 020 * A simple neighbor selection based on {@link NeighbourSelectionWithSuggestions}, 021 * only triggering when there is an unassigned class. The selection picks a random unassigned 022 * class and tries to do a limited-depth search up to the Neighbour.SuggestionDepth 023 * depth. If successful, the returned suggestion is always considered improving as 024 * it finds an assignment that increases the number of assigned classes. 025 * <br> 026 * 027 * @version IFS 1.3 (Iterative Forward Search)<br> 028 * Copyright (C) 2014 Tomáš Müller<br> 029 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 030 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 031 * <br> 032 * This library is free software; you can redistribute it and/or modify 033 * it under the terms of the GNU Lesser General Public License as 034 * published by the Free Software Foundation; either version 3 of the 035 * License, or (at your option) any later version. <br> 036 * <br> 037 * This library is distributed in the hope that it will be useful, but 038 * WITHOUT ANY WARRANTY; without even the implied warranty of 039 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 040 * Lesser General Public License for more details. <br> 041 * <br> 042 * You should have received a copy of the GNU Lesser General Public 043 * License along with this library; if not see 044 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 045 */ 046public class Suggestion extends NeighbourSelectionWithSuggestions { 047 private boolean iAllowUnassignments = false; 048 049 public Suggestion(DataProperties properties) throws Exception { 050 super(properties); 051 iAllowUnassignments = properties.getPropertyBoolean("Suggestion.AllowUnassignments", iAllowUnassignments); 052 } 053 054 @Override 055 public Neighbour<Lecture, Placement> selectNeighbour(Solution<Lecture, Placement> solution) { 056 Collection<Lecture> unassigned = solution.getModel().unassignedVariables(solution.getAssignment()); 057 if (!unassigned.isEmpty()) { 058 Lecture lecture = ToolBox.random(unassigned); 059 int depth = Math.max(2, ToolBox.random(iSuggestionDepth)); 060 Neighbour<Lecture, Placement> neigbour = selectNeighbourWithSuggestions(solution, lecture, depth); 061 if (neigbour != null) 062 return new SuggestionNeighbour(neigbour); 063 Placement placement = ToolBox.random(lecture.values(solution.getAssignment())); 064 if (placement != null) { 065 Set<Placement> conflicts = new HashSet<Placement>(); 066 if (iStat != null) 067 for (Map.Entry<Constraint<Lecture, Placement>, Set<Placement>> entry: solution.getModel().conflictConstraints(solution.getAssignment(), placement).entrySet()) { 068 iStat.constraintAfterAssigned(solution.getAssignment(), solution.getIteration(), entry.getKey(), placement, entry.getValue()); 069 conflicts.addAll(entry.getValue()); 070 } 071 else 072 conflicts = solution.getModel().conflictValues(solution.getAssignment(), placement); 073 if (!conflicts.contains(placement) && (iAllowUnassignments || conflicts.size() <= 1)) 074 return new SimpleNeighbour<Lecture, Placement>(lecture, placement, conflicts); 075 } 076 } 077 return null; 078 } 079 080 /** Simple @{link Neighbour} wrapper always returning -1 as the value */ 081 static class SuggestionNeighbour implements Neighbour<Lecture, Placement> { 082 Neighbour<Lecture, Placement> iNeigbour; 083 084 SuggestionNeighbour(Neighbour<Lecture, Placement> neigbour) { 085 iNeigbour = neigbour; 086 } 087 088 @Override 089 public void assign(Assignment<Lecture, Placement> assignment, long iteration) { 090 iNeigbour.assign(assignment, iteration); 091 } 092 093 @Override 094 public double value(Assignment<Lecture, Placement> assignment) { 095 return -1; 096 } 097 098 @Override 099 public Map<Lecture, Placement> assignments() { 100 return iNeigbour.assignments(); 101 } 102 } 103}