    001package org.cpsolver.coursett.heuristics;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.HashMap;
    006import java.util.Iterator;
    007import java.util.List;
    008import java.util.Map;
    009import java.util.Set;
    010import java.util.concurrent.locks.Lock;
    011
    012import org.cpsolver.coursett.model.Lecture;
    013import org.cpsolver.coursett.model.Placement;
    014import org.cpsolver.coursett.model.TimetableModel;
    015import org.cpsolver.ifs.assignment.Assignment;
    016import org.cpsolver.ifs.heuristics.StandardNeighbourSelection;
    017import org.cpsolver.ifs.model.Neighbour;
    018import org.cpsolver.ifs.solution.Solution;
    019import org.cpsolver.ifs.solver.Solver;
    020import org.cpsolver.ifs.util.DataProperties;
    021import org.cpsolver.ifs.util.JProf;
    022import org.cpsolver.ifs.util.ToolBox;
    023
    024
    025/**
    026 * Neighbour selection which does the standard time neighbour selection most of
    027 * the time, however, the very best neighbour is selected time to time (using
    028 * backtracking based search).
    029 *
    030 * @see StandardNeighbourSelection
    031 * @version CourseTT 1.3 (University Course Timetabling)<br>
    032 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    033 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    034 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    035 * <br>
    036 *          This library is free software; you can redistribute it and/or modify
    037 *          it under the terms of the GNU Lesser General Public License as
    038 *          published by the Free Software Foundation; either version 3 of the
    039 *          License, or (at your option) any later version. <br>
    040 * <br>
    041 *          This library is distributed in the hope that it will be useful, but
    042 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    043 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    044 *          Lesser General Public License for more details. <br>
    045 * <br>
    046 *          You should have received a copy of the GNU Lesser General Public
    047 *          License along with this library; if not see
    048 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    049 */
    050
    051public class NeighbourSelectionWithSuggestions extends StandardNeighbourSelection<Lecture, Placement> {
    052    private double iSuggestionProbability = 0.1;
    053    private double iSuggestionProbabilityAllAssigned = 0.5;
    054    private int iSuggestionTimeout = 500;
    055    private int iSuggestionDepth = 4;
    056
    057    public NeighbourSelectionWithSuggestions(DataProperties properties) throws Exception {
    058        super(properties);
    059        iSuggestionProbability = properties.getPropertyDouble("Neighbour.SuggestionProbability", iSuggestionProbability);
    060        iSuggestionProbabilityAllAssigned = properties.getPropertyDouble("Neighbour.SuggestionProbabilityAllAssigned", iSuggestionProbabilityAllAssigned);
    061        iSuggestionTimeout = properties.getPropertyInt("Neighbour.SuggestionTimeout", iSuggestionTimeout);
    062        iSuggestionDepth = properties.getPropertyInt("Neighbour.SuggestionDepth", iSuggestionDepth);
    063    }
    064
    065    public NeighbourSelectionWithSuggestions(Solver<Lecture, Placement> solver) throws Exception {
    066        this(solver.getProperties());
    067        init(solver);
    068    }
    069
    070    @Override
    071    public void init(Solver<Lecture, Placement> solver) {
    072        super.init(solver);
    073    }
    074
    075    @Override
    076    public Neighbour<Lecture, Placement> selectNeighbour(Solution<Lecture, Placement> solution) {
    077        Neighbour<Lecture, Placement> neighbour = null;
    078        if (solution.getModel().unassignedVariables(solution.getAssignment()).isEmpty()) {
    079            for (int d = iSuggestionDepth; d > 1; d--) {
    080                if (ToolBox.random() < Math.pow(iSuggestionProbabilityAllAssigned, d - 1)) {
    081                    neighbour = selectNeighbourWithSuggestions(solution, selectVariable(solution), d);
    082                    break;
    083                }
    084            }
    085        } else {
    086            for (int d = iSuggestionDepth; d > 1; d--) {
    087                if (ToolBox.random() < Math.pow(iSuggestionProbability, d - 1)) {
    088                    neighbour = selectNeighbourWithSuggestions(solution, selectVariable(solution), d);
    089                    break;
    090                }
    091            }
    092        }
    093        return (neighbour != null ? neighbour : super.selectNeighbour(solution));
    094    }
    095
    096    public Neighbour<Lecture, Placement> selectNeighbourWithSuggestions(Solution<Lecture, Placement> solution, Lecture lecture, int depth) {
    097        if (lecture == null)
    098            return null;
    099
    100        NeighbourSelectionWithSuggestionsContext context = new NeighbourSelectionWithSuggestionsContext(solution);
    101
    102        Lock lock = solution.getLock().writeLock();
    103        lock.lock();
    104        try {
    105            // System.out.println("BEFORE BT ("+lecture.getName()+"): nrAssigned="+iSolution.getModel().assignedVariables().size()+",  value="+iCmp.currentValue(iSolution));
    106
    107            List<Lecture> initialLectures = new ArrayList<Lecture>(1);
    108            initialLectures.add(lecture);
    109            backtrack(context, initialLectures, new HashMap<Lecture, Placement>(), new HashMap<Lecture, Placement>(), depth);
    110
    111            // System.out.println("AFTER  BT ("+lecture.getName()+"): nrAssigned="+iSolution.getModel().assignedVariables().size()+",  value="+iCmp.currentValue(iSolution));
    112        } finally {
    113            lock.unlock();
    114        }
    115
    116        return context.getSuggestionNeighbour();
    117    }
    118
    119    private boolean containsCommited(NeighbourSelectionWithSuggestionsContext context, Collection<Placement> values) {
    120        if (context.getModel().hasConstantVariables()) {
    121            for (Placement placement : values) {
    122                Lecture lecture = placement.variable();
    123                if (lecture.isCommitted())
    124                    return true;
    125            }
    126        }
    127        return false;
    128    }
    129
    130    private void backtrack(NeighbourSelectionWithSuggestionsContext context, List<Lecture> initialLectures, Map<Lecture, Placement> resolvedLectures, HashMap<Lecture, Placement> conflictsToResolve, int depth) {
    131        int nrUnassigned = conflictsToResolve.size();
    132        if ((initialLectures == null || initialLectures.isEmpty()) && nrUnassigned == 0) {
    133            context.setSuggestionNeighbourIfImproving(resolvedLectures);
    134            return;
    135        }
    136        if (depth <= 0 || context.checkTimeoutReached())
    137            return;
    138
    139        Assignment<Lecture, Placement> assignment = context.getAssignment();
    140        for (Lecture lecture: initialLectures != null && !initialLectures.isEmpty() ? initialLectures : new ArrayList<Lecture>(conflictsToResolve.keySet())) {
    141            if (context.isTimeoutReached()) break;
    142            if (resolvedLectures.containsKey(lecture))
    143                continue;
    144            placements: for (Placement placement : lecture.values(assignment)) {
    145                if (context.isTimeoutReached()) break;
    146                Placement cur = assignment.getValue(lecture);
    147                if (placement.equals(cur))
    148                    continue;
    149                if (placement.isHard(assignment))
    150                    continue;
    151                Set<Placement> conflicts = context.getModel().conflictValues(assignment, placement);
    152                if (nrUnassigned + conflicts.size() > depth)
    153                    continue;
    154                if (conflicts.contains(placement))
    155                    continue;
    156                if (containsCommited(context, conflicts))
    157                    continue;
    158                for (Iterator<Placement> i = conflicts.iterator();i.hasNext();) {
    159                    Placement c = i.next();
    160                    if (resolvedLectures.containsKey(c.variable()))
    161                        continue placements;
    162                }
    163                for (Iterator<Placement> i = conflicts.iterator(); i.hasNext();) {
    164                    Placement c = i.next();
    165                    assignment.unassign(0, c.variable());
    166                }
    167                assignment.assign(0, placement);
    168                for (Iterator<Placement> i = conflicts.iterator(); i.hasNext();) {
    169                    Placement c = i.next();
    170                    conflictsToResolve.put(c.variable(), c);
    171                }
    172                Placement resolvedConf = conflictsToResolve.remove(lecture);
    173                resolvedLectures.put(lecture, placement);
    174                backtrack(context, null, resolvedLectures, conflictsToResolve, depth - 1);
    175                resolvedLectures.remove(lecture);
    176                if (cur == null)
    177                    assignment.unassign(0, lecture);
    178                else
    179                    assignment.assign(0, cur);
    180                for (Iterator<Placement> i = conflicts.iterator(); i.hasNext();) {
    181                    Placement p = i.next();
    182                    assignment.assign(0, p);
    183                    conflictsToResolve.remove(p.variable());
    184                }
    185                if (resolvedConf != null)
    186                    conflictsToResolve.put(lecture, resolvedConf);
    187            }
    188        }
    189    }
    190
    191    public class SuggestionNeighbour implements Neighbour<Lecture, Placement> {
    192        private double iValue = 0;
    193        private List<Placement> iDifferentAssignments = null;
    194
    195        public SuggestionNeighbour(Map<Lecture, Placement> resolvedLectures, double value) {
    196            iValue = value;
    197            iDifferentAssignments = new ArrayList<Placement>(resolvedLectures.values());
    198        }
    199
    200        @Override
    201        public double value(Assignment<Lecture, Placement> assignment) {
    202            return iValue;
    203        }
    204
    205        @Override
    206        public void assign(Assignment<Lecture, Placement> assignment, long iteration) {
    207            // System.out.println("START ASSIGN: nrAssigned="+iSolution.getModel().assignedVariables().size()+",  value="+iCmp.currentValue(iSolution));
    208            // System.out.println("  "+this);
    209            for (Placement p : iDifferentAssignments)
    210                assignment.unassign(iteration, p.variable());
    211            for (Placement p : iDifferentAssignments)
    212                assignment.assign(iteration, p);
    213            // System.out.println("END ASSIGN: nrAssigned="+iSolution.getModel().assignedVariables().size()+",  value="+iCmp.currentValue(iSolution));
    214        }
    215
    216        public int compareTo(Solution<Lecture, Placement> solution) {
    217            return Double.compare(iValue, solution.getModel().getTotalValue(solution.getAssignment()));
    218        }
    219
    220        @Override
    221        public String toString() {
    222            StringBuffer sb = new StringBuffer("Suggestion{value=" + iValue + ": ");
    223            for (Iterator<Placement> e = iDifferentAssignments.iterator(); e.hasNext();) {
    224                Placement p = e.next();
    225                sb.append("\n    " + p.variable().getName() + " " + p.getName() + (e.hasNext() ? "," : ""));
    226            }
    227            sb.append("}");
    228            return sb.toString();
    229        }
    230
    231        @Override
    232        public Map<Lecture, Placement> assignments() {
    233            Map<Lecture, Placement> ret = new HashMap<Lecture, Placement>();
    234            for (Placement p : iDifferentAssignments)
    235                ret.put(p.variable(), p);
    236            return ret;
    237        }
    238    }
    239
    240    public class NeighbourSelectionWithSuggestionsContext {
    241        private Solution<Lecture, Placement> iSolution = null;
    242        private SuggestionNeighbour iSuggestionNeighbour = null;
    243        private double iValue = 0;
    244        private int iNrAssigned = 0;
    245        private boolean iTimeoutReached = false;
    246        private long iStartTime;
    247
    248        public NeighbourSelectionWithSuggestionsContext(Solution<Lecture, Placement> solution) {
    249            iSolution = solution;
    250            iSuggestionNeighbour = null;
    251            iValue = solution.getModel().getTotalValue(solution.getAssignment());
    252            iNrAssigned = solution.getAssignment().nrAssignedVariables();
    253            iTimeoutReached = false;
    254            iStartTime = JProf.currentTimeMillis();
    255        }
    256
    257        public SuggestionNeighbour getSuggestionNeighbour() { return iSuggestionNeighbour; }
    258
    259        public boolean setSuggestionNeighbourIfImproving(Map<Lecture, Placement> assignment) {
    260            if (getAssignment().nrAssignedVariables() > getNrAssigned() || (getAssignment().nrAssignedVariables() == getNrAssigned() && getValue() > getModel().getTotalValue(getAssignment()))) {
    261                double value = getModel().getTotalValue(getAssignment());
    262                if (getSuggestionNeighbour() == null || getSuggestionNeighbour().value(getAssignment()) >= value) {
    263                    iSuggestionNeighbour = new SuggestionNeighbour(assignment, value);
    264                    return true;
    265                }
    266            }
    267            return false;
    268        }
    269
    270        public Solution<Lecture, Placement> getSolution() { return iSolution; }
    271        public Assignment<Lecture, Placement> getAssignment() { return getSolution().getAssignment(); }
    272        public TimetableModel getModel() { return (TimetableModel)getSolution().getModel(); }
    273        public int getNrAssigned() { return iNrAssigned; }
    274        public double getValue() { return iValue; }
    275
    276        public boolean isTimeoutReached() { return iTimeoutReached; }
    277        public boolean checkTimeoutReached() {
    278            if (iTimeoutReached) return true;
    279            if (iSuggestionTimeout > 0 && JProf.currentTimeMillis() - iStartTime > iSuggestionTimeout)
    280                iTimeoutReached = true;
    281            return iTimeoutReached;
    282        }
    283        public void setTimeoutReached(boolean timeoutReached) { iTimeoutReached = timeoutReached; }
    284    }
    285}