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 * @author  Tomáš Müller
028 * @version IFS 1.3 (Iterative Forward Search)<br>
029 *          Copyright (C) 2014 Tomáš Müller<br>
030 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
031 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
032 * <br>
033 *          This library is free software; you can redistribute it and/or modify
034 *          it under the terms of the GNU Lesser General Public License as
035 *          published by the Free Software Foundation; either version 3 of the
036 *          License, or (at your option) any later version. <br>
037 * <br>
038 *          This library is distributed in the hope that it will be useful, but
039 *          WITHOUT ANY WARRANTY; without even the implied warranty of
040 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
041 *          Lesser General Public License for more details. <br>
042 * <br>
043 *          You should have received a copy of the GNU Lesser General Public
044 *          License along with this library; if not see
045 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
046 */
047public class Suggestion extends NeighbourSelectionWithSuggestions {
048    private boolean iAllowUnassignments = false;
049
050    public Suggestion(DataProperties properties) throws Exception {
051        super(properties);
052        iAllowUnassignments = properties.getPropertyBoolean("Suggestion.AllowUnassignments", iAllowUnassignments);
053    }
054    
055    @Override
056    public Neighbour<Lecture, Placement> selectNeighbour(Solution<Lecture, Placement> solution) {
057        Collection<Lecture> unassigned = solution.getModel().unassignedVariables(solution.getAssignment());
058        if (!unassigned.isEmpty()) {
059            Lecture lecture = ToolBox.random(unassigned);
060            int depth = Math.max(2, ToolBox.random(iSuggestionDepth));
061            Neighbour<Lecture, Placement> neigbour = selectNeighbourWithSuggestions(solution, lecture, depth);
062            if (neigbour != null)
063                return new SuggestionNeighbour(neigbour);
064            Placement placement = ToolBox.random(lecture.values(solution.getAssignment()));
065            if (placement != null) {
066                Set<Placement> conflicts = new HashSet<Placement>();
067                if (iStat != null)
068                    for (Map.Entry<Constraint<Lecture, Placement>, Set<Placement>> entry: solution.getModel().conflictConstraints(solution.getAssignment(), placement).entrySet()) {
069                        iStat.constraintAfterAssigned(solution.getAssignment(), solution.getIteration(), entry.getKey(), placement, entry.getValue());
070                        conflicts.addAll(entry.getValue());
071                    }
072                else
073                    conflicts = solution.getModel().conflictValues(solution.getAssignment(), placement);
074                if (!conflicts.contains(placement) && (iAllowUnassignments || conflicts.size() <= 1))
075                    return new SimpleNeighbour<Lecture, Placement>(lecture, placement, conflicts);
076            }
077        }
078        return null;
079    }
080    
081    /** Simple @{link Neighbour} wrapper always returning -1 as the value */
082    static class SuggestionNeighbour implements Neighbour<Lecture, Placement> {
083        Neighbour<Lecture, Placement> iNeigbour;
084        
085        SuggestionNeighbour(Neighbour<Lecture, Placement> neigbour) {
086            iNeigbour = neigbour;
087        }
088
089        @Override
090        public void assign(Assignment<Lecture, Placement> assignment, long iteration) {
091            iNeigbour.assign(assignment, iteration);
092        }
093
094        @Override
095        public double value(Assignment<Lecture, Placement> assignment) {
096            return -1;
097        }
098
099        @Override
100        public Map<Lecture, Placement> assignments() {
101            return iNeigbour.assignments();
102        }
103    }
104}