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