001package net.sf.cpsolver.ifs.algorithms.neighbourhoods;
002
003import java.util.ArrayList;
004import java.util.Collection;
005import java.util.HashMap;
006import java.util.Iterator;
007import java.util.List;
008import java.util.Map;
009import java.util.Set;
010
011import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
012import net.sf.cpsolver.ifs.model.Model;
013import net.sf.cpsolver.ifs.model.Neighbour;
014import net.sf.cpsolver.ifs.model.SimpleNeighbour;
015import net.sf.cpsolver.ifs.model.Value;
016import net.sf.cpsolver.ifs.model.Variable;
017import net.sf.cpsolver.ifs.solution.Solution;
018import net.sf.cpsolver.ifs.solver.Solver;
019import net.sf.cpsolver.ifs.util.DataProperties;
020import net.sf.cpsolver.ifs.util.JProf;
021import net.sf.cpsolver.ifs.util.ToolBox;
022
023/**
024 * Try to assign a variable with a new value. A variable is selected randomly, a
025 * different value is randomly selected for the variable -- the variable is
026 * assigned with the new value.  If there is a conflict, it tries to resolve these
027 * conflicts by assigning conflicting variables to other values as well.
028 * <br>
029 * 
030 * @version IFS 1.2 (Iterative Forward Search)<br>
031 *          Copyright (C) 2014 Tomáš Müller<br>
032 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
033 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
034 * <br>
035 *          This library is free software; you can redistribute it and/or modify
036 *          it under the terms of the GNU Lesser General Public License as
037 *          published by the Free Software Foundation; either version 3 of the
038 *          License, or (at your option) any later version. <br>
039 * <br>
040 *          This library is distributed in the hope that it will be useful, but
041 *          WITHOUT ANY WARRANTY; without even the implied warranty of
042 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
043 *          Lesser General Public License for more details. <br>
044 * <br>
045 *          You should have received a copy of the GNU Lesser General Public
046 *          License along with this library; if not see
047 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
048 */
049public class RandomSwapMove<V extends Variable<V, T>, T extends Value<V, T>> implements NeighbourSelection<V, T>, HillClimberSelection {
050    protected int iMaxAttempts = 3;
051    protected boolean iHC = false;
052    protected int iTimeLimit = 200;
053
054    public RandomSwapMove(DataProperties config) {
055        iMaxAttempts = config.getPropertyInt("RandomSwap.MaxAttempts", iMaxAttempts);
056        iTimeLimit = config.getPropertyInt("RandomSwap.TimeLimit", iTimeLimit);
057    }
058    
059    @Override
060    public void setHcMode(boolean hcMode) {
061        iHC = hcMode;
062    }
063
064    @Override
065    public void init(Solver<V, T> solver) {
066    }
067
068    @Override
069    public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) {
070        Model<V, T> model = solution.getModel();
071        double total = model.getTotalValue();
072        int varIdx = ToolBox.random(model.variables().size());
073        for (int i = 0; i < model.variables().size(); i++) {
074            V variable = model.variables().get((i + varIdx) % model.variables().size());
075            List<T> values = variable.values();
076            if (values.isEmpty()) continue;
077            int valIdx = ToolBox.random(values.size());
078            T old = variable.getAssignment();
079            
080            int attempts = 0;
081            long startTime = JProf.currentTimeMillis();
082            for (int j = 0; j < values.size(); j++) {
083                T value = values.get((j + valIdx) % values.size());
084                if (value.equals(old)) continue;
085                
086                Set<T> conflicts = model.conflictValues(value);
087                if (conflicts.contains(value)) continue;
088                if (conflicts.isEmpty()) {
089                    SimpleNeighbour<V, T> n = new SimpleNeighbour<V, T>(variable, value);
090                    if (!iHC || n.value() <= 0) return n;
091                    else continue;
092                }
093                
094                Map<V, T> assignments = new HashMap<V, T>();
095                assignments.put(variable, value);
096                
097                for (T conflict: conflicts)
098                    conflict.variable().unassign(solution.getIteration());
099                variable.assign(solution.getIteration(), value);
100                
101                Double v = resolve(solution, total, startTime, assignments, new ArrayList<T>(conflicts), 0);
102                if (!conflicts.isEmpty())
103                    attempts ++;
104                
105                variable.unassign(solution.getIteration());
106                for (T conflict: conflicts)
107                    conflict.variable().assign(solution.getIteration(), conflict);
108                if (old != null) variable.assign(solution.getIteration(), old);
109                
110                if (v != null)
111                    return new SwapNeighbour(assignments.values(), v);
112                
113                if (attempts >= iMaxAttempts) break;
114            }
115        }
116        return null;
117    }
118    
119    /**
120     * Return true if the time limit was reached, number of attempts are limited to 1 in such a case.
121     */
122    protected boolean isTimeLimitReached(long startTime) {
123        return iTimeLimit > 0 && (JProf.currentTimeMillis() - startTime) > iTimeLimit;
124    }
125    
126    /**
127     * Try to resolve given conflicts. For each conflicting variable it tries to find a 
128     * value with no conflict that is compatible with some other assignment
129     * of the other conflicting variables. 
130     * @param solution current solution
131     * @param total original value of the current solution
132     * @param assignments re-assignments to be made
133     * @param conflicts list of conflicts to resolve
134     * @param index index in the list of conflicts
135     * @return value of the modified solution, null if cannot be resolved
136     */
137    public Double resolve(Solution<V, T> solution, double total, long startTime, Map<V, T> assignments, List<T> conflicts, int index) {
138        if (index == conflicts.size()) return solution.getModel().getTotalValue() - total;
139        T conflict = conflicts.get(index);
140        V variable = conflict.variable();
141        
142        List<T> values = variable.values();
143        if (values.isEmpty()) return null;
144        
145        int valIdx = ToolBox.random(values.size());
146        int attempts = 0;
147        for (int i = 0; i < values.size(); i++) {
148            T value = values.get((i + valIdx) % values.size());
149            if (value.equals(conflict) || solution.getModel().inConflict(value)) continue;
150            
151            variable.assign(solution.getIteration(), value);
152            Double v = resolve(solution, total, startTime, assignments, conflicts, 1 + index);
153            variable.unassign(solution.getIteration());
154            attempts ++;
155            
156            if (v != null && (!iHC || v <= 0)) {
157                assignments.put(variable, value);
158                return v;
159            }
160            if (attempts >= iMaxAttempts || isTimeLimitReached(startTime)) break;
161        }
162            
163        return null;
164    }
165    
166    public class SwapNeighbour extends Neighbour<V, T> {
167        private double iValue = 0;
168        private Collection<T> iAssignments = null;
169
170        public SwapNeighbour(Collection<T> assignments, double value) {
171            iAssignments = assignments; iValue = value;
172        }
173
174        @Override
175        public double value() {
176            return iValue;
177        }
178
179        @Override
180        public void assign(long iteration) {
181            for (T placement: iAssignments)
182                if (placement.variable().getAssignment() != null)
183                    placement.variable().unassign(iteration);
184            for (T placement: iAssignments)
185                placement.variable().assign(iteration, placement);
186        }
187
188        @Override
189        public String toString() {
190            StringBuffer sb = new StringBuffer("Swap{" + iValue + ": ");
191            for (Iterator<T> i = iAssignments.iterator(); i.hasNext(); ) {
192                T p = i.next();
193                sb.append("\n    " + p.variable().getName() + " " + p.getName() + (i.hasNext() ? "," : ""));
194            }
195            sb.append("}");
196            return sb.toString();
197        }
198    }
199}