    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}