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