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