    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}