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}