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