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