    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}