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 Tomas Muller<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 iStop = false; 129 iNrFinished = 0; 130 setName("SolverSync"); 131 132 // Initialization 133 iProgress = Progress.getInstance(currentSolution().getModel()); 134 iProgress.setStatus("Solving problem ..."); 135 iProgress.setPhase("Initializing solver"); 136 initSolver(); 137 onStart(); 138 139 if (isUpdateProgress()) { 140 if (currentSolution().getBestInfo() == null) { 141 iProgress.setPhase("Searching for initial solution ...", currentSolution().getModel().variables().size()); 142 } else { 143 iProgress.setPhase("Improving found solution ..."); 144 } 145 } 146 sLogger.info("Initial solution:" + ToolBox.dict2string(currentSolution().getInfo(), 2)); 147 if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= currentSolution().getAssignment().nrUnassignedVariables(currentSolution().getModel())) && (currentSolution().getBestInfo() == null || getSolutionComparator().isBetterThanBestSolution(currentSolution()))) { 148 if (currentSolution().getAssignment().nrAssignedVariables() == currentSolution().getModel().variables().size()) 149 sLogger.info("Complete solution " + ToolBox.dict2string(currentSolution().getInfo(), 1) + " was found."); 150 currentSolution().saveBest(); 151 } 152 153 if (currentSolution().getModel().variables().isEmpty()) { 154 iProgress.error("Nothing to solve."); 155 iStop = true; 156 } 157 158 BlockingQueue<Neighbour<V, T>> queue = null; 159 if (hasSingleSolution() && iNrSolvers > 1 && getProperties().getPropertyBoolean("ParallelSolver.SingleSolutionQueue", false)) 160 queue = new ArrayBlockingQueue<Neighbour<V, T>>(2 * iNrSolvers); 161 162 if (!iStop) { 163 for (int i = 1; i <= iNrSolvers; i++) { 164 SolverThread thread = new SolverThread(i, queue); 165 thread.setPriority(THREAD_PRIORITY); 166 thread.setName("Solver-" + i); 167 thread.start(); 168 iSolvers.add(thread); 169 } 170 } 171 172 if (queue != null) { 173 iAssignmentThread = new AssignmentThread(queue); 174 iAssignmentThread.start(); 175 } 176 177 int timeout = getProperties().getPropertyInt("Termination.TimeOut", 1800); 178 double start = JProf.currentTimeSec(); 179 while (!iStop && iNrFinished < iNrSolvers) { 180 try { 181 Thread.sleep(1000); 182 double time = JProf.currentTimeSec() - start; 183 184 // Increment progress bar 185 if (isUpdateProgress()) { 186 if (currentSolution().getBestInfo() != null && currentSolution().getModel().getBestUnassignedVariables() == 0) { 187 if (!"Improving found solution ...".equals(iProgress.getPhase())) 188 iProgress.setPhase("Improving found solution ..."); 189 iProgress.setProgress(Math.min(100, (int)Math.round(100 * time / timeout))); 190 } else if (currentSolution().getModel().getBestUnassignedVariables() > 0 && (currentSolution().getModel().countVariables() - currentSolution().getModel().getBestUnassignedVariables() > iProgress.getProgress())) { 191 iProgress.setProgress(currentSolution().getModel().countVariables() - currentSolution().getModel().getBestUnassignedVariables()); 192 } else if (iSolvers.get(0).iAssignment.nrAssignedVariables() > iProgress.getProgress()) { 193 iProgress.setProgress(iSolvers.get(0).iAssignment.nrAssignedVariables()); 194 } 195 } 196 } catch (InterruptedException e) {} 197 } 198 199 boolean stop = iStop; iStop = true; 200 for (SolverThread thread: iSolvers) { 201 try { 202 thread.join(); 203 } catch (InterruptedException e) {} 204 } 205 if (iAssignmentThread != null) { 206 try { 207 iAssignmentThread.join(); 208 } catch (InterruptedException e) {} 209 } 210 211 // Finalization 212 iLastSolution = iCurrentSolution; 213 214 iProgress.setPhase("Done", 1); 215 iProgress.incProgress(); 216 217 iSynchronizationThread = null; 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 } 228 } 229 230 /** 231 * Create a solution that is to be used by a solver thread of the given index 232 * @param index solver thread index 233 * @return new solution to work with 234 */ 235 protected Solution<V, T> createParallelSolution(int index) { 236 Model<V, T> model = iCurrentSolution.getModel(); 237 Assignment<V, T> assignment = new DefaultParallelAssignment<V, T>(index, model, iCurrentSolution.getAssignment()); 238 model.createAssignmentContexts(assignment, true); 239 Solution<V, T> solution = new Solution<V, T>(model, assignment); 240 for (SolutionListener<V, T> listener: iCurrentSolution.getSolutionListeners()) 241 solution.addSolutionListener(listener); 242 return solution; 243 } 244 245 /** 246 * Returns true if the solver works only with one solution (regardless the number of threads it is using) 247 * @return true if the current solution is {@link DefaultSingleAssignment} 248 */ 249 @Override 250 public boolean hasSingleSolution() { 251 return iCurrentSolution.getAssignment() instanceof DefaultSingleAssignment; 252 } 253 254 /** 255 * Solver thread 256 */ 257 protected class SolverThread extends Thread { 258 private double iStartTime; 259 private int iIndex; 260 private boolean iSingle; 261 private Model<V, T> iModel; 262 private Solution<V, T> iSolution; 263 private Assignment<V, T> iAssignment; 264 private BlockingQueue<Neighbour<V, T>> iQueue; 265 266 public SolverThread(int index, BlockingQueue<Neighbour<V, T>> queue) { 267 iIndex = index; 268 iSingle = hasSingleSolution(); 269 iModel = iCurrentSolution.getModel(); 270 iSolution = (iSingle || iCurrentSolution.getAssignment().getIndex() == index ? iCurrentSolution : createParallelSolution(iIndex)); 271 iAssignment = iSolution.getAssignment(); 272 iQueue = queue; 273 } 274 275 @Override 276 public void run() { 277 iStartTime = JProf.currentTimeSec(); 278 try { 279 boolean neighbourCheck = getProperties().getPropertyBoolean("ParallelSolver.SingleSolutionNeighbourCheck", false); 280 boolean tryLazyFirst = getProperties().getPropertyBoolean("ParallelSolver.SingleSolutionTryLazyFirst", false); 281 282 while (!iStop) { 283 // Break if cannot continue 284 if (!getTerminationCondition().canContinue(iSolution)) break; 285 286 // Create a sub-solution if needed 287 Solution<V, T> current = iSolution; 288 if (iSingle) { 289 current = new Solution<V, T>(iModel, iModel.createInheritedAssignment(iSolution, iIndex), iSolution.getIteration(), iSolution.getTime()); 290 current.addSolutionListener(new SolutionListener<V, T>() { 291 @Override 292 public void solutionUpdated(Solution<V, T> solution) { 293 } 294 295 @Override 296 public void getInfo(Solution<V, T> solution, Map<String, String> info) { 297 } 298 299 @Override 300 public void getInfo(Solution<V, T> solution, Map<String, String> info, Collection<V> variables) { 301 } 302 303 @Override 304 public void bestCleared(Solution<V, T> solution) { 305 } 306 307 @Override 308 public void bestSaved(Solution<V, T> solution) { 309 } 310 311 @Override 312 public void bestRestored(Solution<V, T> solution) { 313 iSolution.restoreBest(); 314 } 315 }); 316 } 317 318 // Neighbour selection 319 Neighbour<V, T> neighbour = null; 320 try { 321 neighbour = getNeighbourSelection().selectNeighbour(current); 322 } catch (Exception e) { 323 sLogger.debug("Failed to select a neighbour: " + (e.getMessage() == null ? e.getClass().getSimpleName() : e.getMessage()), e); 324 } 325 for (SolverListener<V, T> listener : iSolverListeners) { 326 if (!listener.neighbourSelected(iAssignment, iSolution.getIteration(), neighbour)) { 327 neighbour = null; 328 continue; 329 } 330 } 331 332 double time = JProf.currentTimeSec() - iStartTime; 333 if (neighbour == null) { 334 sLogger.debug("No neighbour selected."); 335 // still update the solution (increase iteration etc.) 336 iSolution.update(time, false); 337 continue; 338 } 339 340 if (iSingle) { 341 if (iQueue != null) { 342 do { 343 if (iQueue.offer(neighbour, 1000, TimeUnit.MILLISECONDS)) break; 344 } while (!iStop && getTerminationCondition().canContinue(iSolution)); 345 continue; 346 } 347 348 Map<V, T> assignments = null; 349 try { 350 assignments = neighbour.assignments(); 351 } catch (Exception e) { 352 sLogger.error("Failed to enumerate " + neighbour.getClass().getSimpleName(), e); 353 } 354 if (assignments == null) { 355 sLogger.debug("No assignments returned."); 356 // still update the solution (increase iteration etc.) 357 iSolution.update(time, false); 358 continue; 359 } 360 361 if (tryLazyFirst && neighbour instanceof LazyNeighbour) { 362 LazyNeighbour<V, T> lazy = (LazyNeighbour<V, T>)neighbour; 363 double before = current.getModel().getTotalValue(current.getAssignment()); 364 neighbour.assign(current.getAssignment(), current.getIteration()); 365 double after = current.getModel().getTotalValue(current.getAssignment()); 366 if (!lazy.getAcceptanceCriterion().accept(current.getAssignment(), lazy, after - before)) 367 continue; 368 } 369 370 // Assign selected value to the selected variable 371 Lock lock = iSolution.getLock().writeLock(); 372 lock.lock(); 373 try { 374 LazyNeighbourAcceptanceCriterion<V,T> lazy = null; 375 double before = 0, value = 0; 376 if (neighbour instanceof LazyNeighbour) { 377 before = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 378 lazy = ((LazyNeighbour<V, T>)neighbour).getAcceptanceCriterion(); 379 } else if (neighbourCheck) { 380 before = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 381 value = neighbour.value(current.getAssignment()); 382 } 383 Map<V, T> undo = new HashMap<V, T>(); 384 for (Iterator<Map.Entry<V, T>> i = assignments.entrySet().iterator(); i.hasNext(); ) { 385 Map.Entry<V, T> e = i.next(); 386 T cur = iSolution.getAssignment().getValue(e.getKey()); 387 if (e.getValue() == null && cur == null) { 388 i.remove(); 389 } else if (cur != null && cur.equals(e.getValue())) { 390 i.remove(); 391 } else { 392 undo.put(e.getKey(), iSolution.getAssignment().unassign(iSolution.getIteration(), e.getKey())); 393 } 394 } 395 boolean fail = false; 396 for (T val: assignments.values()) { 397 if (val == null) continue; 398 if (iModel.inConflict(iSolution.getAssignment(), val)) { 399 fail = true; break; 400 } 401 iSolution.getAssignment().assign(iSolution.getIteration(), val); 402 } 403 if (!fail) { 404 if (lazy != null) { 405 double after = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 406 if (!lazy.accept(iSolution.getAssignment(), (LazyNeighbour<V, T>) neighbour, after - before)) 407 fail = true; 408 } else if (neighbourCheck) { 409 double after = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 410 if (before + value < after && before < after && !getSolutionComparator().isBetterThanBestSolution(iSolution)) 411 fail = true; 412 } 413 } 414 if (fail) { 415 for (V var: undo.keySet()) 416 iSolution.getAssignment().unassign(iSolution.getIteration(), var); 417 for (T val: undo.values()) 418 if (val != null) 419 iSolution.getAssignment().assign(iSolution.getIteration(), val); 420 } 421 iSolution.update(time, !fail); 422 if (fail) { 423 for (SolverListener<V, T> listener : iSolverListeners) 424 listener.neighbourFailed(current.getAssignment(), iSolution.getIteration(), neighbour); 425 continue; 426 } 427 428 onAssigned(iStartTime, iSolution); 429 430 if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iSolution.getAssignment().nrUnassignedVariables(iModel)) && getSolutionComparator().isBetterThanBestSolution(iSolution)) { 431 iSolution.saveBest(); 432 } 433 } finally { 434 lock.unlock(); 435 } 436 } else { 437 // Assign selected value to the selected variable 438 Lock lock = iSolution.getLock().writeLock(); 439 lock.lock(); 440 try { 441 neighbour.assign(iAssignment, iSolution.getIteration()); 442 iSolution.update(time, currentSolution()); 443 } finally { 444 lock.unlock(); 445 } 446 447 onAssigned(iStartTime, iSolution); 448 449 if (iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iAssignment.nrUnassignedVariables(iModel)) 450 iSolution.saveBestIfImproving(currentSolution(), getSolutionComparator()); 451 } 452 } 453 454 } catch (Exception ex) { 455 sLogger.error(ex.getMessage(), ex); 456 iProgress.fatal(getName() + " failed, reason:" + ex.getMessage(), ex); 457 if (iIndex == 0) { 458 iProgress.setStatus("Solver failed."); 459 onFailure(); 460 } 461 } 462 Lock lock = currentSolution().getLock().writeLock(); 463 lock.lock(); 464 try { 465 iNrFinished ++; 466 } finally { 467 lock.unlock(); 468 } 469 } 470 471 } 472 473 /** 474 * Solver thread 475 */ 476 protected class AssignmentThread extends Thread { 477 private double iStartTime; 478 private Solution<V, T> iSolution; 479 private BlockingQueue<Neighbour<V, T>> iQueue; 480 481 public AssignmentThread(BlockingQueue<Neighbour<V, T>> queue) { 482 setName("Assignment"); 483 setPriority(1 + THREAD_PRIORITY); 484 iSolution = iCurrentSolution; 485 iQueue = queue; 486 } 487 488 @Override 489 public void run() { 490 iStartTime = JProf.currentTimeSec(); 491 try { 492 boolean neighbourCheck = getProperties().getPropertyBoolean("ParallelSolver.SingleSolutionNeighbourCheck", false); 493 494 while (!iStop) { 495 // Break if cannot continue 496 if (!getTerminationCondition().canContinue(iSolution)) break; 497 498 // Create a sub-solution if needed 499 Neighbour<V, T> neighbour = iQueue.poll(1000, TimeUnit.MILLISECONDS); 500 501 if (neighbour == null) continue; 502 503 double time = JProf.currentTimeSec() - iStartTime; 504 505 Map<V, T> assignments = null; 506 try { 507 assignments = neighbour.assignments(); 508 } catch (Exception e) { 509 sLogger.error("Failed to enumerate " + neighbour.getClass().getSimpleName(), e); 510 } 511 if (assignments == null) { 512 sLogger.debug("No assignments returned."); 513 // still update the solution (increase iteration etc.) 514 iSolution.update(time, false); 515 continue; 516 } 517 518 // Assign selected value to the selected variable 519 Lock lock = iSolution.getLock().writeLock(); 520 lock.lock(); 521 try { 522 LazyNeighbourAcceptanceCriterion<V,T> lazy = null; 523 double before = 0, value = 0; 524 if (neighbour instanceof LazyNeighbour) { 525 before = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 526 lazy = ((LazyNeighbour<V, T>)neighbour).getAcceptanceCriterion(); 527 } else if (neighbourCheck) { 528 before = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 529 value = neighbour.value(iSolution.getAssignment()); 530 } 531 Map<V, T> undo = new HashMap<V, T>(); 532 for (V var: assignments.keySet()) 533 undo.put(var, iSolution.getAssignment().unassign(iSolution.getIteration(), var)); 534 boolean fail = false; 535 for (T val: assignments.values()) { 536 if (val == null) continue; 537 if (iSolution.getModel().inConflict(iSolution.getAssignment(), val)) { 538 fail = true; break; 539 } 540 iSolution.getAssignment().assign(iSolution.getIteration(), val); 541 } 542 if (!fail) { 543 if (lazy != null) { 544 double after = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 545 if (!lazy.accept(iSolution.getAssignment(), (LazyNeighbour<V, T>) neighbour, after - before)) 546 fail = true; 547 } else if (neighbourCheck) { 548 double after = iSolution.getModel().getTotalValue(iSolution.getAssignment()); 549 if (before + value < after && before < after && !getSolutionComparator().isBetterThanBestSolution(iSolution)) 550 fail = true; 551 } 552 } 553 if (fail) { 554 for (V var: undo.keySet()) 555 iSolution.getAssignment().unassign(iSolution.getIteration(), var); 556 for (T val: undo.values()) 557 if (val != null) 558 iSolution.getAssignment().assign(iSolution.getIteration(), val); 559 } 560 iSolution.update(time, !fail); 561 if (fail) { 562 for (SolverListener<V, T> listener : iSolverListeners) 563 listener.neighbourFailed(iSolution.getAssignment(), iSolution.getIteration(), neighbour); 564 continue; 565 } 566 567 onAssigned(iStartTime, iSolution); 568 569 if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iSolution.getAssignment().nrUnassignedVariables(iSolution.getModel())) && getSolutionComparator().isBetterThanBestSolution(iSolution)) { 570 iSolution.saveBest(); 571 } 572 } finally { 573 lock.unlock(); 574 } 575 } 576 577 } catch (Exception ex) { 578 sLogger.error(ex.getMessage(), ex); 579 iProgress.fatal(getName() + " failed, reason:" + ex.getMessage(), ex); 580 } 581 Lock lock = currentSolution().getLock().writeLock(); 582 lock.lock(); 583 try { 584 iNrFinished ++; 585 } finally { 586 lock.unlock(); 587 } 588 } 589 590 } 591 592}