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}