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}