001 package net.sf.cpsolver.ifs.solver;
002
003
004 import java.io.*;
005 import java.util.*;
006 import java.lang.reflect.*;
007
008 import net.sf.cpsolver.ifs.extension.*;
009 import net.sf.cpsolver.ifs.heuristics.*;
010 import net.sf.cpsolver.ifs.model.*;
011 import net.sf.cpsolver.ifs.perturbations.*;
012 import net.sf.cpsolver.ifs.solution.*;
013 import net.sf.cpsolver.ifs.termination.*;
014 import net.sf.cpsolver.ifs.util.*;
015
016 /**
017 * IFS Solver.
018 * <br><br>
019 * The iterative forward search (IFS) algorithm is based on ideas of local search methods. However, in contrast to
020 * classical local search techniques, it operates over feasible, though not necessarily complete solutions. In such
021 * a solution, some variables can be left unassigned. Still all hard constraints on assigned variables must be
022 * satisfied. Similarly to backtracking based algorithms, this means that there are no violations of hard
023 * constraints.
024 * <br><br>
025 * This search works in iterations. During each step, an unassigned or assigned variable is initially selected.
026 * Typically an unassigned variable is chosen like in backtracking-based search. An assigned variable may be selected
027 * when all variables are assigned but the solution is not good enough (for example, when there are still many
028 * violations of soft constraints). Once a variable is selected, a value from its domain is chosen for assignment.
029 * Even if the best value is selected (whatever “best” means), its assignment to the selected variable may cause some
030 * hard conflicts with already assigned variables. Such conflicting variables are removed from the solution and become
031 * unassigned. Finally, the selected value is assigned to the selected variable.
032 * <br><br>
033 * Algorithm schema:
034 * <ul><code>
035 * procedure net.sf.cpsolver.ifs(initial) // initial solution is the parameter <br>
036 * iteration = 0; // iteration counter <br>
037 * current = initial; // current (partial) feasible solution <br>
038 * best = initial; // best solution <br>
039 * while canContinue(current, iteration) do <br>
040 * iteration = iteration + 1; <br>
041 * variable = selectVariable(current); <br>
042 * value = selectValue(current, variable); <br>
043 * UNASSIGN(current, CONFLICTING_VARIABLES(current, variable, value)); <br>
044 * ASSIGN(current, variable, value); <br>
045 * if better(current, best) then best = current; <br>
046 * end while <br>
047 * return best;<br>
048 * end procedure <br>
049 * </code>
050 * </ul><br>
051 * The algorithm attempts to move from one (partial) feasible solution to another via repetitive assignment of a
052 * selected value to a selected variable. During this search, the feasibility of all hard constraints in each
053 * iteration step is enforced by unassigning the conflicting variables. The search is terminated when the requested
054 * solution is found or when there is a timeout, expressed e.g., as a maximal number of iterations or available
055 * time being reached. The best solution found is then returned.
056 * <br><br>
057 * The above algorithm schema is parameterized by several functions, namely:
058 * <ul>
059 * <li> the termination condition (function canContinue, see {@link TerminationCondition}),
060 * <li> the solution comparator (function better, see {@link SolutionComparator}),
061 * <li> the neighbour selection (function selectNeighbour, see {@link NeighbourSelection}) and
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 * 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>Neighbour.Class</td><td>{@link String}</td><td>Fully qualified class name of the neighbour selection criterion (see {@link NeighbourSelection}, e.g. {@link StandardNeighbourSelection})</td></tr>
089 * <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>
090 * <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>
091 * </table>
092 *
093 * @see SolverListener
094 * @see Model
095 * @see Solution
096 * @see TerminationCondition
097 * @see SolutionComparator
098 * @see PerturbationsCounter
099 * @see VariableSelection
100 * @see ValueSelection
101 * @see Extension
102 *
103 * @version
104 * IFS 1.1 (Iterative Forward Search)<br>
105 * Copyright (C) 2006 Tomáš Müller<br>
106 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
107 * Lazenska 391, 76314 Zlin, Czech Republic<br>
108 * <br>
109 * This library is free software; you can redistribute it and/or
110 * modify it under the terms of the GNU Lesser General Public
111 * License as published by the Free Software Foundation; either
112 * version 2.1 of the License, or (at your option) any later version.
113 * <br><br>
114 * This library is distributed in the hope that it will be useful,
115 * but WITHOUT ANY WARRANTY; without even the implied warranty of
116 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
117 * Lesser General Public License for more details.
118 * <br><br>
119 * You should have received a copy of the GNU Lesser General Public
120 * License along with this library; if not, write to the Free Software
121 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
122 **/
123
124 public class Solver {
125 public static int THREAD_PRIORITY = 3;
126 /** log */
127 protected static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(Solver.class);
128 /** current solution */
129 protected Solution iCurrentSolution = null;
130 /** last solution (after IFS Solver finishes) */
131 protected Solution iLastSolution = null;
132
133 /** solver is stopped */
134 protected boolean iStop = false;
135
136 /** solver thread */
137 protected SolverThread iSolverThread = null;
138 /** configuration */
139 private DataProperties iProperties = null;
140
141 private TerminationCondition iTerminationCondition = null;
142 private SolutionComparator iSolutionComparator = null;
143 private PerturbationsCounter iPerturbationsCounter = null;
144 private NeighbourSelection iNeighbourSelection = null;
145 private Vector iExtensions = new FastVector(5);
146 private Vector iSolverListeners = new FastVector(5);
147 private int iSaveBestUnassigned = 0;
148
149 private boolean iUpdateProgress = true;
150
151 private Progress iProgress;
152
153 /** Constructor.
154 * @param properties input configuration
155 */
156 public Solver(DataProperties properties) {
157 iProperties = properties;
158 }
159
160 /** Dispose solver */
161 public void dispose() {
162 iExtensions.clear();
163 iSolverListeners.clear();
164 iTerminationCondition = null;
165 iSolutionComparator = null;
166 iPerturbationsCounter = null;
167 iNeighbourSelection = null;
168 }
169
170 private boolean iValueExtraUsed = false;
171 private boolean iVariableExtraUsed = false;
172
173 /** Sets termination condition */
174 public void setTerminalCondition(TerminationCondition terminationCondition) {iTerminationCondition = terminationCondition; }
175 /** Sets solution comparator */
176 public void setSolutionComparator(SolutionComparator solutionComparator) {iSolutionComparator = solutionComparator; }
177 /** Sets neighbour selection criterion */
178 public void setNeighbourSelection(NeighbourSelection neighbourSelection) { iNeighbourSelection = neighbourSelection; }
179 /** Sets perturbation counter (minimal perturbation problem) */
180 public void setPerturbationsCounter(PerturbationsCounter perturbationsCounter) { iPerturbationsCounter = perturbationsCounter; }
181 /** Add an IFS extension */
182 public void addExtension(Extension extension) {
183 if (extension.useValueExtra() && iValueExtraUsed) {
184 sLogger.warn("Unable to add an extension "+extension+" -- value extra is already used.");
185 return;
186 }
187 if (extension.useVariableExtra() && iVariableExtraUsed) {
188 sLogger.warn("Unable to add extension "+extension+" -- variable extra is already used.");
189 return;
190 }
191 iValueExtraUsed = iValueExtraUsed | extension.useValueExtra();
192 iValueExtraUsed = iVariableExtraUsed | extension.useVariableExtra();
193 iExtensions.addElement(extension);
194 }
195
196 /** Returns termination condition */
197 public TerminationCondition getTerminationCondition() { return iTerminationCondition; }
198 /** Returns solution comparator */
199 public SolutionComparator getSolutionComparator() { return iSolutionComparator; }
200 /** Returns neighbour selection criterion */
201 public NeighbourSelection getNeighbourSelection() { return iNeighbourSelection; }
202 /** Returns perturbation counter (minimal perturbation problem) */
203 public PerturbationsCounter getPerturbationsCounter() { return iPerturbationsCounter; }
204 /** Returns list of all used extensions */
205 public Vector getExtensions() { return iExtensions; }
206
207 /** Adds a solver listener */
208 public void addSolverListener(SolverListener listener) {
209 iSolverListeners.addElement(listener);
210 }
211 /** Removes a solver listener */
212 public void removeSolverListener(SolverListener listener) {
213 iSolverListeners.removeElement(listener);
214 }
215 /** Registered solver listeners */
216 public Vector getSolverListeners() {
217 return iSolverListeners;
218 }
219
220 /** Returns configuration */
221 public DataProperties getProperties() { return iProperties; }
222
223 /** Automatic configuratin of the solver -- when Solver.AutoConfigure is true */
224 protected void autoConfigure() {
225 try {
226 boolean mpp = getProperties().getPropertyBoolean("General.MPP", false);
227
228 String terminationConditionClassName = getProperties().getProperty("Termination.Class",(mpp?"net.sf.cpsolver.ifs.termination.MPPTerminationCondition":"net.sf.cpsolver.ifs.termination.GeneralTerminationCondition"));
229 sLogger.info("Using "+terminationConditionClassName);
230 Class terminationConditionClass = Class.forName(terminationConditionClassName);
231 Constructor terminationConditionConstructor = terminationConditionClass.getConstructor(new Class[]{DataProperties.class});
232 setTerminalCondition((TerminationCondition)terminationConditionConstructor.newInstance(new Object[] {getProperties()}));
233
234 String solutionComparatorClassName = getProperties().getProperty("Comparator.Class",(mpp?"net.sf.cpsolver.ifs.solution.MPPSolutionComparator":"net.sf.cpsolver.ifs.solution.GeneralSolutionComparator"));
235 sLogger.info("Using "+solutionComparatorClassName);
236 Class solutionComparatorClass = Class.forName(solutionComparatorClassName);
237 Constructor solutionComparatorConstructor = solutionComparatorClass.getConstructor(new Class[]{DataProperties.class});
238 setSolutionComparator((SolutionComparator)solutionComparatorConstructor.newInstance(new Object[] {getProperties()}));
239
240 String neighbourSelectionClassName = getProperties().getProperty("Neighbour.Class","net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection");
241 sLogger.info("Using "+neighbourSelectionClassName);
242 Class neighbourSelectionClass = Class.forName(neighbourSelectionClassName);
243 Constructor neighbourSelectionConstructor = neighbourSelectionClass.getConstructor(new Class[]{DataProperties.class});
244 setNeighbourSelection((NeighbourSelection)neighbourSelectionConstructor.newInstance(new Object[] {getProperties()}));
245
246 String perturbationCounterClassName = getProperties().getProperty("PerturbationCounter.Class","net.sf.cpsolver.ifs.perturbations.DefaultPerturbationsCounter");
247 sLogger.info("Using "+perturbationCounterClassName);
248 Class perturbationCounterClass = Class.forName(perturbationCounterClassName);
249 Constructor perturbationCounterConstructor = perturbationCounterClass.getConstructor(new Class[]{DataProperties.class});
250 setPerturbationsCounter((PerturbationsCounter)perturbationCounterConstructor.newInstance(new Object[] {getProperties()}));
251
252 for (Enumeration i=iExtensions.elements(); i.hasMoreElements(); ) {
253 Extension extension = (Extension)i.nextElement();
254 extension.unregister(iCurrentSolution.getModel());
255 }
256 iExtensions.clear();
257 String extensionClassNames = getProperties().getProperty("Extensions.Classes",null);
258 if (extensionClassNames!=null) {
259 StringTokenizer extensionClassNameTokenizer = new StringTokenizer(extensionClassNames,";");
260 while (extensionClassNameTokenizer.hasMoreTokens()) {
261 String extensionClassName = extensionClassNameTokenizer.nextToken();
262 sLogger.info("Using "+extensionClassName);
263 Class extensionClass = Class.forName(extensionClassName);
264 Constructor extensionConstructor = extensionClass.getConstructor(new Class[]{Solver.class, DataProperties.class});
265 addExtension((Extension)extensionConstructor.newInstance(new Object[] {this, getProperties()}));
266 }
267 }
268 } catch (Exception e) {
269 sLogger.error("Unable to autoconfigure solver.",e);
270 }
271 }
272
273 /** Clears best solution */
274 public void clearBest() {
275 if (iCurrentSolution!=null) iCurrentSolution.clearBest();
276 }
277
278 /** Sets initial solution */
279 public void setInitalSolution(Solution solution) {
280 iCurrentSolution = solution;
281 iLastSolution = null;
282 }
283
284 /** Sets initial solution */
285 public void setInitalSolution(Model model) {
286 iCurrentSolution = new Solution(model, 0, 0);
287 iLastSolution = null;
288 }
289
290 /** Starts solver */
291 public void start() {
292 iSolverThread = new SolverThread();
293 iSolverThread.setPriority(THREAD_PRIORITY);
294 iSolverThread.start();
295 }
296
297 /** Returns solver's thread */
298 public Thread getSolverThread() {
299 return iSolverThread;
300 }
301
302 /** Initialization */
303 public void init() {
304 }
305
306 /** True, when solver should update progress (see {@link Progress}) */
307 private boolean isUpdateProgress() {
308 return iUpdateProgress;
309 }
310
311 /** True, when solver should update progress (see {@link Progress}) */
312 public void setUpdateProgress(boolean updateProgress) {
313 iUpdateProgress = updateProgress;
314 }
315
316 /** Last solution (when solver finishes) */
317 public Solution lastSolution() { return (iLastSolution==null?iCurrentSolution:iLastSolution); }
318 /** Current solution (during the search) */
319 public Solution currentSolution() { return iCurrentSolution; }
320
321 public void initSolver() {
322 long seed = getProperties().getPropertyLong( "General.Seed", System.currentTimeMillis());
323 ToolBox.setSeed(seed);
324
325 iSaveBestUnassigned = getProperties().getPropertyInt( "General.SaveBestUnassigned", 0);
326
327 clearBest();
328 if (iProperties.getPropertyBoolean("Solver.AutoConfigure",true)) {
329 autoConfigure();
330 }
331
332 // register extensions
333 for (Enumeration i=iExtensions.elements(); i.hasMoreElements(); ) {
334 Extension extension = (Extension)i.nextElement();
335 extension.register(iCurrentSolution.getModel());
336 }
337
338 //register solution
339 iCurrentSolution.init(Solver.this);
340
341 //register and intialize neighbour selection
342 getNeighbourSelection().init(Solver.this);
343
344 //register and intialize perturbations counter
345 if (getPerturbationsCounter()!=null) getPerturbationsCounter().init(Solver.this);
346
347 //save initial configuration
348 if (iProperties.getPropertyBoolean("General.SaveConfiguration",false)) {
349 FileOutputStream f = null;
350 try {
351 f = new FileOutputStream(iProperties.getProperty("General.Output")+File.separator+iProperties.getProperty("General.ProblemName","ifs")+".properties");
352 iProperties.store(f, iProperties.getProperty("General.ProblemNameLong","Iterative Forward Search")+" -- configuration file");
353 f.flush();f.close(); f = null;
354 } catch (Exception e) {
355 sLogger.error("Unable to store configuration file :-(", e);
356 } finally {
357 try {
358 if (f!=null) f.close();
359 } catch (IOException e) {}
360 }
361 }
362 }
363
364 /** Stop running solver */
365 public void stopSolver() {
366 if (getSolverThread()!=null) {
367 iStop = true;
368 try {
369 getSolverThread().join();
370 } catch (InterruptedException ex) {}
371 }
372 }
373 /** True, if the solver is running */
374 public boolean isRunning() {
375 return (getSolverThread()!=null);
376 }
377 /** Called when the solver is stopped */
378 protected void onStop() {}
379 /** Called when the solver is started */
380 protected void onStart() {}
381 /** Called when the solver is finished */
382 protected void onFinish() {}
383 /** Called when the solver fails */
384 protected void onFailure() {}
385
386 /** Called in each iteration, after a neighbour is assigned */
387 protected void onAssigned(double startTime) {}
388
389 /** Solver thread */
390 protected class SolverThread extends Thread {
391
392 /** Solving rutine */
393 public void run() {
394 try {
395 iStop = false;
396 // Sets thread name
397 setName("Solver");
398
399 // Initialization
400 iProgress = Progress.getInstance(iCurrentSolution.getModel());
401 iProgress.setStatus("Solving problem ...");
402 iProgress.setPhase("Initializing solver");
403 initSolver();
404 onStart();
405
406 double startTime = JProf.currentTimeSec();
407 if (isUpdateProgress()) {
408 if (iCurrentSolution.getBestInfo()==null) {
409 iProgress.setPhase("Searching for initial solution ...",iCurrentSolution.getModel().variables().size());
410 } else {
411 iProgress.setPhase("Improving found solution ...");
412 }
413 }
414 long prog = 9999;
415 sLogger.info("Initial solution:"+ToolBox.dict2string(iCurrentSolution.getInfo(),1));
416 if ((iSaveBestUnassigned<0 || iSaveBestUnassigned>=iCurrentSolution.getModel().nrUnassignedVariables()) && (iCurrentSolution.getBestInfo()==null || getSolutionComparator().isBetterThanBestSolution(iCurrentSolution))) {
417 if (iCurrentSolution.getModel().nrUnassignedVariables()==0)
418 sLogger.info("Complete solution "+ToolBox.dict2string(iCurrentSolution.getInfo(),1)+" was found.");
419 synchronized (iCurrentSolution) {
420 iCurrentSolution.saveBest();
421 }
422 }
423
424 if (iCurrentSolution.getModel().variables().isEmpty()) {
425 iProgress.error("Nothing to solve.");
426 iStop=true;
427 }
428
429 // Iterations: until solver can continue
430 while (!iStop && getTerminationCondition().canContinue(iCurrentSolution)) {
431 // Neighbour selection
432 Neighbour neighbour = getNeighbourSelection().selectNeighbour(iCurrentSolution);
433 for (Enumeration i=iSolverListeners.elements();i.hasMoreElements();)
434 if (!((SolverListener)i.nextElement()).neighbourSelected(iCurrentSolution.getIteration(), neighbour)) {
435 neighbour=null; continue;
436 }
437 if (neighbour==null) {
438 sLogger.debug("No neighbour selected.");
439 synchronized (iCurrentSolution) { //still update the solution (increase iteration etc.)
440 iCurrentSolution.update(JProf.currentTimeSec()-startTime);
441 }
442 continue;
443 }
444
445 // Assign selected value to the selected variable
446 synchronized (iCurrentSolution) {
447 neighbour.assign(iCurrentSolution.getIteration());
448 iCurrentSolution.update(JProf.currentTimeSec()-startTime);
449 }
450
451 onAssigned(startTime);
452
453 // Check if the solution is the best ever found one
454 if ((iSaveBestUnassigned<0 || iSaveBestUnassigned>=iCurrentSolution.getModel().nrUnassignedVariables()) && (iCurrentSolution.getBestInfo()==null || getSolutionComparator().isBetterThanBestSolution(iCurrentSolution))) {
455 if (iCurrentSolution.getModel().nrUnassignedVariables()==0) {
456 iProgress.debug("Complete solution of value "+iCurrentSolution.getModel().getTotalValue()+" was found.");
457 }
458 synchronized (iCurrentSolution) {
459 iCurrentSolution.saveBest();
460 }
461 }
462
463 // Increment progress bar
464 if (isUpdateProgress()) {
465 if (iCurrentSolution.getBestInfo()!=null && iCurrentSolution.getModel().getBestUnassignedVariables()==0) {
466 prog++;
467 if (prog == 10000) {
468 iProgress.setPhase("Improving found solution ...");
469 prog=0;
470 } else {
471 iProgress.setProgress(prog/100);
472 }
473 } else if ((iCurrentSolution.getBestInfo()==null || iCurrentSolution.getModel().getBestUnassignedVariables()>0) && (iCurrentSolution.getModel().variables().size()-iCurrentSolution.getModel().nrUnassignedVariables())>iProgress.getProgress()) {
474 iProgress.setProgress(iCurrentSolution.getModel().variables().size()-iCurrentSolution.getModel().nrUnassignedVariables());
475 }
476 }
477
478 }
479
480 // Finalization
481 iLastSolution = iCurrentSolution;
482
483
484 iProgress.setPhase("Done",1); iProgress.incProgress();
485
486 iSolverThread=null;
487 if (iStop) {
488 sLogger.debug("Solver stopped.");
489 iProgress.setStatus("Solver stopped.");
490 onStop();
491 } else {
492 sLogger.debug("Solver done.");
493 iProgress.setStatus("Solver done.");
494 onFinish();
495 }
496 } catch (Exception ex) {
497 sLogger.error(ex.getMessage(),ex);
498 iProgress.fatal("Solver failed, reason:"+ex.getMessage(),ex);
499 iProgress.setStatus("Solver failed.");
500 onFailure();
501 }
502 iSolverThread=null;
503 }
504 }
505
506 }