    001package net.sf.cpsolver.coursett;
    002
    003import net.sf.cpsolver.coursett.heuristics.NeighbourSelectionWithSuggestions;
    004import net.sf.cpsolver.coursett.model.Lecture;
    005import net.sf.cpsolver.coursett.model.Placement;
    006import net.sf.cpsolver.coursett.model.TimetableModel;
    007import net.sf.cpsolver.ifs.model.Neighbour;
    008import net.sf.cpsolver.ifs.solver.Solver;
    009import net.sf.cpsolver.ifs.util.DataProperties;
    010import net.sf.cpsolver.ifs.util.JProf;
    011import net.sf.cpsolver.ifs.util.Progress;
    012
    013/**
    014 * University course timetabling solver. <br>
    015 * <br>
    016 * When a complete solution is found, it is improved by limited depth
    017 * backtracking search. This way it is ensured that the fund solution is at
    018 * least locally optimal.
    019 *
    020 * @version CourseTT 1.2 (University Course Timetabling)<br>
    021 *          Copyright (C) 2006 - 2010 Tomáš Müller<br>
    022 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    023 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    024 * <br>
    025 *          This library is free software; you can redistribute it and/or modify
    026 *          it under the terms of the GNU Lesser General Public License as
    027 *          published by the Free Software Foundation; either version 3 of the
    028 *          License, or (at your option) any later version. <br>
    029 * <br>
    030 *          This library is distributed in the hope that it will be useful, but
    031 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    032 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    033 *          Lesser General Public License for more details. <br>
    034 * <br>
    035 *          You should have received a copy of the GNU Lesser General Public
    036 *          License along with this library; if not see
    037 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    038 */
    039
    040public class TimetableSolver extends Solver<Lecture, Placement> {
    041    private long iLastCompleteSolutionFixIteration = -1;
    042    private long iLastIncompleteSolutionFixIteration = -1;
    043    private long iCompleteSolutionFixInterval = 1;
    044    private long iIncompleteSolutionFixInterval = 5000;
    045
    046    public TimetableSolver(DataProperties properties) {
    047        super(properties);
    048    }
    049
    050    @Override
    051    public void initSolver() {
    052        super.initSolver();
    053        iCompleteSolutionFixInterval = getProperties().getPropertyLong("General.CompleteSolutionFixInterval", iCompleteSolutionFixInterval);
    054        iIncompleteSolutionFixInterval = getProperties().getPropertyLong("General.IncompleteSolutionFixInterval", iIncompleteSolutionFixInterval);
    055    }
    056
    057    @Override
    058    protected void onAssigned(double startTime) {
    059        if (iCurrentSolution.getModel().nrUnassignedVariables() == 0) {
    060            // complete solution was found
    061            if (iCompleteSolutionFixInterval < 0) {
    062             // feature disabled
    063                return;
    064            } else if (iCompleteSolutionFixInterval == 0) {
    065                // only run first time a complete solution is found
    066                if (iLastCompleteSolutionFixIteration >= 0) return;
    067            } else {
    068                // run first time and if not run for a given number of iterations
    069                if (iLastCompleteSolutionFixIteration >= 0 && iCurrentSolution.getIteration() - iLastCompleteSolutionFixIteration < iCompleteSolutionFixInterval) return;
    070            }
    071            if (getSolutionComparator().isBetterThanBestSolution(iCurrentSolution)) {
    072                fixCompleteSolution(startTime);
    073                iLastCompleteSolutionFixIteration = iCurrentSolution.getIteration();
    074            }
    075        } else if (iCurrentSolution.getBestInfo() == null) {
    076            // complete solution has not been found yet
    077            if (iIncompleteSolutionFixInterval < 0) {
    078                // feature disabled
    079                   return;
    080            } else if (iIncompleteSolutionFixInterval == 0) {
    081                // only run first time a complete solution is found
    082                if (iLastIncompleteSolutionFixIteration >= 0) return;
    083            } else {
    084                // run first time and if not run for a given number of iterations
    085                if (iLastIncompleteSolutionFixIteration >= 0 && iCurrentSolution.getIteration() - iLastIncompleteSolutionFixIteration < iIncompleteSolutionFixInterval) return;
    086            }
    087            if (getSolutionComparator().isBetterThanBestSolution(iCurrentSolution)) {
    088                fixCompleteSolution(startTime);
    089                iLastIncompleteSolutionFixIteration = iCurrentSolution.getIteration();
    090            }
    091        }
    092    }
    093
    094    /**
    095     * Try to improve existing solution by backtracking search of very limited
    096     * depth. See {@link NeighbourSelectionWithSuggestions} for more details.
    097     */
    098    protected void fixCompleteSolution(double startTime) {
    099        Progress progress = Progress.getInstance(currentSolution().getModel());
    100
    101        TimetableModel model = (TimetableModel) iCurrentSolution.getModel();
    102        iCurrentSolution.saveBest();
    103        progress.save();
    104        double solutionValue = 0.0, newSolutionValue = model.getTotalValue();
    105        do {
    106            solutionValue = newSolutionValue;
    107            progress.setPhase("Fixing solution", model.variables().size());
    108            for (Lecture variable : model.variables()) {
    109                Placement bestValue = null;
    110                double bestVal = 0.0;
    111                Placement currentValue = variable.getAssignment();
    112                if (currentValue == null)
    113                    continue;
    114                double currentVal = currentValue.toDouble();
    115                for (Placement value : variable.values()) {
    116                    if (value.equals(currentValue))
    117                        continue;
    118                    if (model.conflictValues(value).isEmpty()) {
    119                        double val = value.toDouble();
    120                        if (bestValue == null || val < bestVal) {
    121                            bestValue = value;
    122                            bestVal = val;
    123                        }
    124                    }
    125                }
    126                if (bestValue != null && bestVal < currentVal)
    127                    variable.assign(0, bestValue);
    128                iCurrentSolution.update(JProf.currentTimeSec() - startTime);
    129                progress.incProgress();
    130                if (iStop)
    131                    break;
    132            }
    133            newSolutionValue = model.getTotalValue();
    134            if (newSolutionValue < solutionValue) {
    135                progress.debug("New solution value is  " + newSolutionValue);
    136            }
    137        } while (!iStop && newSolutionValue < solutionValue && getTerminationCondition().canContinue(iCurrentSolution));
    138        progress.restore();
    139
    140        if (!iCurrentSolution.getModel().unassignedVariables().isEmpty())
    141            return;
    142        progress.save();
    143        try {
    144            progress.setPhase("Fixing solution [2]", model.variables().size());
    145            NeighbourSelectionWithSuggestions ns = new NeighbourSelectionWithSuggestions(this);
    146            for (Lecture lecture : model.variables()) {
    147                Neighbour<Lecture, Placement> n = ns.selectNeighbourWithSuggestions(iCurrentSolution, lecture, 2);
    148                if (n != null && n.value() <= 0.0)
    149                    n.assign(0);
    150                iCurrentSolution.update(JProf.currentTimeSec() - startTime);
    151                progress.incProgress();
    152                if (iStop)
    153                    break;
    154            }
    155        } catch (Exception e) {
    156            sLogger.debug(e.getMessage(), e);
    157        } finally {
    158            progress.restore();
    159        }
    160    }
    161}