001package org.cpsolver.ifs.heuristics; 002 003import java.util.Collection; 004import java.util.Map; 005 006import org.apache.logging.log4j.Logger; 007import org.cpsolver.ifs.algorithms.SimpleSearch; 008import org.cpsolver.ifs.assignment.Assignment; 009import org.cpsolver.ifs.assignment.context.AssignmentContext; 010import org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext; 011import org.cpsolver.ifs.extension.ConflictStatistics; 012import org.cpsolver.ifs.extension.Extension; 013import org.cpsolver.ifs.model.Neighbour; 014import org.cpsolver.ifs.model.Value; 015import org.cpsolver.ifs.model.Variable; 016import org.cpsolver.ifs.solution.Solution; 017import org.cpsolver.ifs.solution.SolutionListener; 018import org.cpsolver.ifs.solver.Solver; 019import org.cpsolver.ifs.util.DataProperties; 020 021/** 022 * Simple extension of a provided {@link NeighbourSelection} that halts the construction 023 * heuristic or the IFS search when the underlying heuristic is unable to improve the 024 * number of assigned variables. When a given number of non-improving iterations is reached, 025 * the {@link MaxIdleNeighbourSelection} extension starts returning null. The counter gets 026 * automatically reset every time a solution with more variables assigned is stored as best 027 * solution. 028 029 * @see NeighbourSelection 030 * 031 * @version IFS 1.4 (Iterative Forward Search)<br> 032 * Copyright (C) 2024 Tomáš Müller<br> 033 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 034 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 035 * <br> 036 * This library is free software; you can redistribute it and/or modify 037 * it under the terms of the GNU Lesser General Public License as 038 * published by the Free Software Foundation; either version 3 of the 039 * License, or (at your option) any later version. <br> 040 * <br> 041 * This library is distributed in the hope that it will be useful, but 042 * WITHOUT ANY WARRANTY; without even the implied warranty of 043 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 044 * Lesser General Public License for more details. <br> 045 * <br> 046 * You should have received a copy of the GNU Lesser General Public 047 * License along with this library; if not see <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>. 048 * 049 * @param <V> Variable 050 * @param <T> Value 051 **/ 052public class MaxIdleNeighbourSelection<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSelectionWithContext<V, T, MaxIdleNeighbourSelection<V, T>.MaxIdleContext> implements SolutionListener<V, T> { 053 private Logger iLog = org.apache.logging.log4j.LogManager.getLogger(SimpleSearch.class); 054 protected NeighbourSelection<V, T> iParent = null; 055 protected int iMaxIdle = 1000; 056 protected int iBestAssigned = 0; 057 protected ConflictStatistics<V, T> iStat = null; 058 protected long iTimeOut = -1; 059 060 061 public MaxIdleNeighbourSelection(DataProperties properties, NeighbourSelection<V, T> parent, int maxIdle) { 062 iParent = parent; 063 iMaxIdle = maxIdle; 064 iTimeOut = -1; 065 try { 066 String idle = properties.getProperty("Search.MinConstructionTime", "10%"); 067 if (idle != null && !idle.isEmpty()) { 068 if (idle.endsWith("%")) { 069 iTimeOut = Math.round(0.01 * Double.parseDouble(idle.substring(0, idle.length() - 1).trim()) * 070 properties.getPropertyLong("Termination.TimeOut", 0l)); 071 } else { 072 iTimeOut = Long.parseLong(idle); 073 } 074 } 075 if (iTimeOut > 0) 076 iLog.debug("Minimal construction time is " + iTimeOut + " seconds."); 077 } catch (Exception e) { 078 iLog.warn("Failed to set the minimal construction time: " + e.getMessage()); 079 } 080 } 081 082 @Override 083 public void init(Solver<V, T> solver) { 084 super.init(solver); 085 iParent.init(solver); 086 solver.currentSolution().addSolutionListener(this); 087 for (Extension<V, T> ext: solver.getExtensions()) 088 if (ext instanceof ConflictStatistics) 089 iStat = (ConflictStatistics<V, T>)ext; 090 } 091 092 093 @Override 094 public void solutionUpdated(Solution<V, T> solution) { 095 } 096 097 @Override 098 public void getInfo(Solution<V, T> solution, Map<String, String> info) { 099 } 100 101 @Override 102 public void getInfo(Solution<V, T> solution, Map<String, String> info, Collection<V> variables) { 103 } 104 105 @Override 106 public void bestCleared(Solution<V, T> solution) { 107 iBestAssigned = 0; 108 getContext(solution.getAssignment()).clear(); 109 } 110 111 @Override 112 public void bestSaved(Solution<V, T> solution) { 113 if (solution.getAssignment().nrAssignedVariables() > iBestAssigned) { 114 long max = 0; 115 if (iStat != null) { 116 for (V v: solution.getAssignment().unassignedVariables(solution.getModel())) { 117 long count = iStat.countAssignments(v); 118 if (count > max) max = count; 119 } 120 } 121 getContext(solution.getAssignment()).reset((int)max); 122 } 123 iBestAssigned = solution.getAssignment().nrAssignedVariables(); 124 } 125 126 @Override 127 public void bestRestored(Solution<V, T> solution) { 128 } 129 130 @Override 131 public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) { 132 if (iTimeOut >= 0 && solution.getTime() < iTimeOut) return iParent.selectNeighbour(solution); 133 if (iMaxIdle < 0) return iParent.selectNeighbour(solution); 134 if (iMaxIdle == 0) return null; 135 MaxIdleContext context = getContext(solution.getAssignment()); 136 if (context.inc() >= iMaxIdle) { 137 if (iStat != null) { 138 Collection<V> unassigned = solution.getAssignment().unassignedVariables(solution.getModel()); 139 for (V v: unassigned) { 140 if (iStat.countAssignments(v) < context.getLimit()) 141 return iParent.selectNeighbour(solution); 142 } 143 return null; 144 } else { 145 return null; 146 } 147 } 148 return iParent.selectNeighbour(solution); 149 } 150 151 @Override 152 public MaxIdleContext createAssignmentContext(Assignment<V, T> assignment) { 153 return new MaxIdleContext(assignment); 154 } 155 156 public class MaxIdleContext implements AssignmentContext { 157 private int iCounter = 0; 158 private int iLimit = 0; 159 160 public MaxIdleContext(Assignment<V, T> assignment) { 161 } 162 163 public int getLimit() { 164 if (iLimit <= 0) iLimit = iMaxIdle; 165 return iLimit; 166 } 167 168 public int inc() { return iCounter++; } 169 public void reset(int max) { 170 iCounter = 0; 171 iLimit = max + iMaxIdle; 172 } 173 public void clear() { 174 iCounter = 0; 175 iLimit = iMaxIdle; 176 } 177 178 } 179}