001    package net.sf.cpsolver.coursett;
002    
003    import net.sf.cpsolver.coursett.heuristics.NeighbourSelectionWithSuggestions;
004    import net.sf.cpsolver.coursett.model.Lecture;
005    import net.sf.cpsolver.coursett.model.Placement;
006    import net.sf.cpsolver.coursett.model.TimetableModel;
007    import net.sf.cpsolver.ifs.model.Neighbour;
008    import net.sf.cpsolver.ifs.solver.Solver;
009    import net.sf.cpsolver.ifs.util.DataProperties;
010    import net.sf.cpsolver.ifs.util.JProf;
011    import 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 Tomas Muller<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    
040    public class TimetableSolver extends Solver<Lecture, Placement> {
041    
042        public TimetableSolver(DataProperties properties) {
043            super(properties);
044        }
045    
046        @Override
047        protected void onAssigned(double startTime) {
048            // Check if the solution is the best ever found one
049            if (iCurrentSolution.getModel().unassignedVariables().isEmpty()
050                    && getSolutionComparator().isBetterThanBestSolution(iCurrentSolution)) {
051                fixCompleteSolution(startTime);
052            } /*
053               * else { // If the solver is not able to improve solution in the last
054               * 5000 iterations, take the best one and try to fix it if
055               * (iCurrentSolution.getBestInfo()!=null &&
056               * iCurrentSolution.getModel().getBestUnassignedVariables()>0 &&
057               * iCurrentSolution
058               * .getIteration()==iCurrentSolution.getBestIteration()+5000) {
059               * iCurrentSolution.restoreBest(); fixCompleteSolution(startTime); } }
060               */
061        }
062    
063        /**
064         * Try to improve existing solution by backtracking search of very limited
065         * depth. See {@link NeighbourSelectionWithSuggestions} for more details.
066         */
067        protected void fixCompleteSolution(double startTime) {
068            Progress progress = Progress.getInstance(currentSolution().getModel());
069    
070            TimetableModel model = (TimetableModel) iCurrentSolution.getModel();
071            iCurrentSolution.saveBest();
072            progress.save();
073            double solutionValue = 0.0, newSolutionValue = model.getTotalValue();
074            do {
075                solutionValue = newSolutionValue;
076                progress.setPhase("Fixing solution", model.variables().size());
077                for (Lecture variable : model.variables()) {
078                    Placement bestValue = null;
079                    double bestVal = 0.0;
080                    Placement currentValue = variable.getAssignment();
081                    if (currentValue == null)
082                        continue;
083                    double currentVal = currentValue.toDouble();
084                    for (Placement value : variable.values()) {
085                        if (value.equals(currentValue))
086                            continue;
087                        if (model.conflictValues(value).isEmpty()) {
088                            double val = value.toDouble();
089                            if (bestValue == null || val < bestVal) {
090                                bestValue = value;
091                                bestVal = val;
092                            }
093                        }
094                    }
095                    if (bestValue != null && bestVal < currentVal)
096                        variable.assign(0, bestValue);
097                    iCurrentSolution.update(JProf.currentTimeSec() - startTime);
098                    progress.incProgress();
099                    if (iStop)
100                        break;
101                }
102                newSolutionValue = model.getTotalValue();
103                if (newSolutionValue < solutionValue) {
104                    progress.debug("New solution value is  " + newSolutionValue);
105                }
106            } while (!iStop && newSolutionValue < solutionValue && getTerminationCondition().canContinue(iCurrentSolution));
107            progress.restore();
108    
109            if (!iCurrentSolution.getModel().unassignedVariables().isEmpty())
110                return;
111            progress.save();
112            try {
113                progress.setPhase("Fixing solution [2]", model.variables().size());
114                NeighbourSelectionWithSuggestions ns = new NeighbourSelectionWithSuggestions(this);
115                for (Lecture lecture : model.variables()) {
116                    Neighbour<Lecture, Placement> n = ns.selectNeighbourWithSuggestions(iCurrentSolution, lecture, 2);
117                    if (n != null && n.value() <= 0.0)
118                        n.assign(0);
119                    iCurrentSolution.update(JProf.currentTimeSec() - startTime);
120                    progress.incProgress();
121                    if (iStop)
122                        break;
123                }
124            } catch (Exception e) {
125                sLogger.debug(e.getMessage(), e);
126            } finally {
127                progress.restore();
128            }
129        }
130    }