    001package net.sf.cpsolver.ifs.solver;
    002
    003import java.io.File;
    004import java.io.FileOutputStream;
    005import java.io.IOException;
    006import java.lang.reflect.Constructor;
    007import java.util.ArrayList;
    008import java.util.List;
    009import java.util.StringTokenizer;
    010
    011import net.sf.cpsolver.ifs.extension.ConflictStatistics;
    012import net.sf.cpsolver.ifs.extension.Extension;
    013import net.sf.cpsolver.ifs.extension.MacPropagation;
    014import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
    015import net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection;
    016import net.sf.cpsolver.ifs.heuristics.ValueSelection;
    017import net.sf.cpsolver.ifs.heuristics.VariableSelection;
    018import net.sf.cpsolver.ifs.model.Model;
    019import net.sf.cpsolver.ifs.model.Neighbour;
    020import net.sf.cpsolver.ifs.model.Value;
    021import net.sf.cpsolver.ifs.model.Variable;
    022import net.sf.cpsolver.ifs.perturbations.DefaultPerturbationsCounter;
    023import net.sf.cpsolver.ifs.perturbations.PerturbationsCounter;
    024import net.sf.cpsolver.ifs.solution.GeneralSolutionComparator;
    025import net.sf.cpsolver.ifs.solution.Solution;
    026import net.sf.cpsolver.ifs.solution.SolutionComparator;
    027import net.sf.cpsolver.ifs.termination.GeneralTerminationCondition;
    028import net.sf.cpsolver.ifs.termination.TerminationCondition;
    029import net.sf.cpsolver.ifs.util.DataProperties;
    030import net.sf.cpsolver.ifs.util.JProf;
    031import net.sf.cpsolver.ifs.util.Progress;
    032import 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 Tomáš Müller<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
    205public 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}