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    }