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