001package org.cpsolver.ifs.solver; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.HashMap; 006import java.util.List; 007import java.util.Map; 008import java.util.concurrent.ArrayBlockingQueue; 009import java.util.concurrent.BlockingQueue; 010import java.util.concurrent.TimeUnit; 011import java.util.concurrent.locks.Lock; 012 013import org.cpsolver.ifs.assignment.Assignment; 014import org.cpsolver.ifs.assignment.DefaultParallelAssignment; 015import org.cpsolver.ifs.assignment.DefaultSingleAssignment; 016import org.cpsolver.ifs.assignment.context.CanHoldContext; 017import org.cpsolver.ifs.model.LazyNeighbour; 018import org.cpsolver.ifs.model.LazyNeighbour.LazyNeighbourAcceptanceCriterion; 019import org.cpsolver.ifs.model.Model; 020import org.cpsolver.ifs.model.Neighbour; 021import org.cpsolver.ifs.model.Value; 022import org.cpsolver.ifs.model.Variable; 023import org.cpsolver.ifs.solution.Solution; 024import org.cpsolver.ifs.solution.SolutionListener; 025import org.cpsolver.ifs.util.DataProperties; 026import org.cpsolver.ifs.util.JProf; 027import org.cpsolver.ifs.util.Progress; 028import org.cpsolver.ifs.util.ToolBox; 029 030 031/** 032 * Multi-threaded solver. Instead of one, a given number of solver threads are created 033 * (as defined by Parallel.NrSolvers property) and started in parallel. Each thread 034 * works with its own assignment {@link DefaultParallelAssignment}, but the best solution 035 * is shared among all of them.<br> 036 * <br> 037 * When {@link DefaultSingleAssignment} is given to the solver, only one solution is used. 038 * A neighbour is assigned to this (shared) solution when it does not create any conflicts 039 * outside of {@link Neighbour#assignments()}. 040 * 041 * @see Solver 042 * 043 * @version IFS 1.3 (Iterative Forward Search)<br> 044 * Copyright (C) 2014 Tomas Muller<br> 045 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 046 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 047 * <br> 048 * This library is free software; you can redistribute it and/or modify 049 * it under the terms of the GNU Lesser General Public License as 050 * published by the Free Software Foundation; either version 3 of the 051 * License, or (at your option) any later version. <br> 052 * <br> 053 * This library is distributed in the hope that it will be useful, but 054 * WITHOUT ANY WARRANTY; without even the implied warranty of 055 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 056 * Lesser General Public License for more details. <br> 057 * <br> 058 * You should have received a copy of the GNU Lesser General Public 059 * License along with this library; if not see <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>. 060 * 061 * @param <V> Variable 062 * @param <T> Value 063 **/ 064public class ParallelSolver<V extends Variable<V, T>, T extends Value<V, T>> extends Solver<V, T> { 065 private SynchronizationThread iSynchronizationThread = null; 066 private int iNrFinished = 0; 067 068 public ParallelSolver(DataProperties properties) { 069 super(properties); 070 } 071 072 /** Starts solver */ 073 @Override 074 public void start() { 075 int nrSolvers = Math.min(Math.abs(getProperties().getPropertyInt("Parallel.NrSolvers", 4)), CanHoldContext.sMaxSize - 1); 076 if (nrSolvers == 1) { 077 super.start(); 078 } else { 079 iSynchronizationThread = new SynchronizationThread(nrSolvers); 080 iSynchronizationThread.setPriority(THREAD_PRIORITY); 081 iSynchronizationThread.start(); 082 } 083 } 084 085 /** Returns solver's thread */ 086 @Override 087 public Thread getSolverThread() { 088 return iSynchronizationThread != null ? iSynchronizationThread : super.getSolverThread(); 089 } 090 091 /** Sets initial solution */ 092 @Override 093 public void setInitalSolution(Model<V, T> model) { 094 int nrSolvers = Math.min(Math.abs(getProperties().getPropertyInt("Parallel.NrSolvers", 4)), CanHoldContext.sMaxSize - 1); 095 boolean updateMasterSolution = getProperties().getPropertyBoolean("Parallel.UpdateMasterSolution", true); 096 setInitalSolution(new Solution<V, T>(model, nrSolvers > 1 ? new DefaultParallelAssignment<V, T>(updateMasterSolution ? 1 : 0) : new DefaultSingleAssignment<V, T>(), 0, 0)); 097 } 098 099 /** 100 * Return a working (parallel) solution that contributed to the best solution last. 101 * @return working solution 102 */ 103 protected Solution<V, T> getWorkingSolution() { 104 if (iSynchronizationThread != null && !hasSingleSolution()) { 105 int idx = currentSolution().getBestIndex(); 106 if (idx < 0) idx = 0; // take the first thread solution if there was no best solution saved yet 107 if (idx < iSynchronizationThread.iSolvers.size()) 108 return iSynchronizationThread.iSolvers.get(idx).iSolution; 109 } 110 return currentSolution(); 111 } 112 113 /** 114 * Synchronization thread 115 */ 116 protected class SynchronizationThread extends Thread { 117 private int iNrSolvers; 118 private List<SolverThread> iSolvers = new ArrayList<SolverThread>(); 119 private AssignmentThread iAssignmentThread = null; 120 121 SynchronizationThread(int nrSolvers) { 122 iNrSolvers = nrSolvers; 123 } 124 125 @Override 126 public void run() { 127 iStop = false; 128 iNrFinished = 0; 129 setName("SolverSync"); 130 131 // Initialization 132 iProgress = Progress.getInstance(currentSolution().getModel()); 133 iProgress.setStatus("Solving problem ..."); 134 iProgress.setPhase("Initializing solver"); 135 initSolver(); 136 onStart(); 137 138 if (isUpdateProgress()) { 139 if (currentSolution().getBestInfo() == null) { 140 iProgress.setPhase("Searching for initial solution ...", currentSolution().getModel().variables().size()); 141 } else { 142 iProgress.setPhase("Improving found solution ..."); 143 } 144 } 145 sLogger.info("Initial solution:" + ToolBox.dict2string(currentSolution().getInfo(), 2)); 146 if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= currentSolution().getAssignment().nrUnassignedVariables(currentSolution().getModel())) && (currentSolution().getBestInfo() == null || getSolutionComparator().isBetterThanBestSolution(currentSolution()))) { 147 if (currentSolution().getAssignment().nrAssignedVariables() == currentSolution().getModel().variables().size()) 148 sLogger.info("Complete solution " + ToolBox.dict2string(currentSolution().getInfo(), 1) + " was found."); 149 currentSolution().saveBest(); 150 } 151 152 if (currentSolution().getModel().variables().isEmpty()) { 153 iProgress.error("Nothing to solve."); 154 iStop = true; 155 } 156 157 BlockingQueue<Neighbour<V, T>> queue = null; 158 if (hasSingleSolution() && iNrSolvers > 1 && getProperties().getPropertyBoolean("ParallelSolver.SingleSolutionQueue", false)) 159 queue = new ArrayBlockingQueue<Neighbour<V, T>>(2 * iNrSolvers); 160 161 if (!iStop) { 162 for (int i = 1; i <= iNrSolvers; i++) { 163 SolverThread thread = new SolverThread(i, queue); 164 thread.setPriority(THREAD_PRIORITY); 165 thread.setName("Solver-" + i); 166 thread.start(); 167 iSolvers.add(thread); 168 } 169 } 170 171 if (queue != null) { 172 iAssignmentThread = new AssignmentThread(queue); 173 iAssignmentThread.start(); 174 } 175 176 int timeout = getProperties().getPropertyInt("Termination.TimeOut", 1800); 177 double start = JProf.currentTimeSec(); 178 while (!iStop && iNrFinished < iNrSolvers) { 179 try { 180 Thread.sleep(1000); 181 double time = JProf.currentTimeSec() - start; 182 183 // Increment progress bar 184 if (isUpdateProgress()) { 185 if (currentSolution().getBestInfo() != null && currentSolution().getModel().getBestUnassignedVariables() == 0) { 186 if (!"Improving found solution ...".equals(iProgress.getPhase())) 187 iProgress.setPhase("Improving found solution ..."); 188 iProgress.setProgress(Math.min(100, (int)Math.round(100 * time / timeout))); 189 } else if (currentSolution().getModel().getBestUnassignedVariables() > 0 && (currentSolution().getModel().countVariables() - currentSolution().getModel().getBestUnassignedVariables() > iProgress.getProgress())) { 190 iProgress.setProgress(currentSolution().getModel().countVariables() - currentSolution().getModel().getBestUnassignedVariables()); 191 } else if (iSolvers.get(0).iAssignment.nrAssignedVariables() > iProgress.getProgress()) { 192 iProgress.setProgress(iSolvers.get(0).iAssignment.nrAssignedVariables()); 193 } 194 } 195 } catch (InterruptedException e) {} 196 } 197 198 boolean stop = iStop; iStop = true; 199 for (SolverThread thread: iSolvers) { 200 try { 201 thread.join(); 202 } catch (InterruptedException e) {} 203 } 204 if (iAssignmentThread != null) { 205 try { 206 iAssignmentThread.join(); 207 } catch (InterruptedException e) {} 208 } 209 210 // Finalization 211 iLastSolution = iCurrentSolution; 212 213 iProgress.setPhase("Done", 1); 214 iProgress.incProgress(); 215 216 iSynchronizationThread = null; 217 if (stop) { 218 sLogger.debug("Solver stopped."); 219 iProgress.setStatus("Solver stopped."); 220 onStop(); 221 } else { 222 sLogger.debug("Solver done."); 223 iProgress.setStatus("Solver done."); 224 onFinish(); 225 } 226 } 227 } 228 229 /** 230 * Create a solution that is to be used by a solver thread of the given index 231 * @param index solver thread index 232 * @return new solution to work with 233 */ 234 protected Solution<V, T> createParallelSolution(int index) { 235 Model<V, T> model = iCurrentSolution.getModel(); 236 Assignment<V, T> assignment = new DefaultParallelAssignment<V, T>(index, model, iCurrentSolution.getAssignment()); 237 model.createAssignmentContexts(assignment, true); 238 Solution<V, T> solution = new Solution<V, T>(model, assignment); 239 for (SolutionListener<V, T> listener: iCurrentSolution.getSolutionListeners()) 240 solution.addSolutionListener(listener); 241 return solution; 242 } 243 244 /** 245 * Returns true if the solver works only with one solution (regardless the number of threads it is using) 246 * @return true if the current solution is {@link DefaultSingleAssignment} 247 */ 248 @Override 249 public boolean hasSingleSolution() { 250 return iCurrentSolution.getAssignment() instanceof DefaultSingleAssignment; 251 } 252 253 /** 254 * Solver thread 255 */ 256 protected class SolverThread extends Thread { 257 private double iStartTime; 258 private int iIndex; 259 private boolean iSingle; 260 private Model<V, T> iModel; 261 private Solution<V, T> iSolution; 262 private Assignment<V, T> iAssignment; 263 private BlockingQueue<Neighbour<V, T>> iQueue; 264 265 public SolverThread(int index, BlockingQueue<Neighbour<V, T>> queue) { 266 iIndex = index; 267 iSingle = hasSingleSolution(); 268 iModel = iCurrentSolution.getModel(); 269 iSolution = (iSingle || iCurrentSolution.getAssignment().getIndex() == index ? iCurrentSolution : createParallelSolution(iIndex)); 270 iAssignment = iSolution.getAssignment(); 271 iQueue = queue; 272 } 273 274 @Override 275 public void run() { 276 iStartTime = JProf.currentTimeSec(); 277 try { 278 boolean neighbourCheck = getProperties().getPropertyBoolean("ParallelSolver.SingleSolutionNeighbourCheck", false); 279 boolean tryLazyFirst = getProperties().getPropertyBoolean("ParallelSolver.SingleSolutionTryLazyFirst", false); 280 281 while (!iStop) { 282 // Break if cannot continue 283 if (!getTerminationCondition().canContinue(iSolution)) break; 284 285 // Create a sub-solution if needed 286 Solution<V, T> current = iSolution; 287 if (iSingle) { 288 current = new Solution<V, T>(iModel, iModel.createInheritedAssignment(iSolution, iIndex), iSolution.getIteration(), iSolution.getTime()); 289 current.addSolutionListener(new SolutionListener<V, T>() { 290 @Override 291 public void solutionUpdated(Solution<V, T> solution) { 292 } 293 294 @Override 295 public void getInfo(Solution<V, T> solution, Map<String, String> info) { 296 } 297 298 @Override 299 public void getInfo(Solution<V, T> solution, Map<String, String> info, Collection<V> variables) { 300 } 301 302 @Override 303 public void bestCleared(Solution<V, T> solution) { 304 } 305 306 @Override 307 public void bestSaved(Solution<V, T> solution) { 308 } 309 310 @Override 311 public void bestRestored(Solution<V, T> solution) { 312 iSolution.restoreBest(); 313 } 314 }); 315 } 316 317 // Neighbour selection 318 Neighbour<V, T> neighbour = null; 319 try { 320 neighbour = getNeighbourSelection().selectNeighbour(current); 321 } catch (Exception e) { 322 sLogger.warn("Failed to select a neighbour: " + (e.getMessage() == null ? e.getClass().getSimpleName() : e.getMessage())); 323 } 324 for (SolverListener<V, T> listener : iSolverListeners) { 325 if (!listener.neighbourSelected(iAssignment, iSolution.getIteration(), neighbour)) { 326 neighbour = null; 327 continue; 328 } 329 } 330 331 double time = JProf.currentTimeSec() - iStartTime; 332 if (neighbour == null) { 333 sLogger.debug("No neighbour selected."); 334 // still update the solution (increase iteration etc.) 335 iSolution.update(time, false); 336 continue; 337 } 338 339 if (iSingle) { 340 if (iQueue != null) { 341 do { 342 if (iQueue.offer(neighbour, 1000, TimeUnit.MILLISECONDS)) break; 343 } while (!iStop && getTerminationCondition().canContinue(iSolution)); 344 continue; 345 } 346 347 Map<V, T> assignments = null; 348 try { 349 assignments = neighbour.assignments(); 350 } catch (UnsupportedOperationException e) { 351 sLogger.error("Failed to enumerate " + neighbour.getClass().getSimpleName(), e); 352 } 353 if (assignments == null) { 354 sLogger.debug("No assignments returned."); 355 // still update the solution (increase iteration etc.) 356 iSolution.update(time, false); 357 continue; 358 } 359 360 if (tryLazyFirst && neighbour instanceof LazyNeighbour) { 361 LazyNeighbour<V, T> lazy = (LazyNeighbour<V, T>)neighbour; 362 double before = current.getModel().getTotalValue(current.getAssignment()); 363 neighbour.assign(current.getAssignment(), current.getIteration()); 364 double after = current.getModel().getTotalValue(current.getAssignment()); 365 if (!lazy.getAcceptanceCriterion().accept(current.getAssignment(), lazy, after - before)) 366 continue; 367 } 368 369 // Assign selected value to the selected variable 370 Lock lock = iSolution.getLock().writeLock(); 371 lock.lock(); 372 try { 373 LazyNeighbourAcceptanceCriterion<V,T> lazy = null; 374 double before = 0, value = 0; 375 if (neighbour instanceof LazyNeighbour) { 376 before = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 377 lazy = ((LazyNeighbour<V, T>)neighbour).getAcceptanceCriterion(); 378 } else if (neighbourCheck) { 379 before = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 380 value = neighbour.value(current.getAssignment()); 381 } 382 Map<V, T> undo = new HashMap<V, T>(); 383 for (V var: assignments.keySet()) 384 undo.put(var, iSolution.getAssignment().unassign(iSolution.getIteration(), var)); 385 boolean fail = false; 386 for (T val: assignments.values()) { 387 if (val == null) continue; 388 if (iModel.inConflict(iSolution.getAssignment(), val)) { 389 fail = true; break; 390 } 391 iSolution.getAssignment().assign(iSolution.getIteration(), val); 392 } 393 if (!fail) { 394 if (lazy != null) { 395 double after = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 396 if (!lazy.accept(iSolution.getAssignment(), (LazyNeighbour<V, T>) neighbour, after - before)) 397 fail = true; 398 } else if (neighbourCheck) { 399 double after = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 400 if (before + value < after && before < after && !getSolutionComparator().isBetterThanBestSolution(iSolution)) 401 fail = true; 402 } 403 } 404 if (fail) { 405 for (V var: undo.keySet()) 406 iSolution.getAssignment().unassign(iSolution.getIteration(), var); 407 for (T val: undo.values()) 408 if (val != null) 409 iSolution.getAssignment().assign(iSolution.getIteration(), val); 410 } 411 iSolution.update(time, !fail); 412 if (fail) { 413 for (SolverListener<V, T> listener : iSolverListeners) 414 listener.neighbourFailed(current.getAssignment(), iSolution.getIteration(), neighbour); 415 continue; 416 } 417 418 onAssigned(iStartTime, iSolution); 419 420 if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iSolution.getAssignment().nrUnassignedVariables(iModel)) && getSolutionComparator().isBetterThanBestSolution(iSolution)) { 421 iSolution.saveBest(); 422 } 423 } finally { 424 lock.unlock(); 425 } 426 } else { 427 // Assign selected value to the selected variable 428 Lock lock = iSolution.getLock().writeLock(); 429 lock.lock(); 430 try { 431 neighbour.assign(iAssignment, iSolution.getIteration()); 432 iSolution.update(time, currentSolution()); 433 } finally { 434 lock.unlock(); 435 } 436 437 onAssigned(iStartTime, iSolution); 438 439 if (iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iAssignment.nrUnassignedVariables(iModel)) 440 iSolution.saveBestIfImproving(currentSolution(), getSolutionComparator()); 441 } 442 } 443 444 } catch (Exception ex) { 445 sLogger.error(ex.getMessage(), ex); 446 iProgress.fatal(getName() + " failed, reason:" + ex.getMessage(), ex); 447 if (iIndex == 0) { 448 iProgress.setStatus("Solver failed."); 449 onFailure(); 450 } 451 } 452 Lock lock = currentSolution().getLock().writeLock(); 453 lock.lock(); 454 try { 455 iNrFinished ++; 456 } finally { 457 lock.unlock(); 458 } 459 } 460 461 } 462 463 /** 464 * Solver thread 465 */ 466 protected class AssignmentThread extends Thread { 467 private double iStartTime; 468 private Solution<V, T> iSolution; 469 private BlockingQueue<Neighbour<V, T>> iQueue; 470 471 public AssignmentThread(BlockingQueue<Neighbour<V, T>> queue) { 472 setName("Assignment"); 473 setPriority(1 + THREAD_PRIORITY); 474 iSolution = iCurrentSolution; 475 iQueue = queue; 476 } 477 478 @Override 479 public void run() { 480 iStartTime = JProf.currentTimeSec(); 481 try { 482 boolean neighbourCheck = getProperties().getPropertyBoolean("ParallelSolver.SingleSolutionNeighbourCheck", false); 483 484 while (!iStop) { 485 // Break if cannot continue 486 if (!getTerminationCondition().canContinue(iSolution)) break; 487 488 // Create a sub-solution if needed 489 Neighbour<V, T> neighbour = iQueue.poll(1000, TimeUnit.MILLISECONDS); 490 491 if (neighbour == null) continue; 492 493 double time = JProf.currentTimeSec() - iStartTime; 494 495 Map<V, T> assignments = null; 496 try { 497 assignments = neighbour.assignments(); 498 } catch (UnsupportedOperationException e) { 499 sLogger.error("Failed to enumerate " + neighbour.getClass().getSimpleName(), e); 500 } 501 if (assignments == null) { 502 sLogger.debug("No assignments returned."); 503 // still update the solution (increase iteration etc.) 504 iSolution.update(time, false); 505 continue; 506 } 507 508 // Assign selected value to the selected variable 509 Lock lock = iSolution.getLock().writeLock(); 510 lock.lock(); 511 try { 512 LazyNeighbourAcceptanceCriterion<V,T> lazy = null; 513 double before = 0, value = 0; 514 if (neighbour instanceof LazyNeighbour) { 515 before = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 516 lazy = ((LazyNeighbour<V, T>)neighbour).getAcceptanceCriterion(); 517 } else if (neighbourCheck) { 518 before = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 519 value = neighbour.value(iSolution.getAssignment()); 520 } 521 Map<V, T> undo = new HashMap<V, T>(); 522 for (V var: assignments.keySet()) 523 undo.put(var, iSolution.getAssignment().unassign(iSolution.getIteration(), var)); 524 boolean fail = false; 525 for (T val: assignments.values()) { 526 if (val == null) continue; 527 if (iSolution.getModel().inConflict(iSolution.getAssignment(), val)) { 528 fail = true; break; 529 } 530 iSolution.getAssignment().assign(iSolution.getIteration(), val); 531 } 532 if (!fail) { 533 if (lazy != null) { 534 double after = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 535 if (!lazy.accept(iSolution.getAssignment(), (LazyNeighbour<V, T>) neighbour, after - before)) 536 fail = true; 537 } else if (neighbourCheck) { 538 double after = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 539 if (before + value < after && before < after && !getSolutionComparator().isBetterThanBestSolution(iSolution)) 540 fail = true; 541 } 542 } 543 if (fail) { 544 for (V var: undo.keySet()) 545 iSolution.getAssignment().unassign(iSolution.getIteration(), var); 546 for (T val: undo.values()) 547 if (val != null) 548 iSolution.getAssignment().assign(iSolution.getIteration(), val); 549 } 550 iSolution.update(time, !fail); 551 if (fail) { 552 for (SolverListener<V, T> listener : iSolverListeners) 553 listener.neighbourFailed(iSolution.getAssignment(), iSolution.getIteration(), neighbour); 554 continue; 555 } 556 557 onAssigned(iStartTime, iSolution); 558 559 if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iSolution.getAssignment().nrUnassignedVariables(iSolution.getModel())) && getSolutionComparator().isBetterThanBestSolution(iSolution)) { 560 iSolution.saveBest(); 561 } 562 } finally { 563 lock.unlock(); 564 } 565 } 566 567 } catch (Exception ex) { 568 sLogger.error(ex.getMessage(), ex); 569 iProgress.fatal(getName() + " failed, reason:" + ex.getMessage(), ex); 570 } 571 Lock lock = currentSolution().getLock().writeLock(); 572 lock.lock(); 573 try { 574 iNrFinished ++; 575 } finally { 576 lock.unlock(); 577 } 578 } 579 580 } 581 582}