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 if (stop) { 219 sLogger.debug("Solver stopped."); 220 iProgress.setStatus("Solver stopped."); 221 onStop(); 222 } else { 223 sLogger.debug("Solver done."); 224 iProgress.setStatus("Solver done."); 225 onFinish(); 226 } 227 } catch (Exception ex) { 228 sLogger.error(ex.getMessage(), ex); 229 iProgress.fatal("Solver synchronization failed, reason:" + ex.getMessage(), ex); 230 iProgress.setStatus("Solver failed."); 231 onFailure(); 232 } finally { 233 iSynchronizationThread = null; 234 } 235 } 236 } 237 238 /** 239 * Create a solution that is to be used by a solver thread of the given index 240 * @param index solver thread index 241 * @return new solution to work with 242 */ 243 protected Solution<V, T> createParallelSolution(int index) { 244 Model<V, T> model = iCurrentSolution.getModel(); 245 Assignment<V, T> assignment = new DefaultParallelAssignment<V, T>(index, model, iCurrentSolution.getAssignment()); 246 model.createAssignmentContexts(assignment, true); 247 Solution<V, T> solution = new Solution<V, T>(model, assignment); 248 for (SolutionListener<V, T> listener: iCurrentSolution.getSolutionListeners()) 249 solution.addSolutionListener(listener); 250 return solution; 251 } 252 253 /** 254 * Returns true if the solver works only with one solution (regardless the number of threads it is using) 255 * @return true if the current solution is {@link DefaultSingleAssignment} 256 */ 257 @Override 258 public boolean hasSingleSolution() { 259 return iCurrentSolution.getAssignment() instanceof DefaultSingleAssignment; 260 } 261 262 /** 263 * Solver thread 264 */ 265 protected class SolverThread extends Thread { 266 private double iStartTime; 267 private int iIndex; 268 private boolean iSingle; 269 private Model<V, T> iModel; 270 private Solution<V, T> iSolution; 271 private Assignment<V, T> iAssignment; 272 private BlockingQueue<Neighbour<V, T>> iQueue; 273 274 public SolverThread(int index, BlockingQueue<Neighbour<V, T>> queue) { 275 iIndex = index; 276 iSingle = hasSingleSolution(); 277 iModel = iCurrentSolution.getModel(); 278 iSolution = (iSingle || iCurrentSolution.getAssignment().getIndex() == index ? iCurrentSolution : createParallelSolution(iIndex)); 279 iAssignment = iSolution.getAssignment(); 280 iQueue = queue; 281 } 282 283 @Override 284 public void run() { 285 iStartTime = JProf.currentTimeSec(); 286 try { 287 boolean neighbourCheck = getProperties().getPropertyBoolean("ParallelSolver.SingleSolutionNeighbourCheck", false); 288 boolean tryLazyFirst = getProperties().getPropertyBoolean("ParallelSolver.SingleSolutionTryLazyFirst", false); 289 290 while (!iStop) { 291 // Break if cannot continue 292 if (!getTerminationCondition().canContinue(iSolution)) break; 293 294 // Create a sub-solution if needed 295 Solution<V, T> current = iSolution; 296 if (iSingle) { 297 current = new Solution<V, T>(iModel, iModel.createInheritedAssignment(iSolution, iIndex), iSolution.getIteration(), iSolution.getTime()); 298 current.addSolutionListener(new SolutionListener<V, T>() { 299 @Override 300 public void solutionUpdated(Solution<V, T> solution) { 301 } 302 303 @Override 304 public void getInfo(Solution<V, T> solution, Map<String, String> info) { 305 } 306 307 @Override 308 public void getInfo(Solution<V, T> solution, Map<String, String> info, Collection<V> variables) { 309 } 310 311 @Override 312 public void bestCleared(Solution<V, T> solution) { 313 } 314 315 @Override 316 public void bestSaved(Solution<V, T> solution) { 317 } 318 319 @Override 320 public void bestRestored(Solution<V, T> solution) { 321 iSolution.restoreBest(); 322 } 323 }); 324 } 325 326 // Neighbour selection 327 Neighbour<V, T> neighbour = null; 328 try { 329 neighbour = getNeighbourSelection().selectNeighbour(current); 330 } catch (Exception e) { 331 sLogger.debug("Failed to select a neighbour: " + (e.getMessage() == null ? e.getClass().getSimpleName() : e.getMessage()), e); 332 } 333 for (SolverListener<V, T> listener : iSolverListeners) { 334 if (!listener.neighbourSelected(iAssignment, iSolution.getIteration(), neighbour)) { 335 neighbour = null; 336 continue; 337 } 338 } 339 340 double time = JProf.currentTimeSec() - iStartTime; 341 if (neighbour == null) { 342 sLogger.debug("No neighbour selected."); 343 // still update the solution (increase iteration etc.) 344 iSolution.update(time, false); 345 continue; 346 } 347 348 if (iSingle) { 349 if (iQueue != null) { 350 do { 351 if (iQueue.offer(neighbour, 1000, TimeUnit.MILLISECONDS)) break; 352 } while (!iStop && getTerminationCondition().canContinue(iSolution)); 353 continue; 354 } 355 356 Map<V, T> assignments = null; 357 try { 358 assignments = neighbour.assignments(); 359 } catch (Exception e) { 360 sLogger.error("Failed to enumerate " + neighbour.getClass().getSimpleName(), e); 361 } 362 if (assignments == null) { 363 sLogger.debug("No assignments returned."); 364 // still update the solution (increase iteration etc.) 365 iSolution.update(time, false); 366 continue; 367 } 368 369 if (tryLazyFirst && neighbour instanceof LazyNeighbour) { 370 LazyNeighbour<V, T> lazy = (LazyNeighbour<V, T>)neighbour; 371 double before = current.getModel().getTotalValue(current.getAssignment()); 372 neighbour.assign(current.getAssignment(), current.getIteration()); 373 double after = current.getModel().getTotalValue(current.getAssignment()); 374 if (!lazy.getAcceptanceCriterion().accept(current.getAssignment(), lazy, after - before)) 375 continue; 376 } 377 378 // Assign selected value to the selected variable 379 Lock lock = iSolution.getLock().writeLock(); 380 lock.lock(); 381 try { 382 LazyNeighbourAcceptanceCriterion<V,T> lazy = null; 383 double before = 0, value = 0; 384 if (neighbour instanceof LazyNeighbour) { 385 before = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 386 lazy = ((LazyNeighbour<V, T>)neighbour).getAcceptanceCriterion(); 387 } else if (neighbourCheck) { 388 before = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 389 value = neighbour.value(current.getAssignment()); 390 } 391 Map<V, T> undo = new HashMap<V, T>(); 392 for (Iterator<Map.Entry<V, T>> i = assignments.entrySet().iterator(); i.hasNext(); ) { 393 Map.Entry<V, T> e = i.next(); 394 T cur = iSolution.getAssignment().getValue(e.getKey()); 395 if (e.getValue() == null && cur == null) { 396 i.remove(); 397 } else if (cur != null && cur.equals(e.getValue())) { 398 i.remove(); 399 } else { 400 undo.put(e.getKey(), iSolution.getAssignment().unassign(iSolution.getIteration(), e.getKey())); 401 } 402 } 403 boolean fail = false; 404 for (T val: assignments.values()) { 405 if (val == null) continue; 406 if (iModel.inConflict(iSolution.getAssignment(), val)) { 407 fail = true; break; 408 } 409 iSolution.getAssignment().assign(iSolution.getIteration(), val); 410 } 411 if (!fail) { 412 if (lazy != null) { 413 double after = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 414 if (!lazy.accept(iSolution.getAssignment(), (LazyNeighbour<V, T>) neighbour, after - before)) 415 fail = true; 416 } else if (neighbourCheck) { 417 double after = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 418 if (before + value < after && before < after && !getSolutionComparator().isBetterThanBestSolution(iSolution)) 419 fail = true; 420 } 421 } 422 if (fail) { 423 for (V var: undo.keySet()) 424 iSolution.getAssignment().unassign(iSolution.getIteration(), var); 425 for (T val: undo.values()) 426 if (val != null) 427 iSolution.getAssignment().assign(iSolution.getIteration(), val); 428 } 429 iSolution.update(time, !fail); 430 if (fail) { 431 for (SolverListener<V, T> listener : iSolverListeners) 432 listener.neighbourFailed(current.getAssignment(), iSolution.getIteration(), neighbour); 433 continue; 434 } 435 436 onAssigned(iStartTime, iSolution); 437 438 if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iSolution.getAssignment().nrUnassignedVariables(iModel)) && getSolutionComparator().isBetterThanBestSolution(iSolution)) { 439 iSolution.saveBest(); 440 } 441 } finally { 442 lock.unlock(); 443 } 444 } else { 445 // Assign selected value to the selected variable 446 Lock lock = iSolution.getLock().writeLock(); 447 lock.lock(); 448 try { 449 neighbour.assign(iAssignment, iSolution.getIteration()); 450 iSolution.update(time, currentSolution()); 451 } finally { 452 lock.unlock(); 453 } 454 455 onAssigned(iStartTime, iSolution); 456 457 if (iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iAssignment.nrUnassignedVariables(iModel)) 458 iSolution.saveBestIfImproving(currentSolution(), getSolutionComparator()); 459 } 460 } 461 462 } catch (Exception ex) { 463 sLogger.error(ex.getMessage(), ex); 464 iProgress.fatal(getName() + " failed, reason:" + ex.getMessage(), ex); 465 if (iIndex == 0) { 466 iProgress.setStatus("Solver failed."); 467 onFailure(); 468 } 469 } 470 Lock lock = currentSolution().getLock().writeLock(); 471 lock.lock(); 472 try { 473 iNrFinished ++; 474 } finally { 475 lock.unlock(); 476 } 477 } 478 479 } 480 481 /** 482 * Solver thread 483 */ 484 protected class AssignmentThread extends Thread { 485 private double iStartTime; 486 private Solution<V, T> iSolution; 487 private BlockingQueue<Neighbour<V, T>> iQueue; 488 489 public AssignmentThread(BlockingQueue<Neighbour<V, T>> queue) { 490 setName("Assignment"); 491 setPriority(1 + THREAD_PRIORITY); 492 iSolution = iCurrentSolution; 493 iQueue = queue; 494 } 495 496 @Override 497 public void run() { 498 iStartTime = JProf.currentTimeSec(); 499 try { 500 boolean neighbourCheck = getProperties().getPropertyBoolean("ParallelSolver.SingleSolutionNeighbourCheck", false); 501 502 while (!iStop) { 503 // Break if cannot continue 504 if (!getTerminationCondition().canContinue(iSolution)) break; 505 506 // Create a sub-solution if needed 507 Neighbour<V, T> neighbour = iQueue.poll(1000, TimeUnit.MILLISECONDS); 508 509 if (neighbour == null) continue; 510 511 double time = JProf.currentTimeSec() - iStartTime; 512 513 Map<V, T> assignments = null; 514 try { 515 assignments = neighbour.assignments(); 516 } catch (Exception e) { 517 sLogger.error("Failed to enumerate " + neighbour.getClass().getSimpleName(), e); 518 } 519 if (assignments == null) { 520 sLogger.debug("No assignments returned."); 521 // still update the solution (increase iteration etc.) 522 iSolution.update(time, false); 523 continue; 524 } 525 526 // Assign selected value to the selected variable 527 Lock lock = iSolution.getLock().writeLock(); 528 lock.lock(); 529 try { 530 LazyNeighbourAcceptanceCriterion<V,T> lazy = null; 531 double before = 0, value = 0; 532 if (neighbour instanceof LazyNeighbour) { 533 before = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 534 lazy = ((LazyNeighbour<V, T>)neighbour).getAcceptanceCriterion(); 535 } else if (neighbourCheck) { 536 before = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 537 value = neighbour.value(iSolution.getAssignment()); 538 } 539 Map<V, T> undo = new HashMap<V, T>(); 540 for (V var: assignments.keySet()) 541 undo.put(var, iSolution.getAssignment().unassign(iSolution.getIteration(), var)); 542 boolean fail = false; 543 for (T val: assignments.values()) { 544 if (val == null) continue; 545 if (iSolution.getModel().inConflict(iSolution.getAssignment(), val)) { 546 fail = true; break; 547 } 548 iSolution.getAssignment().assign(iSolution.getIteration(), val); 549 } 550 if (!fail) { 551 if (lazy != null) { 552 double after = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 553 if (!lazy.accept(iSolution.getAssignment(), (LazyNeighbour<V, T>) neighbour, after - before)) 554 fail = true; 555 } else if (neighbourCheck) { 556 double after = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 557 if (before + value < after && before < after && !getSolutionComparator().isBetterThanBestSolution(iSolution)) 558 fail = true; 559 } 560 } 561 if (fail) { 562 for (V var: undo.keySet()) 563 iSolution.getAssignment().unassign(iSolution.getIteration(), var); 564 for (T val: undo.values()) 565 if (val != null) 566 iSolution.getAssignment().assign(iSolution.getIteration(), val); 567 } 568 iSolution.update(time, !fail); 569 if (fail) { 570 for (SolverListener<V, T> listener : iSolverListeners) 571 listener.neighbourFailed(iSolution.getAssignment(), iSolution.getIteration(), neighbour); 572 continue; 573 } 574 575 onAssigned(iStartTime, iSolution); 576 577 if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iSolution.getAssignment().nrUnassignedVariables(iSolution.getModel())) && getSolutionComparator().isBetterThanBestSolution(iSolution)) { 578 iSolution.saveBest(); 579 } 580 } finally { 581 lock.unlock(); 582 } 583 } 584 585 } catch (Exception ex) { 586 sLogger.error(ex.getMessage(), ex); 587 iProgress.fatal(getName() + " failed, reason:" + ex.getMessage(), ex); 588 } 589 Lock lock = currentSolution().getLock().writeLock(); 590 lock.lock(); 591 try { 592 iNrFinished ++; 593 } finally { 594 lock.unlock(); 595 } 596 } 597 598 } 599 600}