    001package net.sf.cpsolver.ifs.termination;
    002
    003import net.sf.cpsolver.ifs.model.Value;
    004import net.sf.cpsolver.ifs.model.Variable;
    005import net.sf.cpsolver.ifs.solution.Solution;
    006import 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 Tomáš Müller<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 **/
    077public 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}