001 package net.sf.cpsolver.ifs.termination;
002
003 import net.sf.cpsolver.ifs.model.Value;
004 import net.sf.cpsolver.ifs.model.Variable;
005 import net.sf.cpsolver.ifs.solution.Solution;
006 import net.sf.cpsolver.ifs.util.DataProperties;
007
008 /**
009 * General implementation of termination condition for minimal perturbation
010 * problem. <br>
011 * <br>
012 * Solver stops when a timeout is reached (expressed either by the number of
013 * iterations or by a time) or when an acceptable complete (all variables are
014 * assigned) solution is found. The acceptance of a solution is expressed either
015 * by the minimal number of variables assigned to not-initial values or by the
016 * perturbations penalty. <br>
017 * <br>
018 * Parameters: <br>
019 * <table border='1'>
020 * <tr>
021 * <th>Parameter</th>
022 * <th>Type</th>
023 * <th>Comment</th>
024 * </tr>
025 * <tr>
026 * <td>Termination.StopWhenComplete</td>
027 * <td>{@link Double}</td>
028 * <td>if true, solver stops when a complete solution is found</td>
029 * </tr>
030 * <tr>
031 * <td>Termination.MaxIters</td>
032 * <td>{@link Integer}</td>
033 * <td>if zero or positive, solver stops when the given number of iteration is
034 * reached</td>
035 * </tr>
036 * <tr>
037 * <td>Termination.TimeOut</td>
038 * <td>{@link Double}</td>
039 * <td>if zero or positive, solver stops when the given timeout (given in
040 * seconds) is reached</td>
041 * </tr>
042 * <tr>
043 * <td>Termination.MinPerturbances</td>
044 * <td>{@link Integer}</td>
045 * <td>if zero or positive, solver stops when the solution is complete and the
046 * number of variables with non-initial values is below or equal to this limit</td>
047 * </tr>
048 * <tr>
049 * <td>Termination.MinPerturbationPenalty</td>
050 * <td>{@link Double}</td>
051 * <td>if zero or positive, solver stops when the solution is complete and when
052 * the perturbation penaly of the solution is below or equal to this limit</td>
053 * </tr>
054 * </table>
055 *
056 * @see net.sf.cpsolver.ifs.solver.Solver
057 * @see net.sf.cpsolver.ifs.perturbations.PerturbationsCounter
058 *
059 * @version IFS 1.2 (Iterative Forward Search)<br>
060 * Copyright (C) 2006 - 2010 Tomas Muller<br>
061 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
062 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
063 * <br>
064 * This library is free software; you can redistribute it and/or modify
065 * it under the terms of the GNU Lesser General Public License as
066 * published by the Free Software Foundation; either version 3 of the
067 * License, or (at your option) any later version. <br>
068 * <br>
069 * This library is distributed in the hope that it will be useful, but
070 * WITHOUT ANY WARRANTY; without even the implied warranty of
071 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
072 * Lesser General Public License for more details. <br>
073 * <br>
074 * You should have received a copy of the GNU Lesser General Public
075 * License along with this library; if not see <http://www.gnu.org/licenses/>.
076 **/
077 public class MPPTerminationCondition<V extends Variable<V, T>, T extends Value<V, T>> implements
078 TerminationCondition<V, T> {
079 protected static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(MPPTerminationCondition.class);
080 private int iMinPerturbances;
081 private int iMaxIter;
082 private double iTimeOut;
083 private double iMinPertPenalty;
084 private boolean iStopWhenComplete;
085
086 public MPPTerminationCondition(DataProperties properties) {
087 iMaxIter = properties.getPropertyInt("Termination.MaxIters", -1);
088 iTimeOut = properties.getPropertyDouble("Termination.TimeOut", -1.0);
089 iMinPerturbances = properties.getPropertyInt("Termination.MinPerturbances", -1);
090 iStopWhenComplete = properties.getPropertyBoolean("Termination.StopWhenComplete", false);
091 iMinPertPenalty = properties.getPropertyDouble("Termination.MinPerturbationPenalty", -1.0);
092 }
093
094 public MPPTerminationCondition(int maxIter, double timeout, int minPerturbances) {
095 iMaxIter = maxIter;
096 iMinPerturbances = minPerturbances;
097 iTimeOut = timeout;
098 }
099
100 @Override
101 public boolean canContinue(Solution<V, T> currentSolution) {
102 if (iMinPerturbances >= 0 && currentSolution.getModel().nrUnassignedVariables() == 0
103 && currentSolution.getModel().perturbVariables().size() <= iMinPerturbances) {
104 sLogger.info("A complete solution with allowed number of perturbances found.");
105 return false;
106 }
107 if (iMinPertPenalty >= 0.0
108 && currentSolution.getModel().nrUnassignedVariables() == 0
109 && currentSolution.getPerturbationsCounter().getPerturbationPenalty(currentSolution.getModel()) <= iMinPertPenalty) {
110 sLogger.info("A complete solution with allowed perturbation penalty found.");
111 return false;
112 }
113 if (iMaxIter >= 0 && currentSolution.getIteration() >= iMaxIter) {
114 sLogger.info("Maximum number of iteration reached.");
115 return false;
116 }
117 if (iTimeOut >= 0 && currentSolution.getTime() > iTimeOut) {
118 sLogger.info("Timeout reached.");
119 return false;
120 }
121 if (iStopWhenComplete || (iMaxIter < 0 && iTimeOut < 0)) {
122 boolean ret = (currentSolution.getModel().nrUnassignedVariables() != 0);
123 if (!ret)
124 sLogger.info("Complete solution found.");
125 return ret;
126 }
127 return true;
128 }
129
130 }