001package org.cpsolver.ifs.termination; 002 003import org.cpsolver.ifs.model.Value; 004import org.cpsolver.ifs.model.Variable; 005import org.cpsolver.ifs.solution.Solution; 006import org.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' summary='Related Solver Parameters'> 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 org.cpsolver.ifs.solver.Solver 057 * @see org.cpsolver.ifs.perturbations.PerturbationsCounter 058 * 059 * @version IFS 1.3 (Iterative Forward Search)<br> 060 * Copyright (C) 2006 - 2014 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 <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>. 076 * 077 * @param <V> Variable 078 * @param <T> Value 079 **/ 080public class MPPTerminationCondition<V extends Variable<V, T>, T extends Value<V, T>> implements 081 TerminationCondition<V, T> { 082 protected static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(MPPTerminationCondition.class); 083 private int iMinPerturbances; 084 private int iMaxIter; 085 private double iTimeOut; 086 private double iMinPertPenalty; 087 private boolean iStopWhenComplete; 088 089 public MPPTerminationCondition(DataProperties properties) { 090 iMaxIter = properties.getPropertyInt("Termination.MaxIters", -1); 091 iTimeOut = properties.getPropertyDouble("Termination.TimeOut", -1.0); 092 iMinPerturbances = properties.getPropertyInt("Termination.MinPerturbances", -1); 093 iStopWhenComplete = properties.getPropertyBoolean("Termination.StopWhenComplete", false); 094 iMinPertPenalty = properties.getPropertyDouble("Termination.MinPerturbationPenalty", -1.0); 095 } 096 097 public MPPTerminationCondition(int maxIter, double timeout, int minPerturbances) { 098 iMaxIter = maxIter; 099 iMinPerturbances = minPerturbances; 100 iTimeOut = timeout; 101 } 102 103 @Override 104 public boolean canContinue(Solution<V, T> currentSolution) { 105 if (iMinPerturbances >= 0 && currentSolution.getAssignment().nrUnassignedVariables(currentSolution.getModel()) == 0 106 && currentSolution.getModel().perturbVariables(currentSolution.getAssignment()).size() <= iMinPerturbances) { 107 sLogger.info("A complete solution with allowed number of perturbances found."); 108 return false; 109 } 110 if (iMinPertPenalty >= 0.0 111 && currentSolution.getAssignment().nrUnassignedVariables(currentSolution.getModel()) == 0 112 && currentSolution.getPerturbationsCounter().getPerturbationPenalty(currentSolution.getAssignment(), currentSolution.getModel()) <= iMinPertPenalty) { 113 sLogger.info("A complete solution with allowed perturbation penalty found."); 114 return false; 115 } 116 if (iMaxIter >= 0 && currentSolution.getIteration() >= iMaxIter) { 117 sLogger.info("Maximum number of iteration reached."); 118 return false; 119 } 120 if (iTimeOut >= 0 && currentSolution.getTime() > iTimeOut) { 121 sLogger.info("Timeout reached."); 122 return false; 123 } 124 if (iStopWhenComplete || (iMaxIter < 0 && iTimeOut < 0)) { 125 boolean ret = (currentSolution.getAssignment().nrUnassignedVariables(currentSolution.getModel()) != 0); 126 if (!ret) 127 sLogger.info("Complete solution found."); 128 return ret; 129 } 130 return true; 131 } 132 133}