001package org.cpsolver.exam.heuristics;
002
003import java.text.DecimalFormat;
004import java.util.ArrayList;
005import java.util.Collection;
006import java.util.List;
007import java.util.Map;
008
009
010import org.apache.log4j.Logger;
011import org.cpsolver.exam.model.Exam;
012import org.cpsolver.exam.model.ExamPlacement;
013import org.cpsolver.exam.neighbours.ExamRandomMove;
014import org.cpsolver.exam.neighbours.ExamRoomMove;
015import org.cpsolver.exam.neighbours.ExamTimeMove;
016import org.cpsolver.ifs.assignment.Assignment;
017import org.cpsolver.ifs.assignment.context.AssignmentContext;
018import org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext;
019import org.cpsolver.ifs.heuristics.NeighbourSelection;
020import org.cpsolver.ifs.model.LazyNeighbour;
021import org.cpsolver.ifs.model.Model;
022import org.cpsolver.ifs.model.Neighbour;
023import org.cpsolver.ifs.model.LazyNeighbour.LazyNeighbourAcceptanceCriterion;
024import org.cpsolver.ifs.solution.Solution;
025import org.cpsolver.ifs.solution.SolutionListener;
026import org.cpsolver.ifs.solver.Solver;
027import org.cpsolver.ifs.util.DataProperties;
028import org.cpsolver.ifs.util.JProf;
029import org.cpsolver.ifs.util.Progress;
030import org.cpsolver.ifs.util.ToolBox;
031
032/**
033 * Greate deluge. In each iteration, one of the following three neighbourhoods
034 * is selected first
035 * <ul>
036 * <li>random move ({@link ExamRandomMove})
037 * <li>period swap ({@link ExamTimeMove})
038 * <li>room swap ({@link ExamRoomMove})
039 * </ul>
040 * , then a neighbour is generated and it is accepted if the value of the new
041 * solution is below certain bound. This bound is initialized to the
042 * GreatDeluge.UpperBoundRate &times; value of the best solution ever found.
043 * After each iteration, the bound is decreased by GreatDeluge.CoolRate (new
044 * bound equals to old bound &times; GreatDeluge.CoolRate). If the bound gets
045 * bellow GreatDeluge.LowerBoundRate &times; value of the best solution ever
046 * found, it is changed back to GreatDeluge.UpperBoundRate &times; value of the
047 * best solution ever found.
048 * 
049 * If there was no improvement found between the bounds, the new bounds are
050 * changed to GreatDeluge.UpperBoundRate^2 and GreatDeluge.LowerBoundRate^2,
051 * GreatDeluge.UpperBoundRate^3 and GreatDeluge.LowerBoundRate^3, etc. till
052 * there is an improvement found. <br>
053 * <br>
054 * 
055 * @version ExamTT 1.3 (Examination Timetabling)<br>
056 *          Copyright (C) 2008 - 2014 Tomáš Müller<br>
057 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
058 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
059 * <br>
060 *          This library is free software; you can redistribute it and/or modify
061 *          it under the terms of the GNU Lesser General Public License as
062 *          published by the Free Software Foundation; either version 3 of the
063 *          License, or (at your option) any later version. <br>
064 * <br>
065 *          This library is distributed in the hope that it will be useful, but
066 *          WITHOUT ANY WARRANTY; without even the implied warranty of
067 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
068 *          Lesser General Public License for more details. <br>
069 * <br>
070 *          You should have received a copy of the GNU Lesser General Public
071 *          License along with this library; if not see
072 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
073 */
074@Deprecated
075public class ExamGreatDeluge extends NeighbourSelectionWithContext<Exam, ExamPlacement, ExamGreatDeluge.Context> implements SolutionListener<Exam, ExamPlacement>, LazyNeighbourAcceptanceCriterion<Exam, ExamPlacement> {
076    private static Logger sLog = Logger.getLogger(ExamGreatDeluge.class);
077    private static DecimalFormat sDF2 = new DecimalFormat("0.00");
078    private static DecimalFormat sDF5 = new DecimalFormat("0.00000");
079    private double iCoolRate = 0.99999995;
080    private double iUpperBoundRate = 1.05;
081    private double iLowerBoundRate = 0.95;
082    private Progress iProgress = null;
083
084    private List<NeighbourSelection<Exam, ExamPlacement>> iNeighbours = null;
085
086    /**
087     * Constructor. Following problem properties are considered:
088     * <ul>
089     * <li>GreatDeluge.CoolRate ... bound cooling rate (default 0.99999995)
090     * <li>GreatDeluge.UpperBoundRate ... bound upper bound relative to best
091     * solution ever found (default 1.05)
092     * <li>GreatDeluge.LowerBoundRate ... bound lower bound relative to best
093     * solution ever found (default 0.95)
094     * </ul>
095     * 
096     * @param properties
097     *            problem properties
098     */
099    @SuppressWarnings("unchecked")
100    public ExamGreatDeluge(DataProperties properties) {
101        iCoolRate = properties.getPropertyDouble("GreatDeluge.CoolRate", iCoolRate);
102        iUpperBoundRate = properties.getPropertyDouble("GreatDeluge.UpperBoundRate", iUpperBoundRate);
103        iLowerBoundRate = properties.getPropertyDouble("GreatDeluge.LowerBoundRate", iLowerBoundRate);
104        String neighbours = properties.getProperty("GreatDeluge.Neighbours", 
105                ExamRandomMove.class.getName() + ";" +
106                ExamRoomMove.class.getName() + ";" +
107                ExamTimeMove.class.getName());
108        neighbours += ";" + properties.getProperty("GreatDeluge.AdditionalNeighbours", "");
109        iNeighbours = new ArrayList<NeighbourSelection<Exam,ExamPlacement>>();
110        for (String neighbour: neighbours.split("\\;")) {
111            if (neighbour == null || neighbour.isEmpty()) continue;
112            try {
113                Class<NeighbourSelection<Exam, ExamPlacement>> clazz = (Class<NeighbourSelection<Exam, ExamPlacement>>)Class.forName(neighbour);
114                iNeighbours.add(clazz.getConstructor(DataProperties.class).newInstance(properties));
115            } catch (Exception e) {
116                sLog.error("Unable to use " + neighbour + ": " + e.getMessage());
117            }
118        }
119    }
120
121    /** Initialization */
122    @Override
123    public void init(Solver<Exam, ExamPlacement> solver) {
124        super.init(solver);
125        solver.currentSolution().addSolutionListener(this);
126        for (NeighbourSelection<Exam, ExamPlacement> neighbour: iNeighbours)
127            neighbour.init(solver);
128        solver.setUpdateProgress(false);
129        iProgress = Progress.getInstance(solver.currentSolution().getModel());
130        getContext(solver.currentSolution().getAssignment()).reset();
131    }
132
133    /** Print some information 
134     * @param solution current solution
135     **/
136    protected void info(Solution<Exam, ExamPlacement> solution) {
137        Assignment<Exam, ExamPlacement> assignment = solution.getAssignment();
138        getContext(assignment).info(solution);
139    }
140
141    /**
142     * Generate neighbour -- select neighbourhood randomly, select neighbour
143     * @param solution current solution
144     * @return a neigbour that was selected
145     */
146    public Neighbour<Exam, ExamPlacement> genMove(Solution<Exam, ExamPlacement> solution) {
147        while (true) {
148            incIter(solution);
149            NeighbourSelection<Exam, ExamPlacement> ns = iNeighbours.get(ToolBox.random(iNeighbours.size()));
150            Neighbour<Exam, ExamPlacement> n = ns.selectNeighbour(solution);
151            if (n != null)
152                return n;
153        }
154    }
155
156    /** Accept neighbour 
157     * @param solution current solution
158     * @param neighbour a neighbour in question
159     * @return true if the neighbour should be accepted
160     **/
161    protected boolean accept(Solution<Exam, ExamPlacement> solution, Neighbour<Exam, ExamPlacement> neighbour) {
162        if (neighbour instanceof LazyNeighbour) {
163            ((LazyNeighbour<Exam, ExamPlacement>)neighbour).setAcceptanceCriterion(this);
164            return true;
165        }
166        Assignment<Exam, ExamPlacement> assignment = solution.getAssignment();
167        return (neighbour.value(assignment) <= 0 || solution.getModel().getTotalValue(assignment) + neighbour.value(assignment) <= getContext(assignment).getBound());
168    }
169    
170    /** Accept lazy neighbour */
171    @Override
172    public boolean accept(Assignment<Exam, ExamPlacement> assignment, LazyNeighbour<Exam, ExamPlacement> neighbour, double value) {
173        return (value <= 0.0 || neighbour.getModel().getTotalValue(assignment) <= getContext(assignment).getBound());
174    }
175
176    /** Increment iteration count, update bound 
177     * @param solution current solution
178     **/
179    protected void incIter(Solution<Exam, ExamPlacement> solution) {
180        getContext(solution.getAssignment()).incIter(solution);
181    }
182
183    /**
184     * A neighbour is generated randomly untill an acceptable one is found.
185     */
186    @Override
187    public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
188        Neighbour<Exam, ExamPlacement> neighbour = null;
189        while ((neighbour = genMove(solution)) != null) {
190            getContext(solution.getAssignment()).incMoves();
191            if (accept(solution, neighbour)) {
192                getContext(solution.getAssignment()).incAcceptedMoves();
193                break;
194            }
195        }
196        return (neighbour == null ? null : neighbour);
197    }
198
199    /** Update last improving iteration count */
200    @Override
201    public void bestSaved(Solution<Exam, ExamPlacement> solution) {
202        getContext(solution.getAssignment()).bestSaved(solution.getModel());
203    }
204
205    @Override
206    public void solutionUpdated(Solution<Exam, ExamPlacement> solution) {
207    }
208
209    @Override
210    public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info) {
211    }
212
213    @Override
214    public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info, Collection<Exam> variables) {
215    }
216
217    @Override
218    public void bestCleared(Solution<Exam, ExamPlacement> solution) {
219    }
220
221    @Override
222    public void bestRestored(Solution<Exam, ExamPlacement> solution) {
223    }
224    
225    @Override
226    public Context createAssignmentContext(Assignment<Exam, ExamPlacement> assignment) {
227        return new Context();
228    }
229    
230    public class Context implements AssignmentContext {
231        private double iUpperBound;
232        private int iMoves = 0;
233        private int iAcceptedMoves = 0;
234        private int iNrIdle = 0;
235        private long iT0 = -1;
236        private long iIter = -1;
237        private double iBound = 0.0;
238        private long iLastImprovingIter = 0;
239        private double iBestValue = 0;
240        
241        protected void reset() {
242            iIter = -1;
243        }
244
245        protected void incIter(Solution<Exam, ExamPlacement> solution) {
246            double best = solution.getModel().getBestValue();
247            if (iIter < 0) {
248                iIter = 0;
249                iLastImprovingIter = 0;
250                iT0 = JProf.currentTimeMillis();
251                iBound = (best > 0.0 ? iUpperBoundRate * best : best / iUpperBoundRate);
252                iUpperBound = iBound;
253                iNrIdle = 0;
254                solution.restoreBest();
255                iProgress.setPhase("Great deluge [" + (1 + iNrIdle) + "]...");
256            } else {
257                iIter++;
258                if (best >= 0.0)
259                    iBound *= iCoolRate;
260                else
261                    iBound /= iCoolRate;
262            }
263            if (iIter % 1000 == 0 && iBound > (best > 0.0 ? iUpperBoundRate * best : best / iUpperBoundRate)) {
264                // some other thread lowered the upper bound over my bound -> adjust my bound
265                iBound = (best > 0.0 ? iUpperBoundRate * best : best / iUpperBoundRate);
266            }
267            if (iIter % 100000 == 0) {
268                info(solution);
269            }
270            double lowerBound = (best >= 0.0 ? Math.pow(iLowerBoundRate, 1 + iNrIdle) * best : best / Math.pow(iLowerBoundRate, 1 + iNrIdle));
271            if (iBound < lowerBound) {
272                iNrIdle++;
273                sLog.info(" -<[" + iNrIdle + "]>- ");
274                iBound = Math.max(best + 2.0, (best >= 0.0 ? Math.pow(iUpperBoundRate, iNrIdle) * best : best / Math.pow(iUpperBoundRate, iNrIdle)));
275                iUpperBound = iBound;
276                iProgress.setPhase("Great deluge [" + (1 + iNrIdle) + "]...");
277                solution.restoreBest();
278            }
279            iProgress.setProgress(100 - Math.round(100.0 * (iBound - lowerBound) / (iUpperBound - lowerBound)));
280        }
281        
282        protected void info(Solution<Exam, ExamPlacement> solution) {
283            sLog.info("Iter=" + iIter / 1000 + "k, NonImpIter=" + sDF2.format((iIter - iLastImprovingIter) / 1000.0)
284                    + "k, Speed=" + sDF2.format(1000.0 * iIter / (JProf.currentTimeMillis() - iT0)) + " it/s");
285            sLog.info("Bound is " + sDF2.format(iBound) + ", " + "best value is " + sDF2.format(solution.getModel().getBestValue())
286                    + " (" + sDF2.format(100.0 * iBound / solution.getModel().getBestValue()) + "%), " + "current value is "
287                    + sDF2.format(solution.getModel().getTotalValue(solution.getAssignment())) + " ("
288                    + sDF2.format(100.0 * iBound / solution.getModel().getTotalValue(solution.getAssignment())) + "%), " + "#idle=" + iNrIdle
289                    + ", " + "Pacc=" + sDF5.format(100.0 * iAcceptedMoves / iMoves) + "%");
290            iAcceptedMoves = iMoves = 0;
291        }
292        
293        protected void bestSaved(Model<Exam, ExamPlacement> model) {
294            if (Math.abs(iBestValue - model.getBestValue()) >= 1.0) {
295                iLastImprovingIter = iIter;
296                iNrIdle = 0;
297                iBestValue = model.getBestValue();
298            }
299        }
300        
301        public double getBound() { return iBound; }
302        
303        public void incMoves() { iMoves ++; }
304        
305        public void incAcceptedMoves() { iAcceptedMoves ++; }
306    }
307}