    001package org.cpsolver.coursett.heuristics;
    002
    003import java.util.ArrayList;
    004import java.util.Enumeration;
    005import java.util.Iterator;
    006
    007import org.cpsolver.coursett.model.Lecture;
    008import org.cpsolver.coursett.model.Placement;
    009import org.cpsolver.ifs.assignment.Assignment;
    010import org.cpsolver.ifs.assignment.context.AssignmentContext;
    011import org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext;
    012import org.cpsolver.ifs.heuristics.NeighbourSelection;
    013import org.cpsolver.ifs.model.Neighbour;
    014import org.cpsolver.ifs.model.SimpleNeighbour;
    015import org.cpsolver.ifs.solution.Solution;
    016import org.cpsolver.ifs.solver.Solver;
    017import org.cpsolver.ifs.util.DataProperties;
    018import org.cpsolver.ifs.util.Progress;
    019
    020
    021/**
    022 * University course timetabling neighbour selection. <br>
    023 * <br>
    024 * When a complete solution is found, it is improved by limited depth
    025 * backtracking search. This way it is ensured that the fund solution is at
    026 * least locally optimal.
    027 *
    028 * @author  Tomáš Müller
    029 * @version CourseTT 1.3 (University Course Timetabling)<br>
    030 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    031 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    032 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    033 * <br>
    034 *          This library is free software; you can redistribute it and/or modify
    035 *          it under the terms of the GNU Lesser General Public License as
    036 *          published by the Free Software Foundation; either version 3 of the
    037 *          License, or (at your option) any later version. <br>
    038 * <br>
    039 *          This library is distributed in the hope that it will be useful, but
    040 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    041 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    042 *          Lesser General Public License for more details. <br>
    043 * <br>
    044 *          You should have received a copy of the GNU Lesser General Public
    045 *          License along with this library; if not see
    046 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    047 */
    048public class FixCompleteSolutionNeighbourSelection extends NeighbourSelectionWithContext<Lecture, Placement, FixCompleteSolutionNeighbourSelection.FixCompleteSolutionNeighbourContext> {
    049    private NeighbourSelection<Lecture, Placement> iParent = null;
    050    private long iLastCompleteSolutionFixIteration = -1;
    051    private long iLastIncompleteSolutionFixIteration = -1;
    052    private long iCompleteSolutionFixInterval = 1;
    053    private long iIncompleteSolutionFixInterval = 5000;
    054    private NeighbourSelectionWithSuggestions iSuggestions = null;
    055    private Progress iProgress = null;
    056    private Solver<Lecture, Placement> iSolver = null;
    057
    058    public FixCompleteSolutionNeighbourSelection(DataProperties config, NeighbourSelection<Lecture, Placement> parent) throws Exception {
    059        iParent = parent;
    060        iSuggestions = new NeighbourSelectionWithSuggestions(config);
    061    }
    062
    063    public FixCompleteSolutionNeighbourSelection(DataProperties config) throws Exception {
    064        this(config, new NeighbourSelectionWithSuggestions(config));
    065    }
    066
    067    @Override
    068    public void init(Solver<Lecture, Placement> solver) {
    069        super.init(solver);
    070        iCompleteSolutionFixInterval = solver.getProperties().getPropertyLong("General.CompleteSolutionFixInterval", iCompleteSolutionFixInterval);
    071        iIncompleteSolutionFixInterval = solver.getProperties().getPropertyLong("General.IncompleteSolutionFixInterval", iIncompleteSolutionFixInterval);
    072        iSuggestions.init(solver);
    073        iParent.init(solver);
    074        iProgress = Progress.getInstance(solver.currentSolution().getModel());
    075        iLastIncompleteSolutionFixIteration = -1;
    076        iLastCompleteSolutionFixIteration = -1;
    077        iSolver = solver;
    078    }
    079
    080    /**
    081     * Try to improve existing solution by backtracking search of very limited
    082     * depth. See {@link NeighbourSelectionWithSuggestions} for more details.
    083     */
    084    @Override
    085    public Neighbour<Lecture, Placement> selectNeighbour(Solution<Lecture, Placement> solution) {
    086        FixCompleteSolutionNeighbourContext context = getContext(solution.getAssignment());
    087        if (context.getPhase() == 0) {
    088            if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) == 0) {
    089                // complete solution was found
    090                if (iCompleteSolutionFixInterval < 0) {
    091                    // feature disabled
    092                    return iParent.selectNeighbour(solution);
    093                } else if (iCompleteSolutionFixInterval == 0) {
    094                    // only run first time a complete solution is found
    095                    if (iLastCompleteSolutionFixIteration >= 0) return iParent.selectNeighbour(solution);
    096                } else {
    097                    // run first time and if not run for a given number of iterations
    098                    if (iLastCompleteSolutionFixIteration >= 0 && solution.getIteration() - iLastCompleteSolutionFixIteration < iCompleteSolutionFixInterval)
    099                        return iParent.selectNeighbour(solution);
    100                }
    101                if (solution.getBestIteration() == solution.getIteration())
    102                    context.incPhase(solution);
    103            } else if (!solution.isBestComplete()) {
    104                // complete solution has not been found yet
    105                if (iIncompleteSolutionFixInterval < 0) {
    106                    // feature disabled
    107                    return iParent.selectNeighbour(solution);
    108                } else if (iIncompleteSolutionFixInterval == 0) {
    109                    // only run first time a complete solution is found
    110                    if (iLastIncompleteSolutionFixIteration >= 0)
    111                        return iParent.selectNeighbour(solution);
    112                } else {
    113                    // run first time and if not run for a given number of iterations
    114                    if (solution.getIteration() - iLastIncompleteSolutionFixIteration < iIncompleteSolutionFixInterval)
    115                        return iParent.selectNeighbour(solution);
    116                }
    117                if (solution.getBestIteration() == solution.getIteration())
    118                    context.incPhase(solution);
    119            }
    120        }
    121
    122        while (context.getPhase() > 0 && !iSolver.isStop()) {
    123            if (context.hasMoreElements()) {
    124                Lecture variable = context.nextElement();
    125                // iProgress.incProgress();
    126                if (context.getPhase() == 1) {
    127                    Placement bestValue = null;
    128                    double bestVal = 0.0;
    129                    Placement currentValue = solution.getAssignment().getValue(variable);
    130                    if (currentValue == null)
    131                        continue;
    132                    double currentVal = currentValue.toDouble(solution.getAssignment());
    133                    for (Placement value : variable.values(solution.getAssignment())) {
    134                        if (value.equals(currentValue))
    135                            continue;
    136                        if (solution.getModel().conflictValues(solution.getAssignment(), value).isEmpty()) {
    137                            double val = value.toDouble(solution.getAssignment());
    138                            if (bestValue == null || val < bestVal) {
    139                                bestValue = value;
    140                                bestVal = val;
    141                            }
    142                        }
    143                    }
    144                    if (bestValue != null && bestVal < currentVal)
    145                        return new SimpleNeighbour<Lecture, Placement>(variable, bestValue);
    146                } else {
    147                    Neighbour<Lecture, Placement> n = iSuggestions.selectNeighbourWithSuggestions(solution, variable, 2);
    148                    if (n != null && n.value(solution.getAssignment()) <= solution.getModel().getTotalValue(solution.getAssignment()))
    149                        return n;
    150                }
    151            } else {
    152                context.incPhase(solution);
    153            }
    154        }
    155        return iParent.selectNeighbour(solution);
    156    }
    157
    158    @Override
    159    public FixCompleteSolutionNeighbourContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
    160        return new FixCompleteSolutionNeighbourContext(assignment);
    161    }
    162
    163    public class FixCompleteSolutionNeighbourContext implements AssignmentContext, Enumeration<Lecture> {
    164        private int iPhase = 0;
    165        private Iterator<Lecture> iLectures = null;
    166
    167        public FixCompleteSolutionNeighbourContext(Assignment<Lecture, Placement> assignment) {}
    168
    169        public int getPhase() { return iPhase; }
    170
    171        public void incPhase(Solution<Lecture, Placement> solution) {
    172            // Progress progress = Progress.getInstance(solution.getModel());
    173            if (iPhase == 0) {
    174                // iSolver.setUpdateProgress(false);
    175                iPhase = 1;
    176                solution.saveBest();
    177                // progress.setPhase("Fixing solution", solution.getModel().countVariables());
    178                iProgress.info("[" + Thread.currentThread().getName() + "] Fixing solution...");
    179                iLectures = new ArrayList<Lecture>(solution.getModel().variables()).iterator();
    180            } else if (iPhase == 1 && solution.isComplete()) {
    181                iPhase = 2;
    182                iProgress.info("[" + Thread.currentThread().getName() + "] Fixing complete solution...");
    183                // progress.setPhase("Fixing solution [2]", solution.getModel().countVariables());
    184                iLectures = new ArrayList<Lecture>(solution.getModel().variables()).iterator();
    185            } else {
    186                if (iPhase == 1)
    187                    iLastIncompleteSolutionFixIteration = solution.getIteration();
    188                else
    189                    iLastCompleteSolutionFixIteration = solution.getIteration();
    190                // iSolver.setUpdateProgress(true);
    191                // if (solution.isBestComplete())
    192                //     iProgress.setPhase("Improving found solution ...");
    193                // else
    194                //     iProgress.setPhase("Searching for initial solution ...", solution.getModel().countVariables());
    195                iPhase = 0;
    196                // progress.restore();
    197                iLectures = null;
    198            }
    199        }
    200
    201        @Override
    202        public boolean hasMoreElements() {
    203            return iLectures != null && iLectures.hasNext();
    204        }
    205
    206        @Override
    207        public Lecture nextElement() {
    208            return iLectures.next();
    209        }
    210
    211    }
    212}