001 package net.sf.cpsolver.ifs.extension;
002
003 import java.util.*;
004
005 import net.sf.cpsolver.ifs.model.*;
006 import net.sf.cpsolver.ifs.solution.*;
007 import net.sf.cpsolver.ifs.solver.*;
008 import net.sf.cpsolver.ifs.util.*;
009
010 /**
011 * Go back to the best known solution when no better solution is found within the given amount of iterations.
012 *
013 * @version
014 * IFS 1.1 (Iterative Forward Search)<br>
015 * Copyright (C) 2006 Tomáš Müller<br>
016 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
017 * Lazenska 391, 76314 Zlin, Czech Republic<br>
018 * <br>
019 * This library is free software; you can redistribute it and/or
020 * modify it under the terms of the GNU Lesser General Public
021 * License as published by the Free Software Foundation; either
022 * version 2.1 of the License, or (at your option) any later version.
023 * <br><br>
024 * This library is distributed in the hope that it will be useful,
025 * but WITHOUT ANY WARRANTY; without even the implied warranty of
026 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
027 * Lesser General Public License for more details.
028 * <br><br>
029 * You should have received a copy of the GNU Lesser General Public
030 * License along with this library; if not, write to the Free Software
031 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
032 */
033 public class SearchIntensification extends Extension implements SolutionListener {
034 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(SearchIntensification.class);
035 private long iInitialIterationLimit = 100;
036 private long iIterationLimit = 100;
037 private long iLastReturn = 0;
038 private ConflictStatistics iCBS = null;
039 private int iResetInterval = 5;
040 private int iResetCounter = 0;
041 private int iMux = 2;
042 private int iMuxInterval = 2;
043 private int iMuxCounter = 0;
044
045 public SearchIntensification(Solver solver, DataProperties properties) {
046 super(solver, properties);
047 iInitialIterationLimit = properties.getPropertyLong("SearchIntensification.IterationLimit", iInitialIterationLimit);
048 iResetInterval = properties.getPropertyInt("SearchIntensification.ResetInterval", iResetInterval);
049 iMuxInterval = properties.getPropertyInt("SearchIntensification.MultiplyInterval", iMuxInterval);
050 iMux = properties.getPropertyInt("SearchIntensification.Multiply", iMux);
051 }
052
053 public boolean init(Solver solver) {
054 if (iResetInterval>0) {
055 for (Enumeration e=solver.getExtensions().elements();e.hasMoreElements();) {
056 Extension ex = (Extension)e.nextElement();
057 if (ex instanceof ConflictStatistics) {
058 iCBS = (ConflictStatistics)ex;
059 break;
060 }
061 }
062 }
063 return super.init(solver);
064 }
065
066 public void register(Model model) {
067 super.register(model);
068 getSolver().currentSolution().addSolutionListener(this);
069 }
070
071 public void unregister(Model model) {
072 super.unregister(model);
073 getSolver().currentSolution().removeSolutionListener(this);
074 }
075
076 public void afterAssigned(long iteration, Value value) {
077 if (iIterationLimit>0 && iteration>0) {
078 Solution solution = getSolver().currentSolution();
079 if (solution.getBestIteration()<0 || !solution.isBestComplete()) return;
080 long bestIt = Math.max(solution.getBestIteration(), iLastReturn);
081 long currIt = solution.getIteration();
082 if (currIt - bestIt > iIterationLimit) {
083 iLastReturn = currIt; iResetCounter++; iMuxCounter++;
084 sLogger.debug("Going back to the best known solution...");
085 solution.restoreBest();
086 sLogger.debug("Reset counter set to "+iResetCounter);
087 if (iMuxInterval>0 && (iMuxCounter%iMuxInterval)==0) {
088 iIterationLimit *= iMux;
089 sLogger.debug("Iteration limit increased to "+iIterationLimit);
090 }
091 if (iCBS!=null && iResetInterval>0 && (iResetCounter%iResetInterval)==0) {
092 sLogger.debug("Reseting CBS...");
093 iCBS.reset();
094 }
095 }
096 }
097 }
098 public void bestSaved(Solution solution) {
099 if (iResetCounter>0)
100 sLogger.debug("Reset counter set to zero.");
101 iResetCounter = 0; iMuxCounter = 0; iIterationLimit = iInitialIterationLimit;
102 }
103 public void solutionUpdated(Solution solution) {
104 }
105 public void bestCleared(Solution solution) {
106 }
107 public void bestRestored(Solution solution) {
108 }
109 public void getInfo(Solution solution, Dictionary info) {
110 }
111 public void getInfo(Solution solution, Dictionary info, Vector variables) {
112 }
113 }