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 * @author  Tomáš Müller
029 * @version CourseTT 1.3 (University Course Timetabling)<br>
030 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
031 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
032 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
033 * <br>
034 *          This library is free software; you can redistribute it and/or modify
035 *          it under the terms of the GNU Lesser General Public License as
036 *          published by the Free Software Foundation; either version 3 of the
037 *          License, or (at your option) any later version. <br>
038 * <br>
039 *          This library is distributed in the hope that it will be useful, but
040 *          WITHOUT ANY WARRANTY; without even the implied warranty of
041 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
042 *          Lesser General Public License for more details. <br>
043 * <br>
044 *          You should have received a copy of the GNU Lesser General Public
045 *          License along with this library; if not see
046 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
047 */
048public class FixCompleteSolutionNeighbourSelection extends NeighbourSelectionWithContext<Lecture, Placement, FixCompleteSolutionNeighbourSelection.FixCompleteSolutionNeighbourContext> {
049    private NeighbourSelection<Lecture, Placement> iParent = null;
050    private long iLastCompleteSolutionFixIteration = -1;
051    private long iLastIncompleteSolutionFixIteration = -1;
052    private long iCompleteSolutionFixInterval = 1;
053    private long iIncompleteSolutionFixInterval = 5000;
054    private NeighbourSelectionWithSuggestions iSuggestions = null;
055    private Progress iProgress = null;
056    private Solver<Lecture, Placement> iSolver = null;
057
058    public FixCompleteSolutionNeighbourSelection(DataProperties config, NeighbourSelection<Lecture, Placement> parent) throws Exception {
059        iParent = parent;
060        iSuggestions = new NeighbourSelectionWithSuggestions(config);
061    }
062    
063    public FixCompleteSolutionNeighbourSelection(DataProperties config) throws Exception {
064        this(config, new NeighbourSelectionWithSuggestions(config));
065    }
066    
067    @Override
068    public void init(Solver<Lecture, Placement> solver) {
069        super.init(solver);
070        iCompleteSolutionFixInterval = solver.getProperties().getPropertyLong("General.CompleteSolutionFixInterval", iCompleteSolutionFixInterval);
071        iIncompleteSolutionFixInterval = solver.getProperties().getPropertyLong("General.IncompleteSolutionFixInterval", iIncompleteSolutionFixInterval);
072        iSuggestions.init(solver);
073        iParent.init(solver);
074        iProgress = Progress.getInstance(solver.currentSolution().getModel());
075        iLastIncompleteSolutionFixIteration = -1;
076        iLastCompleteSolutionFixIteration = -1;
077        iSolver = solver;
078    }
079
080    /**
081     * Try to improve existing solution by backtracking search of very limited
082     * depth. See {@link NeighbourSelectionWithSuggestions} for more details.
083     */
084    @Override
085    public Neighbour<Lecture, Placement> selectNeighbour(Solution<Lecture, Placement> solution) {
086        FixCompleteSolutionNeighbourContext context = getContext(solution.getAssignment());
087        if (context.getPhase() == 0) {
088            if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) == 0) {
089                // complete solution was found
090                if (iCompleteSolutionFixInterval < 0) {
091                    // feature disabled
092                    return iParent.selectNeighbour(solution);
093                } else if (iCompleteSolutionFixInterval == 0) {
094                    // only run first time a complete solution is found
095                    if (iLastCompleteSolutionFixIteration >= 0) return iParent.selectNeighbour(solution);
096                } else {
097                    // run first time and if not run for a given number of iterations
098                    if (iLastCompleteSolutionFixIteration >= 0 && solution.getIteration() - iLastCompleteSolutionFixIteration < iCompleteSolutionFixInterval)
099                        return iParent.selectNeighbour(solution);
100                }
101                if (solution.getBestIteration() == solution.getIteration())
102                    context.incPhase(solution);
103            } else if (!solution.isBestComplete()) {
104                // complete solution has not been found yet
105                if (iIncompleteSolutionFixInterval < 0) {
106                    // feature disabled
107                    return iParent.selectNeighbour(solution);
108                } else if (iIncompleteSolutionFixInterval == 0) {
109                    // only run first time a complete solution is found
110                    if (iLastIncompleteSolutionFixIteration >= 0)
111                        return iParent.selectNeighbour(solution);
112                } else {
113                    // run first time and if not run for a given number of iterations
114                    if (solution.getIteration() - iLastIncompleteSolutionFixIteration < iIncompleteSolutionFixInterval)
115                        return iParent.selectNeighbour(solution);
116                }
117                if (solution.getBestIteration() == solution.getIteration())
118                    context.incPhase(solution);
119            }
120        }
121        
122        while (context.getPhase() > 0 && !iSolver.isStop()) {
123            if (context.hasMoreElements()) {
124                Lecture variable = context.nextElement();
125                // iProgress.incProgress();
126                if (context.getPhase() == 1) {
127                    Placement bestValue = null;
128                    double bestVal = 0.0;
129                    Placement currentValue = solution.getAssignment().getValue(variable);
130                    if (currentValue == null)
131                        continue;
132                    double currentVal = currentValue.toDouble(solution.getAssignment());
133                    for (Placement value : variable.values(solution.getAssignment())) {
134                        if (value.equals(currentValue))
135                            continue;
136                        if (solution.getModel().conflictValues(solution.getAssignment(), value).isEmpty()) {
137                            double val = value.toDouble(solution.getAssignment());
138                            if (bestValue == null || val < bestVal) {
139                                bestValue = value;
140                                bestVal = val;
141                            }
142                        }
143                    }
144                    if (bestValue != null && bestVal < currentVal)
145                        return new SimpleNeighbour<Lecture, Placement>(variable, bestValue);                    
146                } else {
147                    Neighbour<Lecture, Placement> n = iSuggestions.selectNeighbourWithSuggestions(solution, variable, 2);
148                    if (n != null && n.value(solution.getAssignment()) <= solution.getModel().getTotalValue(solution.getAssignment()))
149                        return n;
150                }
151            } else {
152                context.incPhase(solution);
153            }
154        }
155        return iParent.selectNeighbour(solution);
156    }
157    
158    @Override
159    public FixCompleteSolutionNeighbourContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
160        return new FixCompleteSolutionNeighbourContext(assignment);
161    }
162
163    public class FixCompleteSolutionNeighbourContext implements AssignmentContext, Enumeration<Lecture> {
164        private int iPhase = 0;
165        private Iterator<Lecture> iLectures = null;
166        
167        public FixCompleteSolutionNeighbourContext(Assignment<Lecture, Placement> assignment) {}
168        
169        public int getPhase() { return iPhase; }
170        
171        public void incPhase(Solution<Lecture, Placement> solution) {
172            // Progress progress = Progress.getInstance(solution.getModel());                
173            if (iPhase == 0) {
174                // iSolver.setUpdateProgress(false);
175                iPhase = 1;
176                solution.saveBest();
177                // progress.setPhase("Fixing solution", solution.getModel().countVariables());
178                iProgress.info("[" + Thread.currentThread().getName() + "] Fixing solution...");
179                iLectures = new ArrayList<Lecture>(solution.getModel().variables()).iterator();
180            } else if (iPhase == 1 && solution.isComplete()) {
181                iPhase = 2;
182                iProgress.info("[" + Thread.currentThread().getName() + "] Fixing complete solution...");
183                // progress.setPhase("Fixing solution [2]", solution.getModel().countVariables());
184                iLectures = new ArrayList<Lecture>(solution.getModel().variables()).iterator();
185            } else {
186                if (iPhase == 1)
187                    iLastIncompleteSolutionFixIteration = solution.getIteration();
188                else 
189                    iLastCompleteSolutionFixIteration = solution.getIteration();
190                // iSolver.setUpdateProgress(true);
191                // if (solution.isBestComplete())
192                //     iProgress.setPhase("Improving found solution ...");
193                // else
194                //     iProgress.setPhase("Searching for initial solution ...", solution.getModel().countVariables());
195                iPhase = 0;
196                // progress.restore();
197                iLectures = null;
198            }
199        }
200
201        @Override
202        public boolean hasMoreElements() {
203            return iLectures != null && iLectures.hasNext();
204        }
205
206        @Override
207        public Lecture nextElement() {
208            return iLectures.next();
209        }
210        
211    }
212}