001package org.cpsolver.ifs.solver; 002 003import java.util.ArrayList; 004import java.util.HashMap; 005import java.util.List; 006import java.util.Map; 007import java.util.concurrent.locks.Lock; 008 009import org.cpsolver.ifs.assignment.Assignment; 010import org.cpsolver.ifs.assignment.DefaultParallelAssignment; 011import org.cpsolver.ifs.assignment.DefaultSingleAssignment; 012import org.cpsolver.ifs.assignment.InheritedAssignment; 013import org.cpsolver.ifs.model.Model; 014import org.cpsolver.ifs.model.Neighbour; 015import org.cpsolver.ifs.model.Value; 016import org.cpsolver.ifs.model.Variable; 017import org.cpsolver.ifs.solution.Solution; 018import org.cpsolver.ifs.solution.SolutionListener; 019import org.cpsolver.ifs.util.DataProperties; 020import org.cpsolver.ifs.util.JProf; 021import org.cpsolver.ifs.util.Progress; 022import org.cpsolver.ifs.util.ToolBox; 023 024 025/** 026 * Multi-threaded solver. Instead of one, a given number of solver threads are created 027 * (as defined by Parallel.NrSolvers property) and started in parallel. Each thread 028 * works with its own assignment {@link DefaultParallelAssignment}, but the best solution 029 * is shared among all of them.<br> 030 * <br> 031 * When {@link DefaultSingleAssignment} is given to the solver, only one solution is used. 032 * A neighbour is assigned to this (shared) solution when it does not create any conflicts 033 * outside of {@link Neighbour#assignments()}. 034 * 035 * @see Solver 036 * 037 * @version IFS 1.3 (Iterative Forward Search)<br> 038 * Copyright (C) 2014 Tomas Muller<br> 039 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 040 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 041 * <br> 042 * This library is free software; you can redistribute it and/or modify 043 * it under the terms of the GNU Lesser General Public License as 044 * published by the Free Software Foundation; either version 3 of the 045 * License, or (at your option) any later version. <br> 046 * <br> 047 * This library is distributed in the hope that it will be useful, but 048 * WITHOUT ANY WARRANTY; without even the implied warranty of 049 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 050 * Lesser General Public License for more details. <br> 051 * <br> 052 * You should have received a copy of the GNU Lesser General Public 053 * License along with this library; if not see <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>. 054 * 055 * @param <V> Variable 056 * @param <T> Value 057 **/ 058public class ParallelSolver<V extends Variable<V, T>, T extends Value<V, T>> extends Solver<V, T> { 059 private SynchronizationThread iSynchronizationThread = null; 060 private int iNrFinished = 0; 061 062 public ParallelSolver(DataProperties properties) { 063 super(properties); 064 } 065 066 /** Starts solver */ 067 @Override 068 public void start() { 069 int nrSolvers = Math.abs(getProperties().getPropertyInt("Parallel.NrSolvers", 4)); 070 if (nrSolvers == 1) { 071 super.start(); 072 } else { 073 iSynchronizationThread = new SynchronizationThread(nrSolvers); 074 iSynchronizationThread.setPriority(THREAD_PRIORITY); 075 iSynchronizationThread.start(); 076 } 077 } 078 079 /** Returns solver's thread */ 080 @Override 081 public Thread getSolverThread() { 082 return iSynchronizationThread != null ? iSynchronizationThread : super.getSolverThread(); 083 } 084 085 /** Sets initial solution */ 086 @Override 087 public void setInitalSolution(Model<V, T> model) { 088 int nrSolvers = Math.abs(getProperties().getPropertyInt("Parallel.NrSolvers", 4)); 089 boolean updateMasterSolution = getProperties().getPropertyBoolean("Parallel.UpdateMasterSolution", false); 090 setInitalSolution(new Solution<V, T>(model, nrSolvers > 1 ? new DefaultParallelAssignment<V, T>(updateMasterSolution ? 1 : 0) : new DefaultSingleAssignment<V, T>(), 0, 0)); 091 } 092 093 /** 094 * Return a working (parallel) solution that contributed to the best solution last. 095 * @return working solution 096 */ 097 protected Solution<V, T> getWorkingSolution() { 098 if (iSynchronizationThread != null && !hasSingleSolution()) { 099 int idx = currentSolution().getBestIndex(); 100 if (idx < 0) idx = 0; // take the first thread solution if there was no best solution saved yet 101 if (idx < iSynchronizationThread.iSolvers.size()) 102 return iSynchronizationThread.iSolvers.get(idx).iSolution; 103 } 104 return currentSolution(); 105 } 106 107 /** 108 * Synchronization thread 109 */ 110 protected class SynchronizationThread extends Thread { 111 private int iNrSolvers; 112 private List<SolverThread> iSolvers = new ArrayList<SolverThread>(); 113 114 SynchronizationThread(int nrSolvers) { 115 iNrSolvers = nrSolvers; 116 } 117 118 @Override 119 public void run() { 120 iStop = false; 121 iNrFinished = 0; 122 setName("SolverSync"); 123 124 // Initialization 125 iProgress = Progress.getInstance(currentSolution().getModel()); 126 iProgress.setStatus("Solving problem ..."); 127 iProgress.setPhase("Initializing solver"); 128 initSolver(); 129 onStart(); 130 131 double startTime = JProf.currentTimeSec(); 132 if (isUpdateProgress()) { 133 if (currentSolution().getBestInfo() == null) { 134 iProgress.setPhase("Searching for initial solution ...", currentSolution().getModel().variables().size()); 135 } else { 136 iProgress.setPhase("Improving found solution ..."); 137 } 138 } 139 sLogger.info("Initial solution:" + ToolBox.dict2string(currentSolution().getInfo(), 2)); 140 if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= currentSolution().getAssignment().nrUnassignedVariables(currentSolution().getModel())) && (currentSolution().getBestInfo() == null || getSolutionComparator().isBetterThanBestSolution(currentSolution()))) { 141 if (currentSolution().getAssignment().nrAssignedVariables() == currentSolution().getModel().variables().size()) 142 sLogger.info("Complete solution " + ToolBox.dict2string(currentSolution().getInfo(), 1) + " was found."); 143 currentSolution().saveBest(); 144 } 145 146 if (currentSolution().getModel().variables().isEmpty()) { 147 iProgress.error("Nothing to solve."); 148 iStop = true; 149 } 150 151 if (!iStop) { 152 for (int i = 1; i <= iNrSolvers; i++) { 153 SolverThread thread = new SolverThread(i, startTime); 154 thread.setPriority(THREAD_PRIORITY); 155 thread.setName("Solver-" + i); 156 thread.start(); 157 iSolvers.add(thread); 158 } 159 } 160 161 int timeout = getProperties().getPropertyInt("Termination.TimeOut", 1800); 162 double start = JProf.currentTimeSec(); 163 while (!iStop && iNrFinished < iNrSolvers) { 164 try { 165 Thread.sleep(1000); 166 double time = JProf.currentTimeSec() - start; 167 168 // Increment progress bar 169 if (isUpdateProgress()) { 170 if (currentSolution().getBestInfo() != null && currentSolution().getModel().getBestUnassignedVariables() == 0) { 171 if (!"Improving found solution ...".equals(iProgress.getPhase())) 172 iProgress.setPhase("Improving found solution ..."); 173 iProgress.setProgress(Math.min(100, (int)Math.round(100 * time / timeout))); 174 } else if (currentSolution().getModel().getBestUnassignedVariables() > 0 && (currentSolution().getModel().countVariables() - currentSolution().getModel().getBestUnassignedVariables() > iProgress.getProgress())) { 175 iProgress.setProgress(currentSolution().getModel().countVariables() - currentSolution().getModel().getBestUnassignedVariables()); 176 } else if (iSolvers.get(0).iAssignment.nrAssignedVariables() > iProgress.getProgress()) { 177 iProgress.setProgress(iSolvers.get(0).iAssignment.nrAssignedVariables()); 178 } 179 } 180 } catch (InterruptedException e) {} 181 } 182 183 boolean stop = iStop; iStop = true; 184 for (SolverThread thread: iSolvers) { 185 try { 186 thread.join(); 187 } catch (InterruptedException e) {} 188 } 189 190 // Finalization 191 iLastSolution = iCurrentSolution; 192 193 iProgress.setPhase("Done", 1); 194 iProgress.incProgress(); 195 196 iSynchronizationThread = null; 197 if (stop) { 198 sLogger.debug("Solver stopped."); 199 iProgress.setStatus("Solver stopped."); 200 onStop(); 201 } else { 202 sLogger.debug("Solver done."); 203 iProgress.setStatus("Solver done."); 204 onFinish(); 205 } 206 } 207 } 208 209 /** 210 * Create a solution that is to be used by a solver thread of the given index 211 * @param index solver thread index 212 * @return new solution to work with 213 */ 214 protected Solution<V, T> createParallelSolution(int index) { 215 Model<V, T> model = iCurrentSolution.getModel(); 216 Assignment<V, T> assignment = new DefaultParallelAssignment<V, T>(index, model, iCurrentSolution.getAssignment()); 217 model.createAssignmentContexts(assignment, true); 218 Solution<V, T> solution = new Solution<V, T>(model, assignment); 219 for (SolutionListener<V, T> listener: iCurrentSolution.getSolutionListeners()) 220 solution.addSolutionListener(listener); 221 return solution; 222 } 223 224 /** 225 * Returns true if the solver works only with one solution (regardless the number of threads it is using) 226 * @return true if the current solution is {@link DefaultSingleAssignment} 227 */ 228 @Override 229 public boolean hasSingleSolution() { 230 return iCurrentSolution.getAssignment() instanceof DefaultSingleAssignment; 231 } 232 233 /** 234 * Solver thread 235 */ 236 protected class SolverThread extends Thread { 237 private double iStartTime; 238 private int iIndex; 239 private boolean iSingle; 240 private Model<V, T> iModel; 241 private Solution<V, T> iSolution; 242 private Assignment<V, T> iAssignment; 243 244 public SolverThread(int index, double startTime) { 245 iIndex = index; 246 iStartTime = startTime; 247 iSingle = hasSingleSolution(); 248 iModel = iCurrentSolution.getModel(); 249 iSolution = (iSingle || iCurrentSolution.getAssignment().getIndex() == index ? iCurrentSolution : createParallelSolution(iIndex)); 250 iAssignment = iSolution.getAssignment(); 251 } 252 253 @Override 254 public void run() { 255 try { 256 while (!iStop) { 257 // Break if cannot continue 258 if (!getTerminationCondition().canContinue(iSolution)) break; 259 260 // Create a sub-solution if needed 261 Solution<V, T> current = (iSingle ? new Solution<V, T>(iModel, new InheritedAssignment<V, T>(iSolution.getAssignment()), iSolution.getIteration(), iSolution.getTime()) : iSolution); 262 263 // Neighbour selection 264 Neighbour<V, T> neighbour = null; 265 try { 266 neighbour = getNeighbourSelection().selectNeighbour(current); 267 } catch (Exception e) { 268 sLogger.warn("Failed to select a neighbour: " + (e.getMessage() == null ? e.getClass().getSimpleName() : e.getMessage())); 269 } 270 for (SolverListener<V, T> listener : iSolverListeners) { 271 if (!listener.neighbourSelected(iAssignment, iSolution.getIteration(), neighbour)) { 272 neighbour = null; 273 continue; 274 } 275 } 276 277 double time = JProf.currentTimeSec() - iStartTime; 278 if (neighbour == null) { 279 sLogger.debug("No neighbour selected."); 280 // still update the solution (increase iteration etc.) 281 iSolution.update(time, false); 282 continue; 283 } 284 285 if (iSingle) { 286 Map<V, T> assignments = null; 287 try { 288 assignments = neighbour.assignments(); 289 } catch (UnsupportedOperationException e) { 290 sLogger.error("Failed to enumerate " + neighbour.getClass().getSimpleName(), e); 291 } 292 if (assignments == null) { 293 sLogger.debug("No assignments returned."); 294 // still update the solution (increase iteration etc.) 295 iSolution.update(time, false); 296 continue; 297 } 298 299 // Assign selected value to the selected variable 300 Lock lock = iSolution.getLock().writeLock(); 301 lock.lock(); 302 try { 303 Map<V, T> undo = new HashMap<V, T>(); 304 for (V var: assignments.keySet()) 305 undo.put(var, iSolution.getAssignment().unassign(iSolution.getIteration(), var)); 306 boolean fail = false; 307 for (T val: assignments.values()) { 308 if (val == null) continue; 309 if (iModel.inConflict(iSolution.getAssignment(), val)) { 310 fail = true; break; 311 } 312 iSolution.getAssignment().assign(iSolution.getIteration(), val); 313 } 314 if (fail) { 315 for (V var: undo.keySet()) 316 iSolution.getAssignment().unassign(iSolution.getIteration(), var); 317 for (T val: undo.values()) 318 if (val != null) 319 iSolution.getAssignment().assign(iSolution.getIteration(), val); 320 } 321 iSolution.update(time, !fail); 322 if (fail) { 323 for (SolverListener<V, T> listener : iSolverListeners) 324 listener.neighbourFailed(current.getAssignment(), iSolution.getIteration(), neighbour); 325 continue; 326 } 327 328 onAssigned(iStartTime, iSolution); 329 330 if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iSolution.getAssignment().nrUnassignedVariables(iModel)) && getSolutionComparator().isBetterThanBestSolution(iSolution)) { 331 iSolution.saveBest(); 332 } 333 } finally { 334 lock.unlock(); 335 } 336 } else { 337 // Assign selected value to the selected variable 338 Lock lock = iSolution.getLock().writeLock(); 339 lock.lock(); 340 try { 341 neighbour.assign(iAssignment, iSolution.getIteration()); 342 iSolution.update(time); 343 } finally { 344 lock.unlock(); 345 } 346 347 onAssigned(iStartTime, iSolution); 348 349 if (iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iAssignment.nrUnassignedVariables(iModel)) 350 iSolution.saveBestIfImproving(currentSolution(), getSolutionComparator()); 351 } 352 } 353 354 } catch (Exception ex) { 355 sLogger.error(ex.getMessage(), ex); 356 iProgress.fatal(getName() + " failed, reason:" + ex.getMessage(), ex); 357 if (iIndex == 0) { 358 iProgress.setStatus("Solver failed."); 359 onFailure(); 360 } 361 } 362 Lock lock = currentSolution().getLock().writeLock(); 363 lock.lock(); 364 try { 365 iNrFinished ++; 366 } finally { 367 lock.unlock(); 368 } 369 } 370 371 } 372}