001package org.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;
010import java.util.concurrent.locks.Lock;
011
012import org.cpsolver.ifs.assignment.Assignment;
013import org.cpsolver.ifs.heuristics.NeighbourSelection;
014import org.cpsolver.ifs.model.Model;
015import org.cpsolver.ifs.model.Neighbour;
016import org.cpsolver.ifs.model.SimpleNeighbour;
017import org.cpsolver.ifs.model.Value;
018import org.cpsolver.ifs.model.Variable;
019import org.cpsolver.ifs.solution.Solution;
020import org.cpsolver.ifs.solver.Solver;
021import org.cpsolver.ifs.util.DataProperties;
022import org.cpsolver.ifs.util.JProf;
023import org.cpsolver.ifs.util.ToolBox;
024
025
026/**
027 * Try to assign a variable with a new value. A variable is selected randomly, a
028 * different value is randomly selected for the variable -- the variable is
029 * assigned with the new value.  If there is a conflict, it tries to resolve these
030 * conflicts by assigning conflicting variables to other values as well.
031 * <br>
032 * 
033 * @version IFS 1.3 (Iterative Forward Search)<br>
034 *          Copyright (C) 2014 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
050 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
051 * @param <V> Variable
052 * @param <T> Value
053 */
054public class RandomSwapMove<V extends Variable<V, T>, T extends Value<V, T>> implements NeighbourSelection<V, T>, HillClimberSelection {
055    protected int iMaxAttempts = 3;
056    protected boolean iHC = false;
057    protected int iTimeLimit = 200;
058
059    public RandomSwapMove(DataProperties config) {
060        iMaxAttempts = config.getPropertyInt("RandomSwap.MaxAttempts", iMaxAttempts);
061        iTimeLimit = config.getPropertyInt("RandomSwap.TimeLimit", iTimeLimit);
062    }
063    
064    @Override
065    public void setHcMode(boolean hcMode) {
066        iHC = hcMode;
067    }
068
069    @Override
070    public void init(Solver<V, T> solver) {
071    }
072
073    @Override
074    public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) {
075        Model<V, T> model = solution.getModel();
076        Assignment<V, T> assignment = solution.getAssignment();
077        double total = model.getTotalValue(assignment);
078        int varIdx = ToolBox.random(model.variables().size());
079        for (int i = 0; i < model.variables().size(); i++) {
080            V variable = model.variables().get((i + varIdx) % model.variables().size());
081            List<T> values = variable.values(solution.getAssignment());
082            if (values.isEmpty()) continue;
083            int valIdx = ToolBox.random(values.size());
084            T old = variable.getAssignment(assignment);
085            
086            Lock lock = solution.getLock().writeLock();
087            lock.lock();
088            try {
089                int attempts = 0;
090                long startTime = JProf.currentTimeMillis();
091                for (int j = 0; j < values.size(); j++) {
092                    T value = values.get((j + valIdx) % values.size());
093                    if (value.equals(old)) continue;
094                    
095                    Set<T> conflicts = model.conflictValues(assignment, value);
096                    if (conflicts.contains(value)) continue;
097                    if (conflicts.isEmpty()) {
098                        SimpleNeighbour<V, T> n = new SimpleNeighbour<V, T>(variable, value);
099                        if (!iHC || n.value(assignment) <= 0) return n;
100                        else continue;
101                    }
102                    
103                    Map<V, T> assignments = new HashMap<V, T>();
104                    assignments.put(variable, value);
105                    
106                    for (T conflict: conflicts)
107                        assignment.unassign(solution.getIteration(), conflict.variable());
108                    assignment.assign(solution.getIteration(), value);
109                    
110                    Double v = resolve(solution, total, startTime, assignments, new ArrayList<T>(conflicts), 0);
111                    if (!conflicts.isEmpty())
112                        attempts ++;
113                    
114                    assignment.unassign(solution.getIteration(), variable);
115                    for (T conflict: conflicts)
116                        assignment.assign(solution.getIteration(), conflict);
117                    if (old != null) assignment.assign(solution.getIteration(), old);
118                    
119                    if (v != null)
120                        return new SwapNeighbour(assignments.values(), v);
121                    
122                    if (attempts >= iMaxAttempts) break;
123                }
124            } finally {
125                lock.unlock();
126            }
127        }
128        return null;
129    }
130    
131    /**
132     * Return true if the time limit was reached, number of attempts are limited to 1 in such a case.
133     * @param startTime start time
134     * @return true if the given time limit was reached
135     */
136    protected boolean isTimeLimitReached(long startTime) {
137        return iTimeLimit > 0 && (JProf.currentTimeMillis() - startTime) > iTimeLimit;
138    }
139    
140    /**
141     * Try to resolve given conflicts. For each conflicting variable it tries to find a 
142     * value with no conflict that is compatible with some other assignment
143     * of the other conflicting variables. 
144     * @param solution current solution
145     * @param total original value of the current solution
146     * @param startTime starting time
147     * @param assignments re-assignments to be made
148     * @param conflicts list of conflicts to resolve
149     * @param index index in the list of conflicts
150     * @return value of the modified solution, null if cannot be resolved
151     */
152    protected Double resolve(Solution<V, T> solution, double total, long startTime, Map<V, T> assignments, List<T> conflicts, int index) {
153        Assignment<V, T> assignment = solution.getAssignment();
154
155        if (index == conflicts.size()) return solution.getModel().getTotalValue(assignment) - total;
156        T conflict = conflicts.get(index);
157        V variable = conflict.variable();
158        
159        List<T> values = variable.values(solution.getAssignment());
160        if (values.isEmpty()) return null;
161        
162        int valIdx = ToolBox.random(values.size());
163        int attempts = 0;
164        for (int i = 0; i < values.size(); i++) {
165            T value = values.get((i + valIdx) % values.size());
166            if (value.equals(conflict) || solution.getModel().inConflict(assignment, value)) continue;
167            
168            assignment.assign(solution.getIteration(), value);
169            Double v = resolve(solution, total, startTime, assignments, conflicts, 1 + index);
170            assignment.unassign(solution.getIteration(), variable);
171            attempts ++;
172            
173            if (v != null && (!iHC || v <= 0)) {
174                assignments.put(variable, value);
175                return v;
176            }
177            if (attempts >= iMaxAttempts || isTimeLimitReached(startTime)) break;
178        }
179            
180        return null;
181    }
182    
183    public class SwapNeighbour implements Neighbour<V, T> {
184        private double iValue = 0;
185        private Collection<T> iAssignments = null;
186
187        public SwapNeighbour(Collection<T> assignments, double value) {
188            iAssignments = assignments; iValue = value;
189        }
190
191        @Override
192        public double value(Assignment<V, T> assignment) {
193            return iValue;
194        }
195
196        @Override
197        public void assign(Assignment<V, T> assignment, long iteration) {
198            for (T value: iAssignments)
199                assignment.unassign(iteration, value.variable(), value);
200            for (T value: iAssignments)
201                assignment.assign(iteration, value);
202        }
203
204        @Override
205        public String toString() {
206            StringBuffer sb = new StringBuffer("Swap{" + iValue + ": ");
207            for (Iterator<T> i = iAssignments.iterator(); i.hasNext(); ) {
208                T p = i.next();
209                sb.append("\n    " + p.variable().getName() + " " + p.getName() + (i.hasNext() ? "," : ""));
210            }
211            sb.append("}");
212            return sb.toString();
213        }
214
215        @Override
216        public Map<V, T> assignments() {
217            Map<V, T> ret = new HashMap<V, T>();
218            for (T value: iAssignments)
219                ret.put(value.variable(), value);
220            return ret;
221        }
222    }
223}