    001package net.sf.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;
    010
    011import net.sf.cpsolver.coursett.model.Lecture;
    012import net.sf.cpsolver.coursett.model.Placement;
    013import net.sf.cpsolver.coursett.model.TimetableModel;
    014import net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection;
    015import net.sf.cpsolver.ifs.model.Neighbour;
    016import net.sf.cpsolver.ifs.solution.Solution;
    017import net.sf.cpsolver.ifs.solver.Solver;
    018import net.sf.cpsolver.ifs.util.DataProperties;
    019import net.sf.cpsolver.ifs.util.JProf;
    020import net.sf.cpsolver.ifs.util.ToolBox;
    021
    022/**
    023 * Neighbour selection which does the standard time neighbour selection most of
    024 * the time, however, the very best neighbour is selected time to time (using
    025 * backtracking based search).
    026 *
    027 * @see StandardNeighbourSelection
    028 * @version CourseTT 1.2 (University Course Timetabling)<br>
    029 *          Copyright (C) 2006 - 2010 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 */
    047
    048public class NeighbourSelectionWithSuggestions extends StandardNeighbourSelection<Lecture, Placement> {
    049    private double iSuggestionProbability = 0.1;
    050    private double iSuggestionProbabilityAllAssigned = 0.5;
    051    private int iSuggestionTimeout = 500;
    052    private int iSuggestionDepth = 4;
    053
    054    private Solution<Lecture, Placement> iSolution = null;
    055    private SuggestionNeighbour iSuggestionNeighbour = null;
    056    private double iValue = 0;
    057    private int iNrAssigned = 0;
    058    private boolean iTimeoutReached = false;
    059
    060    public NeighbourSelectionWithSuggestions(DataProperties properties) throws Exception {
    061        super(properties);
    062        iSuggestionProbability = properties
    063                .getPropertyDouble("Neighbour.SuggestionProbability", iSuggestionProbability);
    064        iSuggestionProbabilityAllAssigned = properties.getPropertyDouble("Neighbour.SuggestionProbabilityAllAssigned",
    065                iSuggestionProbabilityAllAssigned);
    066        iSuggestionTimeout = properties.getPropertyInt("Neighbour.SuggestionTimeout", iSuggestionTimeout);
    067        iSuggestionDepth = properties.getPropertyInt("Neighbour.SuggestionDepth", iSuggestionDepth);
    068    }
    069
    070    public NeighbourSelectionWithSuggestions(Solver<Lecture, Placement> solver) throws Exception {
    071        this(solver.getProperties());
    072        init(solver);
    073    }
    074
    075    @Override
    076    public void init(Solver<Lecture, Placement> solver) {
    077        super.init(solver);
    078    }
    079
    080    @Override
    081    public Neighbour<Lecture, Placement> selectNeighbour(Solution<Lecture, Placement> solution) {
    082        Neighbour<Lecture, Placement> neighbour = null;
    083        if (solution.getModel().unassignedVariables().isEmpty()) {
    084            for (int d = iSuggestionDepth; d > 1; d--) {
    085                if (ToolBox.random() < Math.pow(iSuggestionProbabilityAllAssigned, d - 1)) {
    086                    neighbour = selectNeighbourWithSuggestions(solution, selectVariable(solution), d);
    087                    break;
    088                }
    089            }
    090        } else {
    091            for (int d = iSuggestionDepth; d > 1; d--) {
    092                if (ToolBox.random() < Math.pow(iSuggestionProbability, d - 1)) {
    093                    neighbour = selectNeighbourWithSuggestions(solution, selectVariable(solution), d);
    094                    break;
    095                }
    096            }
    097        }
    098        return (neighbour != null ? neighbour : super.selectNeighbour(solution));
    099    }
    100
    101    public synchronized Neighbour<Lecture, Placement> selectNeighbourWithSuggestions(
    102            Solution<Lecture, Placement> solution, Lecture lecture, int depth) {
    103        if (lecture == null)
    104            return null;
    105
    106        iSolution = solution;
    107        iSuggestionNeighbour = null;
    108        iValue = solution.getModel().getTotalValue();
    109        iNrAssigned = solution.getModel().assignedVariables().size();
    110        iTimeoutReached = false;
    111
    112        synchronized (solution) {
    113            // System.out.println("BEFORE BT ("+lecture.getName()+"): nrAssigned="+iSolution.getModel().assignedVariables().size()+",  value="+iCmp.currentValue(iSolution));
    114
    115            List<Lecture> initialLectures = new ArrayList<Lecture>(1);
    116            initialLectures.add(lecture);
    117            backtrack(JProf.currentTimeMillis(), initialLectures, new HashMap<Lecture, Placement>(),
    118                    new HashMap<Lecture, Placement>(), depth);
    119
    120            // System.out.println("AFTER  BT ("+lecture.getName()+"): nrAssigned="+iSolution.getModel().assignedVariables().size()+",  value="+iCmp.currentValue(iSolution));
    121        }
    122
    123        return iSuggestionNeighbour;
    124    }
    125
    126    private boolean containsCommited(Collection<Placement> values) {
    127        if (((TimetableModel) iSolution.getModel()).hasConstantVariables()) {
    128            for (Placement placement : values) {
    129                Lecture lecture = placement.variable();
    130                if (lecture.isCommitted())
    131                    return true;
    132            }
    133        }
    134        return false;
    135    }
    136
    137    private void backtrack(long startTime, List<Lecture> initialLectures, Map<Lecture, Placement> resolvedLectures,
    138            HashMap<Lecture, Placement> conflictsToResolve, int depth) {
    139        int nrUnassigned = conflictsToResolve.size();
    140        if ((initialLectures == null || initialLectures.isEmpty()) && nrUnassigned == 0) {
    141            if (iSolution.getModel().assignedVariables().size() > iNrAssigned
    142                    || (iSolution.getModel().assignedVariables().size() == iNrAssigned && iValue > iSolution.getModel().getTotalValue())) {
    143                if (iSuggestionNeighbour == null || iSuggestionNeighbour.compareTo(iSolution) >= 0)
    144                    iSuggestionNeighbour = new SuggestionNeighbour(resolvedLectures);
    145            }
    146            return;
    147        }
    148        if (depth <= 0)
    149            return;
    150        if (iTimeoutReached || iSuggestionTimeout > 0 && JProf.currentTimeMillis() - startTime > iSuggestionTimeout) {
    151            iTimeoutReached = true;
    152            return;
    153        }
    154
    155        for (Lecture lecture: initialLectures != null && !initialLectures.isEmpty() ? initialLectures : new ArrayList<Lecture>(conflictsToResolve.keySet())) {
    156            if (iTimeoutReached) break;
    157            if (resolvedLectures.containsKey(lecture))
    158                continue;
    159            placements: for (Placement placement : lecture.values()) {
    160                if (iTimeoutReached) break;
    161                if (placement.equals(lecture.getAssignment()))
    162                    continue;
    163                if (placement.isHard())
    164                    continue;
    165                Set<Placement> conflicts = iSolution.getModel().conflictValues(placement);
    166                if (nrUnassigned + conflicts.size() > depth)
    167                    continue;
    168                if (conflicts.contains(placement))
    169                    continue;
    170                if (containsCommited(conflicts))
    171                    continue;
    172                for (Iterator<Placement> i = conflicts.iterator();i.hasNext();) {
    173                    Placement c = i.next();
    174                    if (resolvedLectures.containsKey(c.variable()))
    175                        continue placements;
    176                }
    177                Placement cur = lecture.getAssignment();
    178                for (Iterator<Placement> i = conflicts.iterator(); i.hasNext();) {
    179                    Placement c = i.next();
    180                    c.variable().unassign(0);
    181                }
    182                if (cur != null)
    183                    lecture.unassign(0);
    184                lecture.assign(0, placement);
    185                for (Iterator<Placement> i = conflicts.iterator(); i.hasNext();) {
    186                    Placement c = i.next();
    187                    conflictsToResolve.put(c.variable(), c);
    188                }
    189                Placement resolvedConf = conflictsToResolve.remove(lecture);
    190                resolvedLectures.put(lecture, placement);
    191                backtrack(startTime, null, resolvedLectures, conflictsToResolve, depth - 1);
    192                resolvedLectures.remove(lecture);
    193                if (cur == null)
    194                    lecture.unassign(0);
    195                else
    196                    lecture.assign(0, cur);
    197                for (Iterator<Placement> i = conflicts.iterator(); i.hasNext();) {
    198                    Placement p = i.next();
    199                    p.variable().assign(0, p);
    200                    conflictsToResolve.remove(p.variable());
    201                }
    202                if (resolvedConf != null)
    203                    conflictsToResolve.put(lecture, resolvedConf);
    204            }
    205        }
    206    }
    207
    208    public class SuggestionNeighbour extends Neighbour<Lecture, Placement> {
    209        private double iValue = 0;
    210        private List<Placement> iDifferentAssignments = null;
    211
    212        public SuggestionNeighbour(Map<Lecture, Placement> resolvedLectures) {
    213            iValue = iSolution.getModel().getTotalValue();
    214            iDifferentAssignments = new ArrayList<Placement>(resolvedLectures.values());
    215        }
    216
    217        @Override
    218        public double value() {
    219            return iValue;
    220        }
    221
    222        @Override
    223        public void assign(long iteration) {
    224            // System.out.println("START ASSIGN: nrAssigned="+iSolution.getModel().assignedVariables().size()+",  value="+iCmp.currentValue(iSolution));
    225            // System.out.println("  "+this);
    226            for (Placement p : iDifferentAssignments) {
    227                if (p.variable().getAssignment() != null)
    228                    p.variable().unassign(iteration);
    229            }
    230            for (Placement p : iDifferentAssignments) {
    231                p.variable().assign(iteration, p);
    232            }
    233            // System.out.println("END ASSIGN: nrAssigned="+iSolution.getModel().assignedVariables().size()+",  value="+iCmp.currentValue(iSolution));
    234        }
    235
    236        public int compareTo(Solution<Lecture, Placement> solution) {
    237            return Double.compare(iValue, iSolution.getModel().getTotalValue());
    238        }
    239
    240        @Override
    241        public String toString() {
    242            StringBuffer sb = new StringBuffer("Suggestion{value=" + (iValue - iSolution.getModel().getTotalValue()) + ": ");
    243            for (Iterator<Placement> e = iDifferentAssignments.iterator(); e.hasNext();) {
    244                Placement p = e.next();
    245                sb.append("\n    " + p.variable().getName() + " " + p.getName() + (e.hasNext() ? "," : ""));
    246            }
    247            sb.append("}");
    248            return sb.toString();
    249        }
    250    }
    251}