001 package net.sf.cpsolver.ifs.solution;
002
003 import java.util.ArrayList;
004 import java.util.Collection;
005 import java.util.List;
006 import java.util.Locale;
007 import java.util.Map;
008
009 import net.sf.cpsolver.ifs.model.Model;
010 import net.sf.cpsolver.ifs.model.Value;
011 import net.sf.cpsolver.ifs.model.Variable;
012 import net.sf.cpsolver.ifs.perturbations.PerturbationsCounter;
013 import net.sf.cpsolver.ifs.solver.Solver;
014
015 /**
016 * Generic solution. <br>
017 * <br>
018 * It consist from the model and information about current iteration and
019 * solution time.
020 *
021 * @see Model
022 * @see net.sf.cpsolver.ifs.solver.Solver
023 *
024 * @version IFS 1.2 (Iterative Forward Search)<br>
025 * Copyright (C) 2006 - 2010 Tomas Muller<br>
026 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
027 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
028 * <br>
029 * This library is free software; you can redistribute it and/or modify
030 * it under the terms of the GNU Lesser General Public License as
031 * published by the Free Software Foundation; either version 3 of the
032 * License, or (at your option) any later version. <br>
033 * <br>
034 * This library is distributed in the hope that it will be useful, but
035 * WITHOUT ANY WARRANTY; without even the implied warranty of
036 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
037 * Lesser General Public License for more details. <br>
038 * <br>
039 * You should have received a copy of the GNU Lesser General Public
040 * License along with this library; if not see
041 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
042 */
043
044 public class Solution<V extends Variable<V, T>, T extends Value<V, T>> {
045 private static java.text.DecimalFormat sTimeFormat = new java.text.DecimalFormat("0.00",
046 new java.text.DecimalFormatSymbols(Locale.US));
047
048 private Model<V, T> iModel;
049 private long iIteration = 0;
050 private double iTime = 0.0;
051
052 private boolean iBestComplete = false;
053 private Map<String, String> iBestInfo = null;
054 private long iBestIteration = -1;
055 private double iBestTime = -1;
056 private double iBestPerturbationsPenaly = -1.0;
057 private double iBestValue = 0;
058
059 private List<SolutionListener<V, T>> iSolutionListeners = new ArrayList<SolutionListener<V, T>>();
060 private PerturbationsCounter<V, T> iPerturbationsCounter = null;
061
062 /** Constructor */
063 public Solution(Model<V, T> model) {
064 this(model, 0, 0.0);
065 }
066
067 /** Constructor */
068 public Solution(Model<V, T> model, long iteration, double time) {
069 iModel = model;
070 iIteration = iteration;
071 iTime = time;
072 }
073
074 /** Current iteration */
075 public long getIteration() {
076 return iIteration;
077 }
078
079 /** The model associated with the solution */
080 public Model<V, T> getModel() {
081 return iModel;
082 }
083
084 /** Current solution time (time in seconds from the start of the solver) */
085 public double getTime() {
086 return iTime;
087 }
088
089 /** Update time, increment current iteration */
090 public void update(double time) {
091 iTime = time;
092 iIteration++;
093 for (SolutionListener<V, T> listener : iSolutionListeners)
094 listener.solutionUpdated(this);
095 }
096
097 /** Initialization */
098 public void init(Solver<V, T> solver) {
099 iIteration = 0;
100 iTime = 0;
101 if (iModel != null)
102 iModel.init(solver);
103 iPerturbationsCounter = solver.getPerturbationsCounter();
104 }
105
106 @Override
107 public String toString() {
108 return "Solution{\n model=" + iModel + ",\n iteration=" + iIteration + ",\n time=" + iTime + "\n}";
109 }
110
111 /**
112 * Solution information. It consits from info from the model which is
113 * associated with the solution, time, iteration, speed and infos from all
114 * solution listeners.
115 */
116 public Map<String, String> getInfo() {
117 Map<String, String> ret = getModel().getInfo();
118 if (getPerturbationsCounter() != null)
119 getPerturbationsCounter().getInfo(ret, getModel());
120 ret.put("Time", sTimeFormat.format(getTime() / 60.0) + " min");
121 ret.put("Iteration", String.valueOf(getIteration()));
122 if (getTime() > 0)
123 ret.put("Speed", sTimeFormat.format((getIteration()) / getTime()) + " it/s");
124 for (SolutionListener<V, T> listener : iSolutionListeners)
125 listener.getInfo(this, ret);
126 return ret;
127 }
128
129 /**
130 * Extended solution information. Similar to {@link Solution#getInfo()}, but
131 * some more information (that is more expensive to compute) might be added.
132 * Also extended model information is added (see
133 * {@link Model#getExtendedInfo()}) into the resultant table.
134 */
135 public Map<String, String> getExtendedInfo() {
136 Map<String, String> ret = getModel().getExtendedInfo();
137 if (getPerturbationsCounter() != null)
138 getPerturbationsCounter().getInfo(ret, getModel());
139 ret.put("Time", sTimeFormat.format(getTime() / 60.0) + " min");
140 ret.put("Iteration", String.valueOf(getIteration()));
141 if (getTime() > 0)
142 ret.put("Speed", sTimeFormat.format((getIteration()) / getTime()) + " it/s");
143 for (SolutionListener<V, T> listener : iSolutionListeners)
144 listener.getInfo(this, ret);
145 return ret;
146 }
147
148 /**
149 * Solution information. It consists from info from the model which is
150 * associated with the solution, time, iteration, speed and infos from all
151 * solution listeners. Only variables from the given set are included.
152 */
153 public Map<String, String> getInfo(Collection<V> variables) {
154 Map<String, String> ret = getModel().getInfo(variables);
155 if (getPerturbationsCounter() != null)
156 getPerturbationsCounter().getInfo(ret, getModel(), variables);
157 ret.put("Time", sTimeFormat.format(getTime()) + " sec");
158 ret.put("Iteration", String.valueOf(getIteration()));
159 if (getTime() > 0)
160 ret.put("Speed", sTimeFormat.format((getIteration()) / getTime()) + " it/s");
161 for (SolutionListener<V, T> listener : iSolutionListeners)
162 listener.getInfo(this, ret, variables);
163 return ret;
164 }
165
166 /** Info of the best ever found solution */
167 public Map<String, String> getBestInfo() {
168 return iBestInfo;
169 }
170
171 /** Iteration when the best ever found solution was found */
172 public long getBestIteration() {
173 return (iBestIteration < 0 ? getIteration() : iBestIteration);
174 }
175
176 /** Solution time when the best ever found solution was found */
177 public double getBestTime() {
178 return (iBestTime < 0 ? getTime() : iBestTime);
179 }
180
181 /**
182 * Returns true, if all variables of the best ever solution found are
183 * assigned
184 */
185 public boolean isBestComplete() {
186 return iBestComplete;
187 }
188
189 /**
190 * Total value of the best ever found solution -- sum of all assigned values
191 * (see {@link Value#toDouble()}).
192 */
193 public double getBestValue() {
194 return iBestValue;
195 }
196
197 /** Set total value of the best ever found solution */
198 public void setBestValue(double bestValue) {
199 iBestValue = bestValue;
200 }
201
202 /**
203 * Perturbation penalty of the best ever found solution (see
204 * {@link PerturbationsCounter})
205 */
206 public double getBestPerturbationsPenalty() {
207 return iBestPerturbationsPenaly;
208 }
209
210 /** Returns perturbation counter */
211 public PerturbationsCounter<V, T> getPerturbationsCounter() {
212 return iPerturbationsCounter;
213 }
214
215 /** Clear the best ever found solution */
216 public void clearBest() {
217 getModel().clearBest();
218 iBestInfo = null;
219 iBestTime = -1;
220 iBestIteration = -1;
221 iBestComplete = false;
222 iBestValue = 0;
223 iBestPerturbationsPenaly = -1.0;
224 for (SolutionListener<V, T> listener : iSolutionListeners)
225 listener.bestCleared(this);
226 }
227
228 /**
229 * Save the current solution as the best ever found solution (it also calls
230 * {@link Model#saveBest()})
231 */
232 public void saveBest() {
233 getModel().saveBest();
234 iBestInfo = getInfo();
235 iBestTime = getTime();
236 iBestIteration = getIteration();
237 iBestComplete = getModel().nrUnassignedVariables() == 0;
238 iBestValue = getModel().getTotalValue();
239 iBestPerturbationsPenaly = (iPerturbationsCounter == null ? 0.0 : iPerturbationsCounter
240 .getPerturbationPenalty(getModel()));
241 for (SolutionListener<V, T> listener : iSolutionListeners)
242 listener.bestSaved(this);
243 }
244
245 /**
246 * Restore the best ever found solution into the current solution (it also
247 * calls {@link Model#restoreBest()})
248 */
249 public void restoreBest() {
250 if (iBestInfo == null)
251 return;
252 getModel().restoreBest();
253 iTime = iBestTime;
254 iIteration = iBestIteration;
255 for (SolutionListener<V, T> listener : iSolutionListeners)
256 listener.bestRestored(this);
257 }
258
259 /** Adds solution listner */
260 public void addSolutionListener(SolutionListener<V, T> listener) {
261 iSolutionListeners.add(listener);
262 }
263
264 /** Removes solution listener */
265 public void removeSolutionListener(SolutionListener<V, T> listener) {
266 iSolutionListeners.remove(listener);
267 }
268 }