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