    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 * @version CourseTT 1.3 (University Course Timetabling)<br>
    029 *          Copyright (C) 2006 - 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 FixCompleteSolutionNeighbourSelection extends NeighbourSelectionWithContext<Lecture, Placement, FixCompleteSolutionNeighbourSelection.FixCompleteSolutionNeighbourContext> {
    048    private NeighbourSelection<Lecture, Placement> iParent = null;
    049    private long iLastCompleteSolutionFixIteration = -1;
    050    private long iLastIncompleteSolutionFixIteration = -1;
    051    private long iCompleteSolutionFixInterval = 1;
    052    private long iIncompleteSolutionFixInterval = 5000;
    053    private NeighbourSelectionWithSuggestions iSuggestions = null;
    054    private Progress iProgress = null;
    055    private Solver<Lecture, Placement> iSolver = null;
    056
    057    public FixCompleteSolutionNeighbourSelection(DataProperties config, NeighbourSelection<Lecture, Placement> parent) throws Exception {
    058        iParent = parent;
    059        iSuggestions = new NeighbourSelectionWithSuggestions(config);
    060    }
    061
    062    public FixCompleteSolutionNeighbourSelection(DataProperties config) throws Exception {
    063        this(config, new NeighbourSelectionWithSuggestions(config));
    064    }
    065
    066    @Override
    067    public void init(Solver<Lecture, Placement> solver) {
    068        super.init(solver);
    069        iCompleteSolutionFixInterval = solver.getProperties().getPropertyLong("General.CompleteSolutionFixInterval", iCompleteSolutionFixInterval);
    070        iIncompleteSolutionFixInterval = solver.getProperties().getPropertyLong("General.IncompleteSolutionFixInterval", iIncompleteSolutionFixInterval);
    071        iSuggestions.init(solver);
    072        iParent.init(solver);
    073        iProgress = Progress.getInstance(solver.currentSolution().getModel());
    074        iLastIncompleteSolutionFixIteration = -1;
    075        iLastCompleteSolutionFixIteration = -1;
    076        iSolver = solver;
    077    }
    078
    079    /**
    080     * Try to improve existing solution by backtracking search of very limited
    081     * depth. See {@link NeighbourSelectionWithSuggestions} for more details.
    082     */
    083    @Override
    084    public Neighbour<Lecture, Placement> selectNeighbour(Solution<Lecture, Placement> solution) {
    085        FixCompleteSolutionNeighbourContext context = getContext(solution.getAssignment());
    086        if (context.getPhase() == 0) {
    087            if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) == 0) {
    088                // complete solution was found
    089                if (iCompleteSolutionFixInterval < 0) {
    090                    // feature disabled
    091                    return iParent.selectNeighbour(solution);
    092                } else if (iCompleteSolutionFixInterval == 0) {
    093                    // only run first time a complete solution is found
    094                    if (iLastCompleteSolutionFixIteration >= 0) return iParent.selectNeighbour(solution);
    095                } else {
    096                    // run first time and if not run for a given number of iterations
    097                    if (iLastCompleteSolutionFixIteration >= 0 && solution.getIteration() - iLastCompleteSolutionFixIteration < iCompleteSolutionFixInterval)
    098                        return iParent.selectNeighbour(solution);
    099                }
    100                if (solution.getBestIteration() == solution.getIteration())
    101                    context.incPhase(solution);
    102            } else if (!solution.isBestComplete()) {
    103                // complete solution has not been found yet
    104                if (iIncompleteSolutionFixInterval < 0) {
    105                    // feature disabled
    106                    return iParent.selectNeighbour(solution);
    107                } else if (iIncompleteSolutionFixInterval == 0) {
    108                    // only run first time a complete solution is found
    109                    if (iLastIncompleteSolutionFixIteration >= 0)
    110                        return iParent.selectNeighbour(solution);
    111                } else {
    112                    // run first time and if not run for a given number of iterations
    113                    if (solution.getIteration() - iLastIncompleteSolutionFixIteration < iIncompleteSolutionFixInterval)
    114                        return iParent.selectNeighbour(solution);
    115                }
    116                if (solution.getBestIteration() == solution.getIteration())
    117                    context.incPhase(solution);
    118            }
    119        }
    120
    121        while (context.getPhase() > 0 && !iSolver.isStop()) {
    122            if (context.hasMoreElements()) {
    123                Lecture variable = context.nextElement();
    124                // iProgress.incProgress();
    125                if (context.getPhase() == 1) {
    126                    Placement bestValue = null;
    127                    double bestVal = 0.0;
    128                    Placement currentValue = solution.getAssignment().getValue(variable);
    129                    if (currentValue == null)
    130                        continue;
    131                    double currentVal = currentValue.toDouble(solution.getAssignment());
    132                    for (Placement value : variable.values(solution.getAssignment())) {
    133                        if (value.equals(currentValue))
    134                            continue;
    135                        if (solution.getModel().conflictValues(solution.getAssignment(), value).isEmpty()) {
    136                            double val = value.toDouble(solution.getAssignment());
    137                            if (bestValue == null || val < bestVal) {
    138                                bestValue = value;
    139                                bestVal = val;
    140                            }
    141                        }
    142                    }
    143                    if (bestValue != null && bestVal < currentVal)
    144                        return new SimpleNeighbour<Lecture, Placement>(variable, bestValue);
    145                } else {
    146                    Neighbour<Lecture, Placement> n = iSuggestions.selectNeighbourWithSuggestions(solution, variable, 2);
    147                    if (n != null && n.value(solution.getAssignment()) <= solution.getModel().getTotalValue(solution.getAssignment()))
    148                        return n;
    149                }
    150            } else {
    151                context.incPhase(solution);
    152            }
    153        }
    154        return iParent.selectNeighbour(solution);
    155    }
    156
    157    @Override
    158    public FixCompleteSolutionNeighbourContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
    159        return new FixCompleteSolutionNeighbourContext(assignment);
    160    }
    161
    162    public class FixCompleteSolutionNeighbourContext implements AssignmentContext, Enumeration<Lecture> {
    163        private int iPhase = 0;
    164        private Iterator<Lecture> iLectures = null;
    165
    166        public FixCompleteSolutionNeighbourContext(Assignment<Lecture, Placement> assignment) {}
    167
    168        public int getPhase() { return iPhase; }
    169
    170        public void incPhase(Solution<Lecture, Placement> solution) {
    171            // Progress progress = Progress.getInstance(solution.getModel());
    172            if (iPhase == 0) {
    173                // iSolver.setUpdateProgress(false);
    174                iPhase = 1;
    175                solution.saveBest();
    176                // progress.setPhase("Fixing solution", solution.getModel().countVariables());
    177                iProgress.info("[" + Thread.currentThread().getName() + "] Fixing solution...");
    178                iLectures = new ArrayList<Lecture>(solution.getModel().variables()).iterator();
    179            } else if (iPhase == 1 && solution.isComplete()) {
    180                iPhase = 2;
    181                iProgress.info("[" + Thread.currentThread().getName() + "] Fixing complete solution...");
    182                // progress.setPhase("Fixing solution [2]", solution.getModel().countVariables());
    183                iLectures = new ArrayList<Lecture>(solution.getModel().variables()).iterator();
    184            } else {
    185                if (iPhase == 1)
    186                    iLastIncompleteSolutionFixIteration = solution.getIteration();
    187                else
    188                    iLastCompleteSolutionFixIteration = solution.getIteration();
    189                // iSolver.setUpdateProgress(true);
    190                // if (solution.isBestComplete())
    191                //     iProgress.setPhase("Improving found solution ...");
    192                // else
    193                //     iProgress.setPhase("Searching for initial solution ...", solution.getModel().countVariables());
    194                iPhase = 0;
    195                // progress.restore();
    196                iLectures = null;
    197            }
    198        }
    199
    200        @Override
    201        public boolean hasMoreElements() {
    202            return iLectures != null && iLectures.hasNext();
    203        }
    204
    205        @Override
    206        public Lecture nextElement() {
    207            return iLectures.next();
    208        }
    209
    210    }
    211}