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