001    package net.sf.cpsolver.ifs.solver;
002    
003    import java.io.File;
004    import java.io.FileOutputStream;
005    import java.io.IOException;
006    import java.lang.reflect.Constructor;
007    import java.util.ArrayList;
008    import java.util.List;
009    import java.util.StringTokenizer;
010    
011    import net.sf.cpsolver.ifs.extension.ConflictStatistics;
012    import net.sf.cpsolver.ifs.extension.Extension;
013    import net.sf.cpsolver.ifs.extension.MacPropagation;
014    import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
015    import net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection;
016    import net.sf.cpsolver.ifs.heuristics.ValueSelection;
017    import net.sf.cpsolver.ifs.heuristics.VariableSelection;
018    import net.sf.cpsolver.ifs.model.Model;
019    import net.sf.cpsolver.ifs.model.Neighbour;
020    import net.sf.cpsolver.ifs.model.Value;
021    import net.sf.cpsolver.ifs.model.Variable;
022    import net.sf.cpsolver.ifs.perturbations.DefaultPerturbationsCounter;
023    import net.sf.cpsolver.ifs.perturbations.PerturbationsCounter;
024    import net.sf.cpsolver.ifs.solution.GeneralSolutionComparator;
025    import net.sf.cpsolver.ifs.solution.Solution;
026    import net.sf.cpsolver.ifs.solution.SolutionComparator;
027    import net.sf.cpsolver.ifs.termination.GeneralTerminationCondition;
028    import net.sf.cpsolver.ifs.termination.TerminationCondition;
029    import net.sf.cpsolver.ifs.util.DataProperties;
030    import net.sf.cpsolver.ifs.util.JProf;
031    import net.sf.cpsolver.ifs.util.Progress;
032    import net.sf.cpsolver.ifs.util.ToolBox;
033    
034    /**
035     * IFS Solver. <br>
036     * <br>
037     * The iterative forward search (IFS) algorithm is based on ideas of local
038     * search methods. However, in contrast to classical local search techniques, it
039     * operates over feasible, though not necessarily complete solutions. In such a
040     * solution, some variables can be left unassigned. Still all hard constraints
041     * on assigned variables must be satisfied. Similarly to backtracking based
042     * algorithms, this means that there are no violations of hard constraints. <br>
043     * <br>
044     * This search works in iterations. During each step, an unassigned or assigned
045     * variable is initially selected. Typically an unassigned variable is chosen
046     * like in backtracking-based search. An assigned variable may be selected when
047     * all variables are assigned but the solution is not good enough (for example,
048     * when there are still many violations of soft constraints). Once a variable is
049     * selected, a value from its domain is chosen for assignment. Even if the best
050     * value is selected (whatever �best� means), its assignment to the selected
051     * variable may cause some hard conflicts with already assigned variables. Such
052     * conflicting variables are removed from the solution and become unassigned.
053     * Finally, the selected value is assigned to the selected variable. <br>
054     * <br>
055     * Algorithm schema:
056     * <ul>
057     * <code>
058     * procedure net.sf.cpsolver.ifs(initial)  // initial solution is the parameter <br>
059     * &nbsp;&nbsp;iteration = 0;         // iteration counter <br>
060     * &nbsp;&nbsp;current = initial;     // current (partial) feasible solution <br>
061     * &nbsp;&nbsp;best = initial;        // best solution <br>
062     * &nbsp;&nbsp;while canContinue(current, iteration) do <br>
063     * &nbsp;&nbsp;&nbsp;&nbsp;iteration = iteration + 1; <br>
064     * &nbsp;&nbsp;&nbsp;&nbsp;variable = selectVariable(current); <br>
065     * &nbsp;&nbsp;&nbsp;&nbsp;value = selectValue(current, variable); <br>
066     * &nbsp;&nbsp;&nbsp;&nbsp;UNASSIGN(current,  CONFLICTING_VARIABLES(current, variable, value)); <br>
067     * &nbsp;&nbsp;&nbsp;&nbsp;ASSIGN(current, variable, value); <br>
068     * &nbsp;&nbsp;&nbsp;&nbsp;if better(current, best) then best = current; <br>
069     * &nbsp;&nbsp;end while <br>
070     * &nbsp;&nbsp;return best;<br>
071     * end procedure <br>
072     * </code>
073     * </ul>
074     * <br>
075     * The algorithm attempts to move from one (partial) feasible solution to
076     * another via repetitive assignment of a selected value to a selected variable.
077     * During this search, the feasibility of all hard constraints in each iteration
078     * step is enforced by unassigning the conflicting variables. The search is
079     * terminated when the requested solution is found or when there is a timeout,
080     * expressed e.g., as a maximal number of iterations or available time being
081     * reached. The best solution found is then returned. <br>
082     * <br>
083     * The above algorithm schema is parameterized by several functions, namely:
084     * <ul>
085     * <li>the termination condition (function canContinue, see
086     * {@link TerminationCondition}),
087     * <li>the solution comparator (function better, see {@link SolutionComparator}
088     * ),
089     * <li>the neighbour selection (function selectNeighbour, see
090     * {@link NeighbourSelection}) and
091     * </ul>
092     * <br>
093     * Usage:
094     * <ul>
095     * <code>
096     * DataProperties cfg = ToolBox.loadProperties(inputCfg); //input configuration<br>
097     * Solver solver = new Solver(cfg);<br>
098     * solver.setInitalSolution(model); //sets initial solution<br>
099     * <br>
100     * solver.start(); //server is executed in a thread<br>
101     * <br>
102     * try { //wait untill the server finishes<br>
103     * &nbsp;&nbsp;solver.getSolverThread().join(); <br>
104     * } catch (InterruptedException e) {} <br>
105     * <br>
106     * Solution solution = solver.lastSolution(); //last solution<br>
107     * solution.restoreBest(); //restore best solution ever found<br>
108     * </code>
109     * </ul>
110     * <br>
111     * Solver's parameters: <br>
112     * <table border='1'>
113     * <tr>
114     * <th>Parameter</th>
115     * <th>Type</th>
116     * <th>Comment</th>
117     * </tr>
118     * <tr>
119     * <td>General.SaveBestUnassigned</td>
120     * <td>{@link Integer}</td>
121     * <td>During the search, solution is saved when it is the best ever found
122     * solution and if the number of assigned variables is less or equal this
123     * parameter (if set to -1, the solution is always saved)</td>
124     * </tr>
125     * <tr>
126     * <td>General.Seed</td>
127     * <td>{@link Long}</td>
128     * <td>If set, random number generator is initialized with this seed</td>
129     * </tr>
130     * <tr>
131     * <td>General.SaveConfiguration</td>
132     * <td>{@link Boolean}</td>
133     * <td>If true, given configuration is stored into the output folder (during
134     * initialization of the solver,
135     * ${General.Output}/${General.ProblemName}.properties)</td>
136     * </tr>
137     * <tr>
138     * <td>Solver.AutoConfigure</td>
139     * <td>{@link Boolean}</td>
140     * <td>If true, IFS Solver is configured according to the following parameters</td>
141     * </tr>
142     * <tr>
143     * <td>Termination.Class</td>
144     * <td>{@link String}</td>
145     * <td>Fully qualified class name of the termination condition (see
146     * {@link TerminationCondition}, e.g. {@link GeneralTerminationCondition})</td>
147     * </tr>
148     * <tr>
149     * <td>Comparator.Class</td>
150     * <td>{@link String}</td>
151     * <td>Fully qualified class name of the solution comparator (see
152     * {@link SolutionComparator}, e.g. {@link GeneralSolutionComparator})</td>
153     * </tr>
154     * <tr>
155     * <td>Neighbour.Class</td>
156     * <td>{@link String}</td>
157     * <td>Fully qualified class name of the neighbour selection criterion (see
158     * {@link NeighbourSelection}, e.g. {@link StandardNeighbourSelection})</td>
159     * </tr>
160     * <tr>
161     * <td>PerturbationCounter.Class</td>
162     * <td>{@link String}</td>
163     * <td>Fully qualified class name of the perturbation counter in case of solving
164     * minimal perturbation problem (see {@link PerturbationsCounter}, e.g.
165     * {@link DefaultPerturbationsCounter})</td>
166     * </tr>
167     * <tr>
168     * <td>Extensions.Classes</td>
169     * <td>{@link String}</td>
170     * <td>Semi-colon separated list of fully qualified class names of IFS
171     * extensions (see {@link Extension}, e.g. {@link ConflictStatistics} or
172     * {@link MacPropagation})</td>
173     * </tr>
174     * </table>
175     * 
176     * @see SolverListener
177     * @see Model
178     * @see Solution
179     * @see TerminationCondition
180     * @see SolutionComparator
181     * @see PerturbationsCounter
182     * @see VariableSelection
183     * @see ValueSelection
184     * @see Extension
185     * 
186     * @version IFS 1.2 (Iterative Forward Search)<br>
187     *          Copyright (C) 2006 - 2010 Tomas Muller<br>
188     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
189     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
190     * <br>
191     *          This library is free software; you can redistribute it and/or modify
192     *          it under the terms of the GNU Lesser General Public License as
193     *          published by the Free Software Foundation; either version 3 of the
194     *          License, or (at your option) any later version. <br>
195     * <br>
196     *          This library is distributed in the hope that it will be useful, but
197     *          WITHOUT ANY WARRANTY; without even the implied warranty of
198     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
199     *          Lesser General Public License for more details. <br>
200     * <br>
201     *          You should have received a copy of the GNU Lesser General Public
202     *          License along with this library; if not see <http://www.gnu.org/licenses/>.
203     **/
204    
205    public class Solver<V extends Variable<V, T>, T extends Value<V, T>> {
206        public static int THREAD_PRIORITY = 3;
207        /** log */
208        protected static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(Solver.class);
209        /** current solution */
210        protected Solution<V, T> iCurrentSolution = null;
211        /** last solution (after IFS Solver finishes) */
212        protected Solution<V, T> iLastSolution = null;
213    
214        /** solver is stopped */
215        protected boolean iStop = false;
216    
217        /** solver thread */
218        protected SolverThread iSolverThread = null;
219        /** configuration */
220        private DataProperties iProperties = null;
221    
222        private TerminationCondition<V, T> iTerminationCondition = null;
223        private SolutionComparator<V, T> iSolutionComparator = null;
224        private PerturbationsCounter<V, T> iPerturbationsCounter = null;
225        private NeighbourSelection<V, T> iNeighbourSelection = null;
226        private List<Extension<V, T>> iExtensions = new ArrayList<Extension<V, T>>();
227        private List<SolverListener<V, T>> iSolverListeners = new ArrayList<SolverListener<V, T>>();
228        private int iSaveBestUnassigned = 0;
229    
230        private boolean iUpdateProgress = true;
231    
232        private Progress iProgress;
233    
234        /**
235         * Constructor.
236         * 
237         * @param properties
238         *            input configuration
239         */
240        public Solver(DataProperties properties) {
241            iProperties = properties;
242        }
243    
244        /** Dispose solver */
245        public void dispose() {
246            iExtensions.clear();
247            iSolverListeners.clear();
248            iTerminationCondition = null;
249            iSolutionComparator = null;
250            iPerturbationsCounter = null;
251            iNeighbourSelection = null;
252        }
253    
254        private boolean iValueExtraUsed = false;
255        private boolean iVariableExtraUsed = false;
256    
257        /** Sets termination condition */
258        public void setTerminalCondition(TerminationCondition<V, T> terminationCondition) {
259            iTerminationCondition = terminationCondition;
260        }
261    
262        /** Sets solution comparator */
263        public void setSolutionComparator(SolutionComparator<V, T> solutionComparator) {
264            iSolutionComparator = solutionComparator;
265        }
266    
267        /** Sets neighbour selection criterion */
268        public void setNeighbourSelection(NeighbourSelection<V, T> neighbourSelection) {
269            iNeighbourSelection = neighbourSelection;
270        }
271    
272        /** Sets perturbation counter (minimal perturbation problem) */
273        public void setPerturbationsCounter(PerturbationsCounter<V, T> perturbationsCounter) {
274            iPerturbationsCounter = perturbationsCounter;
275        }
276    
277        /** Add an IFS extension */
278        public void addExtension(Extension<V, T> extension) {
279            if (extension.useValueExtra() && iValueExtraUsed) {
280                sLogger.warn("Unable to add an extension " + extension + " -- value extra is already used.");
281                return;
282            }
283            if (extension.useVariableExtra() && iVariableExtraUsed) {
284                sLogger.warn("Unable to add extension " + extension + " -- variable extra is already used.");
285                return;
286            }
287            iValueExtraUsed = iValueExtraUsed | extension.useValueExtra();
288            iValueExtraUsed = iVariableExtraUsed | extension.useVariableExtra();
289            iExtensions.add(extension);
290        }
291    
292        /** Returns termination condition */
293        public TerminationCondition<V, T> getTerminationCondition() {
294            return iTerminationCondition;
295        }
296    
297        /** Returns solution comparator */
298        public SolutionComparator<V, T> getSolutionComparator() {
299            return iSolutionComparator;
300        }
301    
302        /** Returns neighbour selection criterion */
303        public NeighbourSelection<V, T> getNeighbourSelection() {
304            return iNeighbourSelection;
305        }
306    
307        /** Returns perturbation counter (minimal perturbation problem) */
308        public PerturbationsCounter<V, T> getPerturbationsCounter() {
309            return iPerturbationsCounter;
310        }
311    
312        /** Returns list of all used extensions */
313        public List<Extension<V, T>> getExtensions() {
314            return iExtensions;
315        }
316    
317        /** Adds a solver listener */
318        public void addSolverListener(SolverListener<V, T> listener) {
319            iSolverListeners.add(listener);
320        }
321    
322        /** Removes a solver listener */
323        public void removeSolverListener(SolverListener<V, T> listener) {
324            iSolverListeners.remove(listener);
325        }
326    
327        /** Registered solver listeners */
328        public List<SolverListener<V, T>> getSolverListeners() {
329            return iSolverListeners;
330        }
331    
332        /** Returns configuration */
333        public DataProperties getProperties() {
334            return iProperties;
335        }
336    
337        /**
338         * Automatic configuratin of the solver -- when Solver.AutoConfigure is true
339         */
340        @SuppressWarnings("unchecked")
341        protected void autoConfigure() {
342            try {
343                boolean mpp = getProperties().getPropertyBoolean("General.MPP", false);
344    
345                String terminationConditionClassName = getProperties().getProperty(
346                        "Termination.Class",
347                        (mpp ? "net.sf.cpsolver.ifs.termination.MPPTerminationCondition"
348                                : "net.sf.cpsolver.ifs.termination.GeneralTerminationCondition"));
349                sLogger.info("Using " + terminationConditionClassName);
350                Class<?> terminationConditionClass = Class.forName(terminationConditionClassName);
351                Constructor<?> terminationConditionConstructor = terminationConditionClass
352                        .getConstructor(new Class[] { DataProperties.class });
353                setTerminalCondition((TerminationCondition<V, T>) terminationConditionConstructor
354                        .newInstance(new Object[] { getProperties() }));
355    
356                String solutionComparatorClassName = getProperties().getProperty(
357                        "Comparator.Class",
358                        (mpp ? "net.sf.cpsolver.ifs.solution.MPPSolutionComparator"
359                                : "net.sf.cpsolver.ifs.solution.GeneralSolutionComparator"));
360                sLogger.info("Using " + solutionComparatorClassName);
361                Class<?> solutionComparatorClass = Class.forName(solutionComparatorClassName);
362                Constructor<?> solutionComparatorConstructor = solutionComparatorClass
363                        .getConstructor(new Class[] { DataProperties.class });
364                setSolutionComparator((SolutionComparator<V, T>) solutionComparatorConstructor
365                        .newInstance(new Object[] { getProperties() }));
366    
367                String neighbourSelectionClassName = getProperties().getProperty("Neighbour.Class",
368                        "net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection");
369                sLogger.info("Using " + neighbourSelectionClassName);
370                Class<?> neighbourSelectionClass = Class.forName(neighbourSelectionClassName);
371                Constructor<?> neighbourSelectionConstructor = neighbourSelectionClass
372                        .getConstructor(new Class[] { DataProperties.class });
373                setNeighbourSelection((NeighbourSelection<V, T>) neighbourSelectionConstructor
374                        .newInstance(new Object[] { getProperties() }));
375    
376                String perturbationCounterClassName = getProperties().getProperty("PerturbationCounter.Class",
377                        "net.sf.cpsolver.ifs.perturbations.DefaultPerturbationsCounter");
378                sLogger.info("Using " + perturbationCounterClassName);
379                Class<?> perturbationCounterClass = Class.forName(perturbationCounterClassName);
380                Constructor<?> perturbationCounterConstructor = perturbationCounterClass
381                        .getConstructor(new Class[] { DataProperties.class });
382                setPerturbationsCounter((PerturbationsCounter<V, T>) perturbationCounterConstructor
383                        .newInstance(new Object[] { getProperties() }));
384    
385                for (Extension<V, T> extension : iExtensions) {
386                    extension.unregister(iCurrentSolution.getModel());
387                }
388                iExtensions.clear();
389                String extensionClassNames = getProperties().getProperty("Extensions.Classes", null);
390                if (extensionClassNames != null) {
391                    StringTokenizer extensionClassNameTokenizer = new StringTokenizer(extensionClassNames, ";");
392                    while (extensionClassNameTokenizer.hasMoreTokens()) {
393                        String extensionClassName = extensionClassNameTokenizer.nextToken().trim();
394                        if (extensionClassName.isEmpty()) continue;
395                        sLogger.info("Using " + extensionClassName);
396                        Class<?> extensionClass = Class.forName(extensionClassName);
397                        Constructor<?> extensionConstructor = extensionClass.getConstructor(new Class[] { Solver.class,
398                                DataProperties.class });
399                        addExtension((Extension<V, T>) extensionConstructor.newInstance(new Object[] { this,
400                                getProperties() }));
401                    }
402                }
403            } catch (Exception e) {
404                sLogger.error("Unable to autoconfigure solver.", e);
405            }
406        }
407    
408        /** Clears best solution */
409        public void clearBest() {
410            if (iCurrentSolution != null)
411                iCurrentSolution.clearBest();
412        }
413    
414        /** Sets initial solution */
415        public void setInitalSolution(Solution<V, T> solution) {
416            iCurrentSolution = solution;
417            iLastSolution = null;
418        }
419    
420        /** Sets initial solution */
421        public void setInitalSolution(Model<V, T> model) {
422            iCurrentSolution = new Solution<V, T>(model, 0, 0);
423            iLastSolution = null;
424        }
425    
426        /** Starts solver */
427        public void start() {
428            iSolverThread = new SolverThread();
429            iSolverThread.setPriority(THREAD_PRIORITY);
430            iSolverThread.start();
431        }
432    
433        /** Returns solver's thread */
434        public Thread getSolverThread() {
435            return iSolverThread;
436        }
437    
438        /** Initialization */
439        public void init() {
440        }
441    
442        /** True, when solver should update progress (see {@link Progress}) */
443        private boolean isUpdateProgress() {
444            return iUpdateProgress;
445        }
446    
447        /** True, when solver should update progress (see {@link Progress}) */
448        public void setUpdateProgress(boolean updateProgress) {
449            iUpdateProgress = updateProgress;
450        }
451    
452        /** Last solution (when solver finishes) */
453        public Solution<V, T> lastSolution() {
454            return (iLastSolution == null ? iCurrentSolution : iLastSolution);
455        }
456    
457        /** Current solution (during the search) */
458        public Solution<V, T> currentSolution() {
459            return iCurrentSolution;
460        }
461    
462        public void initSolver() {
463            long seed = getProperties().getPropertyLong("General.Seed", System.currentTimeMillis());
464            ToolBox.setSeed(seed);
465    
466            iSaveBestUnassigned = getProperties().getPropertyInt("General.SaveBestUnassigned", 0);
467    
468            clearBest();
469            if (iProperties.getPropertyBoolean("Solver.AutoConfigure", true)) {
470                autoConfigure();
471            }
472    
473            // register extensions
474            for (Extension<V, T> extension : iExtensions) {
475                extension.register(iCurrentSolution.getModel());
476            }
477    
478            // register solution
479            iCurrentSolution.init(Solver.this);
480    
481            // register and intialize neighbour selection
482            getNeighbourSelection().init(Solver.this);
483    
484            // register and intialize perturbations counter
485            if (getPerturbationsCounter() != null)
486                getPerturbationsCounter().init(Solver.this);
487    
488            // save initial configuration
489            if (iProperties.getPropertyBoolean("General.SaveConfiguration", false)) {
490                FileOutputStream f = null;
491                try {
492                    f = new FileOutputStream(iProperties.getProperty("General.Output") + File.separator
493                            + iProperties.getProperty("General.ProblemName", "ifs") + ".properties");
494                    iProperties.store(f, iProperties.getProperty("General.ProblemNameLong", "Iterative Forward Search")
495                            + "  -- configuration file");
496                    f.flush();
497                    f.close();
498                    f = null;
499                } catch (Exception e) {
500                    sLogger.error("Unable to store configuration file :-(", e);
501                } finally {
502                    try {
503                        if (f != null)
504                            f.close();
505                    } catch (IOException e) {
506                    }
507                }
508            }
509        }
510    
511        /** Stop running solver */
512        public void stopSolver() {
513            stopSolver(true);
514        }
515        
516        /** Stop running solver */
517        public void stopSolver(boolean join) {
518            if (getSolverThread() != null) {
519                iStop = true;
520                if (join) {
521                    try {
522                        getSolverThread().join();
523                    } catch (InterruptedException ex) {
524                    }
525                }
526            }
527        }
528    
529        /** True, if the solver is running */
530        public boolean isRunning() {
531            return (getSolverThread() != null);
532        }
533    
534        /** Called when the solver is stopped */
535        protected void onStop() {
536        }
537    
538        /** Called when the solver is started */
539        protected void onStart() {
540        }
541    
542        /** Called when the solver is finished */
543        protected void onFinish() {
544        }
545    
546        /** Called when the solver fails */
547        protected void onFailure() {
548        }
549    
550        /** Called in each iteration, after a neighbour is assigned */
551        protected void onAssigned(double startTime) {
552        }
553    
554        /** Solver thread */
555        protected class SolverThread extends Thread {
556    
557            /** Solving rutine */
558            @Override
559            public void run() {
560                try {
561                    iStop = false;
562                    // Sets thread name
563                    setName("Solver");
564    
565                    // Initialization
566                    iProgress = Progress.getInstance(iCurrentSolution.getModel());
567                    iProgress.setStatus("Solving problem ...");
568                    iProgress.setPhase("Initializing solver");
569                    initSolver();
570                    onStart();
571    
572                    double startTime = JProf.currentTimeSec();
573                    if (isUpdateProgress()) {
574                        if (iCurrentSolution.getBestInfo() == null) {
575                            iProgress.setPhase("Searching for initial solution ...", iCurrentSolution.getModel()
576                                    .variables().size());
577                        } else {
578                            iProgress.setPhase("Improving found solution ...");
579                        }
580                    }
581                    long prog = 9999;
582                    sLogger.info("Initial solution:" + ToolBox.dict2string(iCurrentSolution.getInfo(), 1));
583                    if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iCurrentSolution.getModel()
584                            .nrUnassignedVariables())
585                            && (iCurrentSolution.getBestInfo() == null || getSolutionComparator().isBetterThanBestSolution(
586                                    iCurrentSolution))) {
587                        if (iCurrentSolution.getModel().nrUnassignedVariables() == 0)
588                            sLogger.info("Complete solution " + ToolBox.dict2string(iCurrentSolution.getInfo(), 1)
589                                    + " was found.");
590                        synchronized (iCurrentSolution) {
591                            iCurrentSolution.saveBest();
592                        }
593                    }
594    
595                    if (iCurrentSolution.getModel().variables().isEmpty()) {
596                        iProgress.error("Nothing to solve.");
597                        iStop = true;
598                    }
599    
600                    // Iterations: until solver can continue
601                    while (!iStop && getTerminationCondition().canContinue(iCurrentSolution)) {
602                        // Neighbour selection
603                        Neighbour<V, T> neighbour = getNeighbourSelection().selectNeighbour(iCurrentSolution);
604                        for (SolverListener<V, T> listener : iSolverListeners) {
605                            if (!listener.neighbourSelected(iCurrentSolution.getIteration(), neighbour)) {
606                                neighbour = null;
607                                continue;
608                            }
609                        }
610                        if (neighbour == null) {
611                            sLogger.debug("No neighbour selected.");
612                            synchronized (iCurrentSolution) { // still update the
613                                                              // solution (increase
614                                                              // iteration etc.)
615                                iCurrentSolution.update(JProf.currentTimeSec() - startTime);
616                            }
617                            continue;
618                        }
619    
620                        // Assign selected value to the selected variable
621                        synchronized (iCurrentSolution) {
622                            neighbour.assign(iCurrentSolution.getIteration());
623                            iCurrentSolution.update(JProf.currentTimeSec() - startTime);
624                        }
625    
626                        onAssigned(startTime);
627    
628                        // Check if the solution is the best ever found one
629                        if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iCurrentSolution.getModel()
630                                .nrUnassignedVariables())
631                                && (iCurrentSolution.getBestInfo() == null || getSolutionComparator()
632                                        .isBetterThanBestSolution(iCurrentSolution))) {
633                            if (iCurrentSolution.getModel().nrUnassignedVariables() == 0) {
634                                iProgress.debug("Complete solution of value " + iCurrentSolution.getModel().getTotalValue()
635                                        + " was found.");
636                            }
637                            synchronized (iCurrentSolution) {
638                                iCurrentSolution.saveBest();
639                            }
640                        }
641    
642                        // Increment progress bar
643                        if (isUpdateProgress()) {
644                            if (iCurrentSolution.getBestInfo() != null
645                                    && iCurrentSolution.getModel().getBestUnassignedVariables() == 0) {
646                                prog++;
647                                if (prog == 10000) {
648                                    iProgress.setPhase("Improving found solution ...");
649                                    prog = 0;
650                                } else {
651                                    iProgress.setProgress(prog / 100);
652                                }
653                            } else if ((iCurrentSolution.getBestInfo() == null || iCurrentSolution.getModel()
654                                    .getBestUnassignedVariables() > 0)
655                                    && (iCurrentSolution.getModel().variables().size() - iCurrentSolution.getModel()
656                                            .nrUnassignedVariables()) > iProgress.getProgress()) {
657                                iProgress.setProgress(iCurrentSolution.getModel().variables().size()
658                                        - iCurrentSolution.getModel().nrUnassignedVariables());
659                            }
660                        }
661    
662                    }
663    
664                    // Finalization
665                    iLastSolution = iCurrentSolution;
666    
667                    iProgress.setPhase("Done", 1);
668                    iProgress.incProgress();
669    
670                    iSolverThread = null;
671                    if (iStop) {
672                        sLogger.debug("Solver stopped.");
673                        iProgress.setStatus("Solver stopped.");
674                        onStop();
675                    } else {
676                        sLogger.debug("Solver done.");
677                        iProgress.setStatus("Solver done.");
678                        onFinish();
679                    }
680                } catch (Exception ex) {
681                    sLogger.error(ex.getMessage(), ex);
682                    iProgress.fatal("Solver failed, reason:" + ex.getMessage(), ex);
683                    iProgress.setStatus("Solver failed.");
684                    onFailure();
685                }
686                iSolverThread = null;
687            }
688        }
689        
690        /** Return true if {@link Solver#stopSolver()} was called */
691        public boolean isStop() {
692            return iStop;
693        }
694    
695    }