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}