    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'><caption>Related Solver Parameters</caption>
    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 * @author  Tomáš Müller
    184 * @version IFS 1.3 (Iterative Forward Search)<br>
    185 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    186 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    187 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    188 * <br>
    189 *          This library is free software; you can redistribute it and/or modify
    190 *          it under the terms of the GNU Lesser General Public License as
    191 *          published by the Free Software Foundation; either version 3 of the
    192 *          License, or (at your option) any later version. <br>
    193 * <br>
    194 *          This library is distributed in the hope that it will be useful, but
    195 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    196 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    197 *          Lesser General Public License for more details. <br>
    198 * <br>
    199 *          You should have received a copy of the GNU Lesser General Public
    200 *          License along with this library; if not see <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
    201 *
    202 * @param <V> Variable
    203 * @param <T> Value
    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.logging.log4j.Logger sLogger = org.apache.logging.log4j.LogManager.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    protected List<SolverListener<V, T>> iSolverListeners = new ArrayList<SolverListener<V, T>>();
    228    protected int iSaveBestUnassigned = 0;
    229
    230    private boolean iUpdateProgress = true;
    231
    232    protected 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    /** Sets termination condition
    255     * @param terminationCondition termination condition
    256     **/
    257    public void setTerminalCondition(TerminationCondition<V, T> terminationCondition) {
    258        iTerminationCondition = terminationCondition;
    259    }
    260
    261    /** Sets solution comparator
    262     * @param solutionComparator solution comparator
    263     **/
    264    public void setSolutionComparator(SolutionComparator<V, T> solutionComparator) {
    265        iSolutionComparator = solutionComparator;
    266    }
    267
    268    /** Sets neighbour selection criterion
    269     * @param neighbourSelection neighbour selection criterion
    270     **/
    271    public void setNeighbourSelection(NeighbourSelection<V, T> neighbourSelection) {
    272        iNeighbourSelection = neighbourSelection;
    273    }
    274
    275    /** Sets perturbation counter (minimal perturbation problem)
    276     * @param perturbationsCounter perturbation counter
    277     **/
    278    public void setPerturbationsCounter(PerturbationsCounter<V, T> perturbationsCounter) {
    279        iPerturbationsCounter = perturbationsCounter;
    280    }
    281
    282    /** Add an IFS extension
    283     * @param extension an extension
    284     **/
    285    public void addExtension(Extension<V, T> extension) {
    286        iExtensions.add(extension);
    287    }
    288
    289    /** Returns termination condition
    290     * @return termination condition
    291     **/
    292    public TerminationCondition<V, T> getTerminationCondition() {
    293        return iTerminationCondition;
    294    }
    295
    296    /** Returns solution comparator
    297     * @return solution comparator
    298     **/
    299    public SolutionComparator<V, T> getSolutionComparator() {
    300        return iSolutionComparator;
    301    }
    302
    303    /** Returns neighbour selection criterion
    304     * @return neighbour selection criterion
    305     **/
    306    public NeighbourSelection<V, T> getNeighbourSelection() {
    307        return iNeighbourSelection;
    308    }
    309
    310    /** Returns perturbation counter (minimal perturbation problem)
    311     * @return perturbation counter
    312     **/
    313    public PerturbationsCounter<V, T> getPerturbationsCounter() {
    314        return iPerturbationsCounter;
    315    }
    316
    317    /** Returns list of all used extensions
    318     * @return list of all registered extensions
    319     **/
    320    public List<Extension<V, T>> getExtensions() {
    321        return iExtensions;
    322    }
    323
    324    /** Adds a solver listener
    325     * @param listener solver listener
    326     **/
    327    public void addSolverListener(SolverListener<V, T> listener) {
    328        iSolverListeners.add(listener);
    329    }
    330
    331    /** Removes a solver listener
    332     * @param listener solver listener
    333     **/
    334    public void removeSolverListener(SolverListener<V, T> listener) {
    335        iSolverListeners.remove(listener);
    336    }
    337
    338    /** Registered solver listeners
    339     * @return list of all registered solver listeners
    340     **/
    341    public List<SolverListener<V, T>> getSolverListeners() {
    342        return iSolverListeners;
    343    }
    344
    345    /** Returns configuration
    346     * @return solver configuration
    347     **/
    348    public DataProperties getProperties() {
    349        return iProperties;
    350    }
    351
    352    /**
    353     * Automatic configuratin of the solver -- when Solver.AutoConfigure is true
    354     */
    355    @SuppressWarnings("unchecked")
    356    protected void autoConfigure() {
    357        try {
    358            boolean mpp = getProperties().getPropertyBoolean("General.MPP", false);
    359
    360            String terminationConditionClassName = getProperties().getProperty(
    361                    "Termination.Class",
    362                    (mpp ? "org.cpsolver.ifs.termination.MPPTerminationCondition"
    363                            : "org.cpsolver.ifs.termination.GeneralTerminationCondition"));
    364            sLogger.info("Using " + terminationConditionClassName);
    365            Class<?> terminationConditionClass = Class.forName(terminationConditionClassName);
    366            Constructor<?> terminationConditionConstructor = terminationConditionClass
    367                    .getConstructor(new Class[] { DataProperties.class });
    368            setTerminalCondition((TerminationCondition<V, T>) terminationConditionConstructor
    369                    .newInstance(new Object[] { getProperties() }));
    370
    371            String solutionComparatorClassName = getProperties().getProperty(
    372                    "Comparator.Class",
    373                    (mpp ? "org.cpsolver.ifs.solution.MPPSolutionComparator"
    374                            : "org.cpsolver.ifs.solution.GeneralSolutionComparator"));
    375            sLogger.info("Using " + solutionComparatorClassName);
    376            Class<?> solutionComparatorClass = Class.forName(solutionComparatorClassName);
    377            Constructor<?> solutionComparatorConstructor = solutionComparatorClass
    378                    .getConstructor(new Class[] { DataProperties.class });
    379            setSolutionComparator((SolutionComparator<V, T>) solutionComparatorConstructor
    380                    .newInstance(new Object[] { getProperties() }));
    381
    382            String neighbourSelectionClassName = getProperties().getProperty("Neighbour.Class",
    383                    "org.cpsolver.ifs.heuristics.StandardNeighbourSelection");
    384            sLogger.info("Using " + neighbourSelectionClassName);
    385            Class<?> neighbourSelectionClass = Class.forName(neighbourSelectionClassName);
    386            Constructor<?> neighbourSelectionConstructor = neighbourSelectionClass
    387                    .getConstructor(new Class[] { DataProperties.class });
    388            setNeighbourSelection((NeighbourSelection<V, T>) neighbourSelectionConstructor
    389                    .newInstance(new Object[] { getProperties() }));
    390
    391            String perturbationCounterClassName = getProperties().getProperty("PerturbationCounter.Class",
    392                    "org.cpsolver.ifs.perturbations.DefaultPerturbationsCounter");
    393            sLogger.info("Using " + perturbationCounterClassName);
    394            Class<?> perturbationCounterClass = Class.forName(perturbationCounterClassName);
    395            Constructor<?> perturbationCounterConstructor = perturbationCounterClass
    396                    .getConstructor(new Class[] { DataProperties.class });
    397            setPerturbationsCounter((PerturbationsCounter<V, T>) perturbationCounterConstructor
    398                    .newInstance(new Object[] { getProperties() }));
    399
    400            for (Extension<V, T> extension : iExtensions) {
    401                extension.unregister(iCurrentSolution.getModel());
    402            }
    403            iExtensions.clear();
    404            String extensionClassNames = getProperties().getProperty("Extensions.Classes", null);
    405            if (extensionClassNames != null) {
    406                StringTokenizer extensionClassNameTokenizer = new StringTokenizer(extensionClassNames, ";");
    407                while (extensionClassNameTokenizer.hasMoreTokens()) {
    408                    String extensionClassName = extensionClassNameTokenizer.nextToken().trim();
    409                    if (extensionClassName.isEmpty()) continue;
    410                    sLogger.info("Using " + extensionClassName);
    411                    Class<?> extensionClass = Class.forName(extensionClassName);
    412                    Constructor<?> extensionConstructor = extensionClass.getConstructor(new Class[] { Solver.class,
    413                            DataProperties.class });
    414                    addExtension((Extension<V, T>) extensionConstructor.newInstance(new Object[] { this,
    415                            getProperties() }));
    416                }
    417            }
    418        } catch (Exception e) {
    419            sLogger.error("Unable to autoconfigure solver.", e);
    420        }
    421    }
    422
    423    /** Clears best solution */
    424    public void clearBest() {
    425        if (iCurrentSolution != null)
    426            iCurrentSolution.clearBest();
    427    }
    428
    429    /** Sets initial solution
    430     * @param solution initial solution
    431     **/
    432    public void setInitalSolution(Solution<V, T> solution) {
    433        iCurrentSolution = solution;
    434        iLastSolution = null;
    435    }
    436
    437    /** Sets initial solution
    438     * @param model problem model
    439     **/
    440    public void setInitalSolution(Model<V, T> model) {
    441        setInitalSolution(new Solution<V, T>(model, new DefaultSingleAssignment<V, T>(), 0, 0));
    442    }
    443
    444    /** Starts solver */
    445    public void start() {
    446        iSolverThread = new SolverThread();
    447        iSolverThread.setPriority(THREAD_PRIORITY);
    448        iSolverThread.start();
    449    }
    450
    451    /** Returns solver's thread
    452     * @return solver's thread
    453     **/
    454    public Thread getSolverThread() {
    455        return iSolverThread;
    456    }
    457
    458    /** Initialization */
    459    public void init() {
    460    }
    461
    462    /** True, when solver should update progress (see {@link Progress})
    463     * @return true if the solver should update process
    464     **/
    465    protected boolean isUpdateProgress() {
    466        return iUpdateProgress;
    467    }
    468
    469    /** True, when solver should update progress (see {@link Progress})
    470     * @param updateProgress true if the solver should update process (default is true)
    471     **/
    472    public void setUpdateProgress(boolean updateProgress) {
    473        iUpdateProgress = updateProgress;
    474    }
    475
    476    /** Last solution (when solver finishes)
    477     * @return last solution
    478     **/
    479    public Solution<V, T> lastSolution() {
    480        return (iLastSolution == null ? iCurrentSolution : iLastSolution);
    481    }
    482
    483    /** Current solution (during the search)
    484     * @return current solution
    485     **/
    486    public Solution<V, T> currentSolution() {
    487        return iCurrentSolution;
    488    }
    489
    490    public void initSolver() {
    491        long seed = getProperties().getPropertyLong("General.Seed", System.currentTimeMillis());
    492        ToolBox.setSeed(seed);
    493
    494        iSaveBestUnassigned = getProperties().getPropertyInt("General.SaveBestUnassigned", 0);
    495
    496        clearBest();
    497        if (iProperties.getPropertyBoolean("Solver.AutoConfigure", true)) {
    498            autoConfigure();
    499        }
    500
    501        // register extensions
    502        for (Extension<V, T> extension : iExtensions) {
    503            extension.register(iCurrentSolution.getModel());
    504        }
    505
    506        // register solution
    507        iCurrentSolution.init(Solver.this);
    508
    509        // register and intialize neighbour selection
    510        getNeighbourSelection().init(Solver.this);
    511
    512        // register and intialize perturbations counter
    513        if (getPerturbationsCounter() != null)
    514            getPerturbationsCounter().init(Solver.this);
    515
    516        // save initial configuration
    517        if (iProperties.getPropertyBoolean("General.SaveConfiguration", false)) {
    518            FileOutputStream f = null;
    519            try {
    520                f = new FileOutputStream(iProperties.getProperty("General.Output") + File.separator
    521                        + iProperties.getProperty("General.ProblemName", "ifs") + ".properties");
    522                iProperties.store(f, iProperties.getProperty("General.ProblemNameLong", "Iterative Forward Search")
    523                        + "  -- configuration file");
    524                f.flush();
    525                f.close();
    526                f = null;
    527            } catch (Exception e) {
    528                sLogger.error("Unable to store configuration file :-(", e);
    529            } finally {
    530                try {
    531                    if (f != null)
    532                        f.close();
    533                } catch (IOException e) {
    534                }
    535            }
    536        }
    537    }
    538
    539    /** Stop running solver */
    540    public void stopSolver() {
    541        stopSolver(true);
    542    }
    543
    544    /** Stop running solver
    545     * @param join wait for the solver thread to finish
    546     **/
    547    public void stopSolver(boolean join) {
    548        if (getSolverThread() != null) {
    549            iStop = true;
    550            if (join) {
    551                try {
    552                    getSolverThread().join();
    553                } catch (InterruptedException ex) {
    554                }
    555            }
    556        }
    557    }
    558
    559    /** True, if the solver is running
    560     * @return true if the solver is running
    561     **/
    562    public boolean isRunning() {
    563        return (getSolverThread() != null);
    564    }
    565
    566    /** Called when the solver is stopped */
    567    protected void onStop() {
    568    }
    569
    570    /** Called when the solver is started */
    571    protected void onStart() {
    572    }
    573
    574    /** Called when the solver is finished */
    575    protected void onFinish() {
    576    }
    577
    578    /** Called when the solver fails */
    579    protected void onFailure() {
    580    }
    581
    582    /** Called in each iteration, after a neighbour is assigned
    583     * @param startTime solver start time in seconds
    584     * @param solution current solution
    585     **/
    586    protected void onAssigned(double startTime, Solution<V, T> solution) {
    587    }
    588
    589    /**
    590     * Returns true if the solver works only with one solution (regardless the number of threads it is using)
    591     * @return true
    592     */
    593    public boolean hasSingleSolution() {
    594        return currentSolution().getAssignment() instanceof DefaultSingleAssignment;
    595    }
    596
    597    /** Solver thread */
    598    protected class SolverThread extends Thread {
    599
    600        /** Solving rutine */
    601        @Override
    602        public void run() {
    603            try {
    604                iStop = false;
    605                // Sets thread name
    606                setName("Solver");
    607
    608                // Initialization
    609                iProgress = Progress.getInstance(iCurrentSolution.getModel());
    610                iProgress.setStatus("Solving problem ...");
    611                iProgress.setPhase("Initializing solver");
    612                initSolver();
    613                onStart();
    614
    615                double startTime = JProf.currentTimeSec();
    616                int timeout = getProperties().getPropertyInt("Termination.TimeOut", 1800);
    617                if (isUpdateProgress()) {
    618                    if (iCurrentSolution.getBestInfo() == null) {
    619                        iProgress.setPhase("Searching for initial solution ...", iCurrentSolution.getModel()
    620                                .variables().size());
    621                    } else {
    622                        iProgress.setPhase("Improving found solution ...");
    623                    }
    624                }
    625                sLogger.info("Initial solution:" + ToolBox.dict2string(iCurrentSolution.getExtendedInfo(), 1));
    626                if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iCurrentSolution.getAssignment().nrUnassignedVariables(iCurrentSolution.getModel()))
    627                        && (iCurrentSolution.getBestInfo() == null || getSolutionComparator().isBetterThanBestSolution(iCurrentSolution))) {
    628                    if (iCurrentSolution.getModel().variables().size() == iCurrentSolution.getAssignment().nrAssignedVariables())
    629                        sLogger.info("Complete solution " + ToolBox.dict2string(iCurrentSolution.getExtendedInfo(), 1) + " was found.");
    630                    iCurrentSolution.saveBest();
    631                }
    632
    633                if (iCurrentSolution.getModel().variables().isEmpty()) {
    634                    iProgress.error("Nothing to solve.");
    635                    iStop = true;
    636                }
    637
    638                // Iterations: until solver can continue
    639                while (!iStop && getTerminationCondition().canContinue(iCurrentSolution)) {
    640                    // Neighbour selection
    641                    Neighbour<V, T> neighbour = getNeighbourSelection().selectNeighbour(iCurrentSolution);
    642                    for (SolverListener<V, T> listener : iSolverListeners) {
    643                        if (!listener.neighbourSelected(iCurrentSolution.getAssignment(), iCurrentSolution.getIteration(), neighbour)) {
    644                            neighbour = null;
    645                            continue;
    646                        }
    647                    }
    648                    if (neighbour == null) {
    649                        sLogger.debug("No neighbour selected.");
    650                        // still update the solution (increase iteration etc.)
    651                        iCurrentSolution.update(JProf.currentTimeSec() - startTime, false);
    652                        continue;
    653                    }
    654
    655                    // Assign selected value to the selected variable
    656                    Lock lock = iCurrentSolution.getLock().writeLock();
    657                    lock.lock();
    658                    try {
    659                        neighbour.assign(iCurrentSolution.getAssignment(), iCurrentSolution.getIteration());
    660                    } finally {
    661                        lock.unlock();
    662                    }
    663                    double time = JProf.currentTimeSec() - startTime;
    664                    iCurrentSolution.update(time);
    665
    666                    onAssigned(startTime, iCurrentSolution);
    667
    668                    // Check if the solution is the best ever found one
    669                    if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iCurrentSolution.getAssignment().nrUnassignedVariables(iCurrentSolution.getModel())) && (iCurrentSolution.getBestInfo() == null || getSolutionComparator().isBetterThanBestSolution(iCurrentSolution))) {
    670                        if (iCurrentSolution.getModel().variables().size() == iCurrentSolution.getAssignment().nrAssignedVariables()) {
    671                            iProgress.debug("Complete solution of value " + iCurrentSolution.getModel().getTotalValue(iCurrentSolution.getAssignment()) + " was found.");
    672                        }
    673                        iCurrentSolution.saveBest();
    674                    }
    675
    676                    // Increment progress bar
    677                    if (isUpdateProgress()) {
    678                        if (iCurrentSolution.getBestInfo() != null && iCurrentSolution.getModel().getBestUnassignedVariables() == 0) {
    679                            if (!"Improving found solution ...".equals(iProgress.getPhase()))
    680                                iProgress.setPhase("Improving found solution ...");
    681                            iProgress.setProgress(Math.min(100, (int)Math.round(100 * time / timeout)));
    682                        } else if ((iCurrentSolution.getBestInfo() == null || iCurrentSolution.getModel().getBestUnassignedVariables() > 0) && (iCurrentSolution.getAssignment().nrAssignedVariables() > iProgress.getProgress())) {
    683                            iProgress.setProgress(iCurrentSolution.getAssignment().nrAssignedVariables());
    684                        }
    685                    }
    686
    687                }
    688
    689                // Finalization
    690                iLastSolution = iCurrentSolution;
    691
    692                iProgress.setPhase("Done", 1);
    693                iProgress.incProgress();
    694
    695                if (iStop) {
    696                    sLogger.debug("Solver stopped.");
    697                    iProgress.setStatus("Solver stopped.");
    698                    onStop();
    699                } else {
    700                    sLogger.debug("Solver done.");
    701                    iProgress.setStatus("Solver done.");
    702                    onFinish();
    703                }
    704            } catch (Exception ex) {
    705                sLogger.error(ex.getMessage(), ex);
    706                iProgress.fatal("Solver failed, reason:" + ex.getMessage(), ex);
    707                iProgress.setStatus("Solver failed.");
    708                onFailure();
    709            } finally {
    710                iSolverThread = null;
    711            }
    712        }
    713    }
    714
    715    /** Return true if {@link Solver#stopSolver()} was called
    716     * @return true if the solver is to be stopped
    717     **/
    718    public boolean isStop() {
    719        return iStop;
    720    }
    721
    722}