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