001package org.cpsolver.ifs.algorithms;
002
003import java.util.Collection;
004import java.util.Map;
005
006import org.apache.logging.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 = org.apache.logging.log4j.LogManager.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}