    001    package ifs.solver;
    002
    003    import ifs.extension.*;
    004    import ifs.heuristics.*;
    005    import ifs.model.*;
    006    import ifs.solution.*;
    007    import ifs.termination.*;
    008    import ifs.util.*;
    009    import ifs.perturbations.*;
    010
    011    import java.io.*;
    012    import java.util.*;
    013    import java.lang.reflect.*;
    014
    015    /**
    016     * IFS Solver.
    017     * <br><br>
    018     * The iterative forward search (IFS) algorithm is based on ideas of local search methods. However, in contrast to
    019     * classical local search techniques, it operates over feasible, though not necessarily complete solutions. In such
    020     * a solution, some variables can be left unassigned. Still all hard constraints on assigned variables must be
    021     * satisfied. Similarly to backtracking based algorithms, this means that there are no violations of hard
    022     * constraints.
    023     * <br><br>
    024     * This search works in iterations. During each step, an unassigned or assigned variable is initially selected.
    025     * Typically an unassigned variable is chosen like in backtracking-based search. An assigned variable may be selected
    026     * when all variables are assigned but the solution is not good enough (for example, when there are still many
    027     * violations of soft constraints). Once a variable is selected, a value from its domain is chosen for assignment.
    028     * Even if the best value is selected (whatever “best” means), its assignment to the selected variable may cause some
    029     * hard conflicts with already assigned variables. Such conflicting variables are removed from the solution and become
    030     * unassigned. Finally, the selected value is assigned to the selected variable.
    031     * <br><br>
    032     * Algorithm schema:
    033     * <ul><code>
    034     * procedure ifs(initial)  // initial solution is the parameter <br>
    035     * &nbsp;&nbsp;iteration = 0;         // iteration counter <br>
    036     * &nbsp;&nbsp;current = initial;     // current (partial) feasible solution <br>
    037     * &nbsp;&nbsp;best = initial;        // best solution <br>
    038     * &nbsp;&nbsp;while canContinue(current, iteration) do <br>
    039     * &nbsp;&nbsp;&nbsp;&nbsp;iteration = iteration + 1; <br>
    040     * &nbsp;&nbsp;&nbsp;&nbsp;variable = selectVariable(current); <br>
    041     * &nbsp;&nbsp;&nbsp;&nbsp;value = selectValue(current, variable); <br>
    042     * &nbsp;&nbsp;&nbsp;&nbsp;UNASSIGN(current,  CONFLICTING_VARIABLES(current, variable, value)); <br>
    043     * &nbsp;&nbsp;&nbsp;&nbsp;ASSIGN(current, variable, value); <br>
    044     * &nbsp;&nbsp;&nbsp;&nbsp;if better(current, best) then best = current; <br>
    045     * &nbsp;&nbsp;end while <br>
    046     * &nbsp;&nbsp;return best;<br>
    047     * end procedure <br>
    048     * </code>
    049     * </ul><br>
    050     * The algorithm attempts to move from one (partial) feasible solution to another via repetitive assignment of a
    051     * selected value to a selected variable. During this search, the feasibility of all hard constraints in each
    052     * iteration step is enforced by unassigning the conflicting variables. The search is terminated when the requested
    053     * solution is found or when there is a timeout, expressed e.g., as a maximal number of iterations or available
    054     * time being reached. The best solution found is then returned.
    055     * <br><br>
    056     * The above algorithm schema is parameterized by several functions, namely:
    057     * <ul>
    058     * <li> the termination condition (function canContinue, see {@link TerminationCondition}),
    059     * <li> the solution comparator (function better, see {@link SolutionComparator}),
    060     * <li> the variable selection (function selectVariable, see {@link VariableSelection}) and
    061     * <li> the value selection (function selectValue, see {@link ValueSelection}).
    062     * </ul>
    063     * <br>
    064     * Usage:<ul><code>
    065     * DataProperties cfg = ToolBox.loadProperties(inputCfg); //input configuration<br>
    066     * Solver solver = new Solver(cfg);<br>
    067     * solver.setInitalSolution(model); //sets initial solution<br>
    068     * <br>
    069     * solver.start(); //server is executed in a thread<br>
    070     * <br>
    071     * try { //wait untill the server finishes<br>
    072     * &nbsp;&nbsp;solver.getSolverThread().join(); <br>
    073     * } catch (InterruptedException e) {} <br>
    074     * <br>
    075     * Solution solution = solver.lastSolution(); //last solution<br>
    076     * solution.restoreBest(); //restore best solution ever found<br>
    077     * </code></ul>
    078     * <br>
    079     * Solver's parameters:
    080     * <br>
    081     * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
    082     * <tr><td>General.SaveBestUnassigned</td><td>{@link Integer}</td><td>During the search, solution is saved when it is the best ever found solution and if the number of assigned variables is less or equal this parameter (if set to -1, the solution is always saved)</td></tr>
    083     * <tr><td>General.Seed</td><td>{@link Long}</td><td>If set, random number generator is initialized with this seed</td></tr>
    084     * <tr><td>General.SaveConfiguration</td><td>{@link Boolean}</td><td>If true, given configuration is stored into the output folder (during initialization of the solver, ${General.Output}/${General.ProblemName}.properties)</td></tr>
    085     * <tr><td>Solver.AutoConfigure</td><td>{@link Boolean}</td><td>If true, IFS Solver is configured according to the following parameters</td></tr>
    086     * <tr><td>Termination.Class</td><td>{@link String}</td><td>Fully qualified class name of the termination condition (see {@link TerminationCondition}, e.g. {@link GeneralTerminationCondition})</td></tr>
    087     * <tr><td>Comparator.Class</td><td>{@link String}</td><td>Fully qualified class name of the solution comparator (see {@link SolutionComparator}, e.g. {@link GeneralSolutionComparator})</td></tr>
    088     * <tr><td>Value.Class</td><td>{@link String}</td><td>Fully qualified class name of the value selection criterion (see {@link ValueSelection}, e.g. {@link GeneralValueSelection})</td></tr>
    089     * <tr><td>Variable.Class</td><td>{@link String}</td><td>Fully qualified class name of the variable selection criterion (see {@link VariableSelection}, e.g. {@link GeneralVariableSelection})</td></tr>
    090     * <tr><td>PerturbationCounter.Class</td><td>{@link String}</td><td>Fully qualified class name of the perturbation counter in case of solving minimal perturbation problem (see {@link PerturbationsCounter}, e.g. {@link DefaultPerturbationsCounter})</td></tr>
    091     * <tr><td>Extensions.Classes</td><td>{@link String}</td><td>Semi-colon separated list of fully qualified class names of IFS extensions (see {@link Extension}, e.g. {@link ConflictStatistics} or {@link MacPropagation})</td></tr>
    092     * </table>
    093     *
    094     * @see SolverListener
    095     * @see Model
    096     * @see Solution
    097     * @see TerminationCondition
    098     * @see SolutionComparator
    099     * @see PerturbationsCounter
    100     * @see VariableSelection
    101     * @see ValueSelection
    102     * @see Extension
    103     *
    104     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    105     * @version 1.0
    106    **/
    107
    108    public class Solver {
    109        /** log */
    110        protected static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(Solver.class);
    111        /** current solution */
    112        protected Solution iCurrentSolution = null;
    113        /** last solution (after IFS Solver finishes) */
    114        protected Solution iLastSolution = null;
    115
    116        /** solver status: done */
    117        protected boolean iDone = false;
    118        /** solver status: running */
    119        protected boolean iRunning = false;
    120        /** solver status: stopped */
    121        protected boolean iStop = false;
    122
    123        /** solver thread */
    124        protected SolverThread iSolverThread = null;
    125        /** configuration */
    126        private DataProperties iProperties = null;
    127
    128        private TerminationCondition iTerminationCondition = null;
    129        private SolutionComparator iSolutionComparator = null;
    130        private PerturbationsCounter iPerturbationsCounter = null;
    131        private ValueSelection iValueSelection = null;
    132        private VariableSelection iVariableSelection = null;
    133        private Vector iExtensions = new FastVector(5);
    134        private Vector iSolverListeners = new FastVector(5);
    135        private int iSaveBestUnassigned = 0;
    136
    137        /** Constructor.
    138         * @param properties input configuration
    139         */
    140        public Solver(DataProperties properties) {
    141            iProperties = properties;
    142
    143            long seed = properties.getPropertyLong( "General.Seed", System.currentTimeMillis());
    144            ToolBox.setSeed(seed);
    145
    146            iSaveBestUnassigned = properties.getPropertyInt( "General.SaveBestUnassigned", 0);
    147
    148            clearBest();
    149            if (iProperties.getPropertyBoolean("Solver.AutoConfigure",true)) {
    150                autoConfigure();
    151            }
    152        }
    153
    154        private boolean iValueExtraUsed = false;
    155        private boolean iVariableExtraUsed = false;
    156
    157        /** Sets termination condition */
    158        public void setTerminalCondition(TerminationCondition terminationCondition) {iTerminationCondition = terminationCondition; }
    159        /** Sets solution comparator */
    160        public void setSolutionComparator(SolutionComparator solutionComparator) {iSolutionComparator = solutionComparator; }
    161        /** Sets value selection criterion */
    162        public void setValueSelection(ValueSelection valueSelection) { iValueSelection = valueSelection; }
    163        /** Sets variable selection criterion */
    164        public void setVariableSelection(VariableSelection variableSelection) { iVariableSelection = variableSelection; }
    165        /** Sets perturbation counter (minimal perturbation problem) */
    166        public void setPerturbationsCounter(PerturbationsCounter perturbationsCounter) { iPerturbationsCounter = perturbationsCounter; }
    167        /** Add an IFS extension */
    168        public void addExtension(Extension extension) {
    169            if (extension.useValueExtra() && iValueExtraUsed) {
    170                sLogger.warn("Unable to add an extension "+extension+" -- value extra is already used.");
    171                return;
    172            }
    173            if (extension.useVariableExtra() && iVariableExtraUsed) {
    174                sLogger.warn("Unable to add extension "+extension+" -- variable extra is already used.");
    175                return;
    176            }
    177            iValueExtraUsed = iValueExtraUsed | extension.useValueExtra();
    178            iValueExtraUsed = iVariableExtraUsed | extension.useVariableExtra();
    179            iExtensions.addElement(extension);
    180        }
    181
    182        /** Returns termination condition */
    183        public TerminationCondition getTerminationCondition() { return iTerminationCondition; }
    184        /** Returns solution comparator */
    185        public SolutionComparator getSolutionComparator() { return iSolutionComparator; }
    186        /** Returns values selection criterion */
    187        public ValueSelection getValueSelection() { return iValueSelection; }
    188        /** Returns variable selection criterion */
    189        public VariableSelection getVariableSelection() { return iVariableSelection; }
    190        /** Returns perturbation counter (minimal perturbation problem) */
    191        public PerturbationsCounter getPerturbationsCounter() { return iPerturbationsCounter; }
    192        /** Returns list of all used extensions */
    193        public Vector getExtensions() { return iExtensions; }
    194
    195        /** Adds a solver listener */
    196        public void addSolverListener(SolverListener listener) {
    197            iSolverListeners.addElement(listener);
    198        }
    199        /** Removes a solver listener */
    200        public void removeSolverListener(SolverListener listener) {
    201            iSolverListeners.removeElement(listener);
    202        }
    203
    204        /** Returns configuration */
    205        public DataProperties getProperties() { return iProperties; }
    206
    207        /** Automatic configuratin of the solver -- when Solver.AutoConfigure is true */
    208        protected void autoConfigure() {
    209            try {
    210                boolean mpp = getProperties().getPropertyBoolean("General.MPP", false);
    211
    212                String terminationConditionClassName = getProperties().getProperty("Termination.Class",(mpp?"ifs.termination.MPPTerminationCondition":"ifs.termination.GeneralTerminationCondition"));
    213                sLogger.info("Using "+terminationConditionClassName);
    214                Class terminationConditionClass = Class.forName(terminationConditionClassName);
    215                Constructor terminationConditionConstructor = terminationConditionClass.getConstructor(new Class[]{DataProperties.class});
    216                setTerminalCondition((TerminationCondition)terminationConditionConstructor.newInstance(new Object[] {getProperties()}));
    217
    218                String solutionComparatorClassName = getProperties().getProperty("Comparator.Class",(mpp?"ifs.solution.MPPSolutionComparator":"ifs.solution.GeneralSolutionComparator"));
    219                sLogger.info("Using "+solutionComparatorClassName);
    220                Class solutionComparatorClass = Class.forName(solutionComparatorClassName);
    221                Constructor solutionComparatorConstructor = solutionComparatorClass.getConstructor(new Class[]{DataProperties.class});
    222                setSolutionComparator((SolutionComparator)solutionComparatorConstructor.newInstance(new Object[] {getProperties()}));
    223
    224                String valueSelectionClassName = getProperties().getProperty("Value.Class","ifs.heuristics.GeneralValueSelection");
    225                sLogger.info("Using "+valueSelectionClassName);
    226                Class valueSelectionClass = Class.forName(valueSelectionClassName);
    227                Constructor valueSelectionConstructor = valueSelectionClass.getConstructor(new Class[]{DataProperties.class});
    228                setValueSelection((ValueSelection)valueSelectionConstructor.newInstance(new Object[] {getProperties()}));
    229
    230                String variableSelectionClassName = getProperties().getProperty("Variable.Class","ifs.heuristics.GeneralVariableSelection");
    231                sLogger.info("Using "+variableSelectionClassName);
    232                Class variableSelectionClass = Class.forName(variableSelectionClassName);
    233                Constructor variableSelectionConstructor = variableSelectionClass.getConstructor(new Class[]{DataProperties.class});
    234                setVariableSelection((VariableSelection)variableSelectionConstructor.newInstance(new Object[] {getProperties()}));
    235
    236                String perturbationCounterClassName = getProperties().getProperty("PerturbationCounter.Class","ifs.perturbations.DefaultPerturbationsCounter");
    237                sLogger.info("Using "+perturbationCounterClassName);
    238                Class perturbationCounterClass = Class.forName(perturbationCounterClassName);
    239                Constructor perturbationCounterConstructor = perturbationCounterClass.getConstructor(new Class[]{DataProperties.class});
    240                setPerturbationsCounter((PerturbationsCounter)perturbationCounterConstructor.newInstance(new Object[] {getProperties()}));
    241
    242                String extensionClassNames = getProperties().getProperty("Extensions.Classes",null);
    243                if (extensionClassNames!=null) {
    244                    StringTokenizer extensionClassNameTokenizer = new StringTokenizer(extensionClassNames,";");
    245                    while (extensionClassNameTokenizer.hasMoreTokens()) {
    246                        String extensionClassName = extensionClassNameTokenizer.nextToken();
    247                        sLogger.info("Using "+extensionClassName);
    248                        Class extensionClass = Class.forName(extensionClassName);
    249                        Constructor extensionConstructor = extensionClass.getConstructor(new Class[]{Solver.class, DataProperties.class});
    250                        addExtension((Extension)extensionConstructor.newInstance(new Object[] {this, getProperties()}));
    251                    }
    252                }
    253            } catch (Exception e) {
    254                sLogger.error("Unable to autoconfigure solver.",e);
    255            }
    256        }
    257
    258        /** Clears best solution */
    259        public void clearBest() {
    260            if (iCurrentSolution!=null) iCurrentSolution.clearBest();
    261        }
    262
    263        /** Sets initial solution */
    264        public void setInitalSolution(Solution solution) {
    265            iCurrentSolution = solution;
    266        }
    267
    268        /** Sets initial solution */
    269        public void setInitalSolution(Model model) {
    270            iCurrentSolution = new Solution(model, 0, 0);
    271        }
    272
    273        /** Starts solver */
    274        public void start() {
    275            iSolverThread = new SolverThread();
    276            iSolverThread.start();
    277        }
    278
    279        /** Returns solver's thread */
    280        public Thread getSolverThread() {
    281            return iSolverThread;
    282        }
    283
    284        /** Initialization */
    285        public void init() {
    286            iStop = false;
    287            iDone = false;
    288            iRunning = false;
    289        }
    290
    291        /** Last solution (when solver finishes) */
    292        public Solution lastSolution() { return (iLastSolution==null?iCurrentSolution:iLastSolution); }
    293        /** Current solution (during the search) */
    294        public Solution currentSolution() { return iCurrentSolution; }
    295        /** Solver status: solver is done */
    296        public boolean isDone() { return iDone; }
    297        /** Solver status: solver is running */
    298        public boolean isRunning() { return iRunning; }
    299        /** Stops the running solver */
    300        public void stopSolver() { iStop = true; };
    301        /** Solver status: solver is stopped */
    302        public boolean isStopped() { return iStop; }
    303
    304        private void initSolver() {
    305            Progress.getInstance().setPhase("Initializing solver");
    306
    307            // register extensions
    308            for (Enumeration i=iExtensions.elements(); i.hasMoreElements(); ) {
    309                Extension extension = (Extension)i.nextElement();
    310                extension.register(iCurrentSolution.getModel());
    311            }
    312
    313            //register solution
    314            iCurrentSolution.init(Solver.this);
    315
    316            //register and intialize value selection
    317            getValueSelection().init(Solver.this);
    318
    319            //register and intialize value selection
    320            getVariableSelection().init(Solver.this);
    321
    322            //register and intialize perturbations counter
    323            if (getPerturbationsCounter()!=null) getPerturbationsCounter().init(Solver.this);
    324
    325            //save initial configuration
    326            if (iProperties.getPropertyBoolean("General.SaveConfiguration",false)) {
    327                try {
    328                    FileOutputStream f = new FileOutputStream(iProperties.getProperty("General.Output")+File.separator+iProperties.getProperty("General.ProblemName","ifs")+".properties");
    329                    iProperties.store(f, iProperties.getProperty("General.ProblemNameLong","Iterative Forward Search")+"  -- configuration file");
    330                    f.flush();f.close();
    331                } catch (Exception e) {
    332                    sLogger.error("Unable to store configuration file :-(", e);
    333                }
    334            }
    335        }
    336
    337        /** Solver thread */
    338        protected class SolverThread extends Thread {
    339            /** Solving rutine */
    340            public void run() {
    341                try {
    342                    // Sets thread name
    343                    setName("Solver");
    344
    345                    // Status
    346                    iStop = false; iDone = false; iRunning = true;
    347
    348                    // Initialization
    349                    Progress.getInstance().setStatus("Solving");
    350                    initSolver();
    351                    double startTime = JProf.currentTimeSec();
    352                    if (iCurrentSolution.getBestInfo()==null) {
    353                        Progress.getInstance().setPhase("Searching for initial solution ...",iCurrentSolution.getModel().variables().size());
    354                    } else {
    355                        Progress.getInstance().setPhase("Improving found solution ...");
    356                    }
    357                    long prog = 9999;
    358                    sLogger.info("Initial solution:"+ToolBox.dict2string(iCurrentSolution.getInfo(),1));
    359                    if ((iSaveBestUnassigned<0 || iSaveBestUnassigned>=iCurrentSolution.getModel().unassignedVariables().size()) && (iCurrentSolution.getBestInfo()==null || getSolutionComparator().isBetterThanBestSolution(iCurrentSolution))) {
    360                        if (iCurrentSolution.getModel().unassignedVariables().isEmpty())
    361                            sLogger.info("Complete solution "+ToolBox.dict2string(iCurrentSolution.getInfo(),1)+" was found.");
    362                        synchronized (iCurrentSolution) {
    363                            iCurrentSolution.saveBest();
    364                        }
    365                    }
    366
    367                    // Iterations: until solver can continue
    368                    while (!iStop && getTerminationCondition().canContinue(iCurrentSolution)) {
    369                        // Variable selection
    370                        Variable variable = getVariableSelection().selectVariable(iCurrentSolution);
    371                        for (Enumeration i=iSolverListeners.elements();i.hasMoreElements();)
    372                            if (!((SolverListener)i.nextElement()).variableSelected(iCurrentSolution.getIteration(), variable)) continue;
    373                        if (variable == null) {
    374                            sLogger.warn("No variable selected.");
    375                        }
    376                        if (variable != null && variable.values().isEmpty()) {
    377                            sLogger.error("Variable "+variable.getName()+" has no values.");
    378                            continue;
    379                        }
    380
    381                        // Value selection
    382                        Value value = getValueSelection().selectValue(iCurrentSolution, variable);
    383                        for (Enumeration i=iSolverListeners.elements();i.hasMoreElements();)
    384                            if (!((SolverListener)i.nextElement()).valueSelected(iCurrentSolution.getIteration(), variable, value)) continue;
    385                        if (variable == null) {
    386                            sLogger.warn("No value selected for variable "+variable+".");
    387                        }
    388
    389                        // Assign selected value to the selected variable
    390                        synchronized (iCurrentSolution) {
    391                            if (value!=null) variable.assign(iCurrentSolution.getIteration(), value); else variable.unassign(iCurrentSolution.getIteration());
    392                            iCurrentSolution.update(JProf.currentTimeSec()-startTime);
    393                        }
    394
    395                        // Check if the solution is the best ever found one
    396                        if ((iSaveBestUnassigned<0 || iSaveBestUnassigned>=iCurrentSolution.getModel().unassignedVariables().size()) && (iCurrentSolution.getBestInfo()==null || getSolutionComparator().isBetterThanBestSolution(iCurrentSolution))) {
    397                            if (iCurrentSolution.getModel().unassignedVariables().isEmpty())
    398                                sLogger.info("Complete solution "+ToolBox.dict2string(iCurrentSolution.getInfo(),1)+" was found.");
    399                            synchronized (iCurrentSolution) {
    400                                iCurrentSolution.saveBest();
    401                            }
    402                        }
    403
    404                        // Increment progress bar
    405                        if (iCurrentSolution.getBestInfo()!=null && iCurrentSolution.getModel().getBestUnassignedVariables()==0) {
    406                            prog++;
    407                            if (prog == 10000) {
    408                                Progress.getInstance().setPhase("Improving found solution ...");
    409                                prog=0;
    410                            } else {
    411                                Progress.getInstance().setProgress(prog/100);
    412                            }
    413                        } else if ((iCurrentSolution.getBestInfo()==null || iCurrentSolution.getModel().getBestUnassignedVariables()>0) && (iCurrentSolution.getModel().variables().size()-iCurrentSolution.getModel().unassignedVariables().size())>Progress.getInstance().getProgress()) {
    414                            Progress.getInstance().setProgress(iCurrentSolution.getModel().variables().size()-iCurrentSolution.getModel().unassignedVariables().size());
    415                        }
    416
    417                    }
    418
    419                    // Finalization
    420                    iLastSolution = iCurrentSolution;
    421                    if (!iStop) {
    422                        Progress.getInstance().setPhase("Done",1); Progress.getInstance().incProgress();
    423                    }
    424
    425                    //Update status
    426                    iDone = true; iRunning = false; iSolverThread=null;
    427
    428                    sLogger.debug("Solver stoped.");
    429                } catch (Exception ex) {
    430                    sLogger.error(ex.getMessage(),ex);
    431                }
    432            }
    433        }
    434
    435    }