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}