    001package org.cpsolver.ifs.algorithms;
    002
    003import java.util.Collection;
    004import java.util.Map;
    005
    006import org.apache.log4j.Logger;
    007import org.cpsolver.ifs.assignment.Assignment;
    008import org.cpsolver.ifs.assignment.context.AssignmentContext;
    009import org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext;
    010import org.cpsolver.ifs.heuristics.NeighbourSelection;
    011import org.cpsolver.ifs.model.Model;
    012import org.cpsolver.ifs.model.Neighbour;
    013import org.cpsolver.ifs.model.SimpleNeighbour;
    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.ParallelSolver;
    019import org.cpsolver.ifs.solver.Solver;
    020import org.cpsolver.ifs.util.DataProperties;
    021import org.cpsolver.ifs.util.ToolBox;
    022
    023
    024/**
    025 * A simple neighbourhood selection extension suitable for the {@link ParallelSolver}
    026 * during the construction phase. If the best ever found solution was found by a different
    027 * thread ({@link Assignment#getIndex()} does not match) and the current solution has
    028 * a smaller number of variables assigned for at least the given number of iterations
    029 * (parameter ParallelConstruction.MaxIdle, defaults to 100), start assigning unassigned variables
    030 * to their best values. Otherwise, pass the selection to the provided neighbourhood selection.
    031 *
    032 * @version IFS 1.3 (Iterative Forward Search)<br>
    033 *          Copyright (C) 2014 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
    049 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    050 * @param <V> Variable
    051 * @param <T> Value
    052 */
    053public class ParallelConstruction<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSelectionWithContext<V, T, ParallelConstruction<V, T>.ConstructionContext> implements SolutionListener<V, T> {
    054    protected static Logger sLog = Logger.getLogger(ParallelConstruction.class);
    055    protected NeighbourSelection<V, T> iParent = null;
    056    protected Double iBestValue = null;
    057    protected int iBestIndex = -1, iBestAssigned = 0;
    058    protected int iMaxIdle = 100;
    059
    060    public ParallelConstruction(DataProperties config, NeighbourSelection<V, T> parent) {
    061        iParent = parent;
    062        iMaxIdle = config.getPropertyInt("ParallelConstruction.MaxIdle", iMaxIdle);
    063    }
    064
    065    @Override
    066    public void init(Solver<V, T> solver) {
    067        super.init(solver);
    068        iParent.init(solver);
    069        solver.currentSolution().addSolutionListener(this);
    070    }
    071
    072
    073    @Override
    074    public void solutionUpdated(Solution<V, T> solution) {
    075    }
    076
    077    @Override
    078    public void getInfo(Solution<V, T> solution, Map<String, String> info) {
    079    }
    080
    081    @Override
    082    public void getInfo(Solution<V, T> solution, Map<String, String> info, Collection<V> variables) {
    083    }
    084
    085    @Override
    086    public void bestCleared(Solution<V, T> solution) {
    087    }
    088
    089    @Override
    090    public void bestSaved(Solution<V, T> solution) {
    091        iBestValue = solution.getBestValue();
    092        iBestIndex = solution.getAssignment().getIndex();
    093        iBestAssigned = solution.getAssignment().nrAssignedVariables();
    094        getContext(solution.getAssignment()).reset();
    095    }
    096
    097    @Override
    098    public void bestRestored(Solution<V, T> solution) {
    099    }
    100
    101    @Override
    102    public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) {
    103        if (iBestValue != null && iBestIndex != solution.getAssignment().getIndex()) {
    104            ConstructionContext context = getContext(solution.getAssignment());
    105            if (solution.getAssignment().nrAssignedVariables() == iBestAssigned) {
    106                context.reset();
    107            } else if (solution.getAssignment().nrAssignedVariables() < iBestAssigned && context.inc() >= iMaxIdle) {
    108                Model<V, T> model = solution.getModel();
    109                Assignment<V, T> assignment = solution.getAssignment();
    110                int idx = ToolBox.random(model.countVariables());
    111                for (int i = 0; i < model.countVariables(); i++) {
    112                    V variable = model.variables().get((i + idx) % model.countVariables());
    113                    T value = assignment.getValue(variable);
    114                    T best = variable.getBestAssignment();
    115                    if (value == null && best != null)
    116                        return new SimpleNeighbour<V, T>(variable, best, model.conflictValues(solution.getAssignment(), best));
    117                }
    118            }
    119        }
    120        return iParent.selectNeighbour(solution);
    121    }
    122
    123    @Override
    124    public ConstructionContext createAssignmentContext(Assignment<V, T> assignment) {
    125        return new ConstructionContext(assignment);
    126    }
    127
    128    public class ConstructionContext implements AssignmentContext {
    129        private int iCounter = 0;
    130
    131        public ConstructionContext(Assignment<V, T> assignment) {
    132        }
    133
    134        public int inc() { return iCounter++; }
    135        public void reset() { iCounter = 0; }
    136
    137    }
    138
    139}