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}