001package org.cpsolver.ifs.solution; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.List; 006import java.util.Locale; 007import java.util.Map; 008import java.util.concurrent.locks.ReentrantReadWriteLock; 009 010import org.cpsolver.coursett.criteria.TimetablingCriterion; 011import org.cpsolver.ifs.assignment.Assignment; 012import org.cpsolver.ifs.model.Model; 013import org.cpsolver.ifs.model.Value; 014import org.cpsolver.ifs.model.Variable; 015import org.cpsolver.ifs.perturbations.PerturbationsCounter; 016import org.cpsolver.ifs.solver.Solver; 017 018 019/** 020 * Generic solution. <br> 021 * <br> 022 * It consist from the model and information about current iteration and 023 * solution time. 024 * 025 * @see Model 026 * @see org.cpsolver.ifs.solver.Solver 027 * 028 * @version IFS 1.3 (Iterative Forward Search)<br> 029 * Copyright (C) 2006 - 2014 Tomas Muller<br> 030 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 031 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 032 * <br> 033 * This library is free software; you can redistribute it and/or modify 034 * it under the terms of the GNU Lesser General Public License as 035 * published by the Free Software Foundation; either version 3 of the 036 * License, or (at your option) any later version. <br> 037 * <br> 038 * This library is distributed in the hope that it will be useful, but 039 * WITHOUT ANY WARRANTY; without even the implied warranty of 040 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 041 * Lesser General Public License for more details. <br> 042 * <br> 043 * You should have received a copy of the GNU Lesser General Public 044 * License along with this library; if not see 045 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 046 * 047 * @param <V> Variable 048 * @param <T> Value 049 */ 050public class Solution<V extends Variable<V, T>, T extends Value<V, T>> { 051 private static java.text.DecimalFormat sTimeFormat = new java.text.DecimalFormat("0.00", new java.text.DecimalFormatSymbols(Locale.US)); 052 053 private Model<V, T> iModel; 054 private Assignment<V, T> iAssignment; 055 private long iIteration = 0; 056 private long iFailedIterations = 0; 057 private double iTime = 0.0; 058 059 private Map<String, String> iBestInfo = null; 060 private long iBestIteration = -1; 061 private long iBestFailedIterations = -1; 062 private double iBestTime = -1; 063 private double iBestPerturbationsPenaly = -1.0; 064 private int iBestIndex = -1; 065 066 private List<SolutionListener<V, T>> iSolutionListeners = new ArrayList<SolutionListener<V, T>>(); 067 private PerturbationsCounter<V, T> iPerturbationsCounter = null; 068 private final ReentrantReadWriteLock iLock = new ReentrantReadWriteLock(); 069 070 /** Constructor 071 * @param model problem model 072 **/ 073 @Deprecated 074 public Solution(Model<V, T> model) { 075 this(model, model.getDefaultAssignment(), 0, 0.0); 076 } 077 078 /** Constructor 079 * @param model problem model 080 * @param assignment current assignment 081 **/ 082 public Solution(Model<V, T> model, Assignment<V, T> assignment) { 083 this(model, assignment, 0, 0.0); 084 } 085 086 /** Constructor 087 * @param model problem model 088 * @param assignment current assignment 089 * @param iteration current iteration 090 * @param time current solver time 091 **/ 092 public Solution(Model<V, T> model, Assignment<V, T> assignment, long iteration, double time) { 093 iModel = model; 094 iAssignment = assignment; 095 iIteration = iteration; 096 iTime = time; 097 } 098 099 /** Current iteration 100 * @return current iteration 101 **/ 102 public long getIteration() { 103 return iIteration; 104 } 105 106 /** Number of failed iterations (i.e., number of calls {@link Solution#update(double, boolean)} with false success) 107 * @return number of failed iterations 108 **/ 109 public long getFailedIterations() { 110 return iFailedIterations; 111 } 112 113 /** Number of failed iterations (i.e., number of calls {@link Solution#update(double, boolean)} with false success) in the best solution 114 * @return number of failed iterations in the best solution 115 **/ 116 public long getBestFailedIterations() { 117 return (iBestIteration < 0 ? getFailedIterations() : iBestFailedIterations); 118 } 119 120 /** The model associated with the solution 121 * @return problem model 122 **/ 123 public Model<V, T> getModel() { 124 return iModel; 125 } 126 127 /** The assignment associated with this solution 128 * @return current assignment 129 **/ 130 public Assignment<V, T> getAssignment() { 131 return iAssignment; 132 } 133 134 /** Set a new assignment 135 * @param assignment current assignment 136 **/ 137 public void setAssignment(Assignment<V, T> assignment) { 138 iAssignment = assignment; 139 } 140 141 /** Current solution time (time in seconds from the start of the solver) 142 * @return solver time 143 **/ 144 public double getTime() { 145 return iTime; 146 } 147 148 /** Update time, increment current iteration 149 * @param time updated solver time 150 * @param success true if the last iteration was successful 151 **/ 152 public void update(double time, boolean success) { 153 iLock.writeLock().lock(); 154 try { 155 iTime = time; 156 iIteration++; 157 if (!success) iFailedIterations ++; 158 for (SolutionListener<V, T> listener : iSolutionListeners) 159 listener.solutionUpdated(this); 160 } finally { 161 iLock.writeLock().unlock(); 162 } 163 } 164 165 /** Update time, increment current iteration 166 * @param time updated solver time 167 **/ 168 public void update(double time) { 169 update(time, true); 170 } 171 172 /** Initialization 173 * @param solver current solver 174 **/ 175 public void init(Solver<V, T> solver) { 176 iIteration = 0; 177 iFailedIterations = 0; 178 iTime = 0; 179 if (iModel != null) 180 iModel.init(solver); 181 iPerturbationsCounter = solver.getPerturbationsCounter(); 182 } 183 184 /** 185 * String representation -- returns a list of values of objective criteria 186 * @return comma separated string of {@link TimetablingCriterion#toString(Assignment)} 187 */ 188 @Override 189 public String toString() { 190 return getModel().toString(getAssignment()) + (getFailedIterations() > 0 ? ", F:" + sTimeFormat.format(100.0 * getFailedIterations() / getIteration()) + "%" : ""); 191 } 192 193 /** 194 * Solution information. It consists from info from the model which is 195 * associated with the solution, time, iteration, speed and infos from all 196 * solution listeners. 197 * @return info table 198 */ 199 public Map<String, String> getInfo() { 200 Map<String, String> ret = getModel().getInfo(iAssignment); 201 if (getPerturbationsCounter() != null) 202 getPerturbationsCounter().getInfo(getAssignment(), getModel(), ret); 203 ret.put("Time", sTimeFormat.format(getTime() / 60.0) + " min"); 204 ret.put("Iteration", getIteration() + (getFailedIterations() > 0 ? " (" + sTimeFormat.format(100.0 * getFailedIterations() / getIteration())+ "% failed)" : "")); 205 if (getTime() > 0) 206 ret.put("Speed", sTimeFormat.format((getIteration()) / getTime()) + " it/s"); 207 for (SolutionListener<V, T> listener : iSolutionListeners) 208 listener.getInfo(this, ret); 209 return ret; 210 } 211 212 /** 213 * Extended solution information. Similar to {@link Solution#getInfo()}, but 214 * some more information (that is more expensive to compute) might be added. 215 * Also extended model information is added (see 216 * {@link Model#getExtendedInfo(Assignment)}) into the resultant table. 217 * @return extended info table 218 */ 219 public Map<String, String> getExtendedInfo() { 220 Map<String, String> ret = getModel().getExtendedInfo(iAssignment); 221 if (getPerturbationsCounter() != null) 222 getPerturbationsCounter().getInfo(getAssignment(), getModel(), ret); 223 ret.put("Time", sTimeFormat.format(getTime() / 60.0) + " min"); 224 ret.put("Iteration", getIteration() + (getFailedIterations() > 0 ? " (" + sTimeFormat.format(100.0 * getFailedIterations() / getIteration())+ "% failed)" : "")); 225 if (getTime() > 0) 226 ret.put("Speed", sTimeFormat.format((getIteration()) / getTime()) + " it/s"); 227 for (SolutionListener<V, T> listener : iSolutionListeners) 228 listener.getInfo(this, ret); 229 return ret; 230 } 231 232 /** 233 * Solution information. It consists from info from the model which is 234 * associated with the solution, time, iteration, speed and infos from all 235 * solution listeners. Only variables from the given set are included. 236 * @param variables sub-problem 237 * @return info table 238 */ 239 public Map<String, String> getInfo(Collection<V> variables) { 240 Map<String, String> ret = getModel().getInfo(iAssignment, variables); 241 if (getPerturbationsCounter() != null) 242 getPerturbationsCounter().getInfo(getAssignment(), getModel(), ret, variables); 243 ret.put("Time", sTimeFormat.format(getTime()) + " sec"); 244 ret.put("Iteration", String.valueOf(getIteration())); 245 if (getTime() > 0) 246 ret.put("Speed", sTimeFormat.format((getIteration()) / getTime()) + " it/s"); 247 for (SolutionListener<V, T> listener : iSolutionListeners) 248 listener.getInfo(this, ret, variables); 249 return ret; 250 } 251 252 /** Info of the best ever found solution 253 * @return info table of the best solution 254 **/ 255 public Map<String, String> getBestInfo() { 256 return iBestInfo; 257 } 258 259 /** Iteration when the best ever found solution was found 260 * @return iteration of the best solution 261 **/ 262 public long getBestIteration() { 263 return (iBestIteration < 0 ? getIteration() : iBestIteration); 264 } 265 266 /** Solution time when the best ever found solution was found 267 * @return solver time of the best solution 268 **/ 269 public double getBestTime() { 270 return (iBestTime < 0 ? getTime() : iBestTime); 271 } 272 273 /** 274 * Returns true, if all variables of the best ever solution found are 275 * assigned 276 * @return true if the best solution has all the variables assigned 277 */ 278 public boolean isBestComplete() { 279 return getModel().getBestUnassignedVariables() == 0; 280 } 281 282 /** 283 * Index of the best assignment. 284 * @return {@link Assignment#getIndex()} of the best saved solution 285 */ 286 public int getBestIndex() { 287 return iBestIndex; 288 } 289 290 /** 291 * Total value of the best ever found solution -- sum of all assigned values 292 * (see {@link Value#toDouble(Assignment)}). 293 * @return value of the best solution 294 */ 295 public double getBestValue() { 296 return getModel().getBestValue(); 297 } 298 299 /** Set total value of the best ever found solution 300 * @param bestValue value of the best solution 301 **/ 302 public void setBestValue(double bestValue) { 303 getModel().setBestValue(bestValue); 304 } 305 306 /** 307 * Perturbation penalty of the best ever found solution (see 308 * {@link PerturbationsCounter}) 309 * @return perturbation penalty of the best solution 310 */ 311 public double getBestPerturbationsPenalty() { 312 return iBestPerturbationsPenaly; 313 } 314 315 /** Returns perturbation counter 316 * @return perturbations counter 317 **/ 318 public PerturbationsCounter<V, T> getPerturbationsCounter() { 319 return iPerturbationsCounter; 320 } 321 322 /** Clear the best ever found solution */ 323 public void clearBest() { 324 iLock.writeLock().lock(); 325 try { 326 getModel().clearBest(); 327 iBestInfo = null; 328 iBestTime = -1; 329 iBestIteration = -1; 330 iBestFailedIterations = 0; 331 iBestIndex = -1; 332 iBestPerturbationsPenaly = -1.0; 333 for (SolutionListener<V, T> listener : iSolutionListeners) 334 listener.bestCleared(this); 335 } finally { 336 iLock.writeLock().unlock(); 337 } 338 } 339 340 /** True if the solution is complete, i.e., all the variables are assigned 341 * @return true if all the variables are assigned 342 **/ 343 public boolean isComplete() { 344 return getAssignment().nrAssignedVariables() == getModel().variables().size(); 345 } 346 347 /** 348 * Save the current solution as the best ever found solution (it also calls 349 * {@link Model#saveBest(Assignment)}) 350 * @param master master solution into which information about the best solution are to be copied as well 351 */ 352 public void saveBest(Solution<V, T> master) { 353 iLock.writeLock().lock(); 354 try { 355 getModel().saveBest(iAssignment); 356 iBestInfo = getInfo(); 357 iBestTime = getTime(); 358 iBestIteration = getIteration(); 359 iBestFailedIterations = getFailedIterations(); 360 iBestIndex = getAssignment().getIndex(); 361 iBestPerturbationsPenaly = (iPerturbationsCounter == null ? 0.0 : iPerturbationsCounter.getPerturbationPenalty(getAssignment(), getModel())); 362 for (SolutionListener<V, T> listener : iSolutionListeners) 363 listener.bestSaved(this); 364 365 if (master != null) { 366 master.iIteration = iIteration; 367 master.iFailedIterations = iFailedIterations; 368 master.iTime = iTime; 369 master.iBestInfo = iBestInfo; 370 master.iBestTime = iBestTime; 371 master.iBestIteration = iBestIteration; 372 master.iBestFailedIterations = iBestFailedIterations; 373 master.iBestPerturbationsPenaly = iBestPerturbationsPenaly; 374 master.iBestIndex = iBestIndex; 375 } 376 } finally { 377 iLock.writeLock().unlock(); 378 } 379 } 380 381 public boolean saveBestIfImproving(Solution<V, T> master, SolutionComparator<V, T> comparator) { 382 master.iLock.readLock().lock(); 383 try { 384 if (iBestInfo != null && !comparator.isBetterThanBestSolution(this)) return false; 385 } finally { 386 master.iLock.readLock().unlock(); 387 } 388 master.iLock.writeLock().lock(); 389 try { 390 if (iBestInfo != null && !comparator.isBetterThanBestSolution(this)) return false; 391 getModel().saveBest(iAssignment); 392 iBestInfo = getInfo(); 393 iBestTime = getTime(); 394 iBestIteration = getIteration(); 395 iBestFailedIterations = getFailedIterations(); 396 iBestIndex = getAssignment().getIndex(); 397 iBestPerturbationsPenaly = (iPerturbationsCounter == null ? 0.0 : iPerturbationsCounter.getPerturbationPenalty(getAssignment(), getModel())); 398 for (SolutionListener<V, T> listener : iSolutionListeners) 399 listener.bestSaved(this); 400 401 master.iIteration = iIteration; 402 master.iFailedIterations = iFailedIterations; 403 master.iTime = iTime; 404 master.iBestInfo = iBestInfo; 405 master.iBestTime = iBestTime; 406 master.iBestIteration = iBestIteration; 407 master.iBestFailedIterations = iBestFailedIterations; 408 master.iBestPerturbationsPenaly = iBestPerturbationsPenaly; 409 master.iBestIndex = iBestIndex; 410 411 return true; 412 } finally { 413 master.iLock.writeLock().unlock(); 414 } 415 } 416 417 418 /** 419 * Save the current solution as the best ever found solution (it also calls 420 * {@link Model#saveBest(Assignment)}) 421 */ 422 public void saveBest() { 423 iLock.writeLock().lock(); 424 try { 425 saveBest(null); 426 } finally { 427 iLock.writeLock().unlock(); 428 } 429 } 430 431 /** 432 * Restore the best ever found solution into the current solution (it also 433 * calls {@link Model#restoreBest(Assignment)}) 434 */ 435 public void restoreBest() { 436 iLock.writeLock().lock(); 437 try { 438 getModel().restoreBest(iAssignment); 439 iTime = iBestTime; 440 iIteration = iBestIteration; 441 iFailedIterations = iBestFailedIterations; 442 for (SolutionListener<V, T> listener : iSolutionListeners) 443 listener.bestRestored(this); 444 } finally { 445 iLock.writeLock().unlock(); 446 } 447 } 448 449 /** Adds solution listener 450 * @param listener a solution listener 451 **/ 452 public void addSolutionListener(SolutionListener<V, T> listener) { 453 iSolutionListeners.add(listener); 454 } 455 456 /** Removes solution listener 457 * @param listener a solution listener 458 **/ 459 public void removeSolutionListener(SolutionListener<V, T> listener) { 460 iSolutionListeners.remove(listener); 461 } 462 463 /** Registered of solution listeners 464 * @return list of registered solution listener 465 **/ 466 public List<SolutionListener<V, T>> getSolutionListeners() { 467 return iSolutionListeners; 468 } 469 470 public ReentrantReadWriteLock getLock() { return iLock; } 471}