    001package net.sf.cpsolver.ifs.model;
    002
    003import net.sf.cpsolver.ifs.model.Model;
    004import net.sf.cpsolver.ifs.model.Neighbour;
    005import net.sf.cpsolver.ifs.model.Value;
    006import net.sf.cpsolver.ifs.model.Variable;
    007
    008/**
    009 * Lazy neigbour (a change of the overall solution value is unknown before
    010 * the neighbour is assigned, it is possible to undo the neighbour instead).
    011 * This neighbour is useful when it is
    012 * two expensive to compute change of overall solution value before the
    013 * variable is reassigned. It is possible to undo the neighbour instead.
    014 * Search strategy has to implement {@link LazyNeighbourAcceptanceCriterion}.
    015 *
    016 * @version IFS 1.2 (Iterative Forward Search)<br>
    017 *          Copyright (C) 2013 Tomáš Müller<br>
    018 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    019 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    020 * <br>
    021 *          This library is free software; you can redistribute it and/or modify
    022 *          it under the terms of the GNU Lesser General Public License as
    023 *          published by the Free Software Foundation; either version 3 of the
    024 *          License, or (at your option) any later version. <br>
    025 * <br>
    026 *          This library is distributed in the hope that it will be useful, but
    027 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    028 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    029 *          Lesser General Public License for more details. <br>
    030 * <br>
    031 *          You should have received a copy of the GNU Lesser General Public
    032 *          License along with this library; if not see
    033 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    034 */
    035public abstract class LazyNeighbour<V extends Variable<V, T>, T extends Value<V, T>> extends Neighbour<V,T> {
    036    private LazyNeighbourAcceptanceCriterion<V,T> iCriterion = null;
    037
    038    /**
    039     * Set acceptance criterion (to be used by a search strategy before the
    040     * neighbour is accepted, so that it can be undone if desired)
    041     */
    042    public void setAcceptanceCriterion(LazyNeighbourAcceptanceCriterion<V,T> criterion) {
    043        iCriterion = criterion;
    044    }
    045
    046    /**
    047     * Assign neighbour, check given acceptance criterion, and undo
    048     * assignment if the change is not accepted.
    049     */
    050    @Override
    051    public void assign(long iteration) {
    052        double before = getModel().getTotalValue();
    053        doAssign(iteration);
    054        double after = getModel().getTotalValue();
    055        if (!iCriterion.accept(this, after - before)) undoAssign(iteration);
    056    }
    057    /**
    058     * Return -1 (neighbour is always accepted). The search strategy that
    059     * is using this neighbour must implement {@link LazyNeighbourAcceptanceCriterion}.
    060     */
    061    @Override
    062    public double value() { return -1; }
    063
    064    /** Perform assignment */
    065    protected abstract void doAssign(long iteration);
    066    /** Undo assignment */
    067    protected abstract void undoAssign(long iteration);
    068    /** Return problem model (it is needed in order to be able to get
    069     * overall solution value before and after the assignment of this neighbour) */
    070    public abstract Model<V,T> getModel();
    071
    072    /** Neighbour acceptance criterion interface (to be implemented
    073     * by search strategies that are using {@link LazyNeighbour}.
    074     * It is also required to call {@link LazyNeighbour#setAcceptanceCriterion(LazyNeighbour.LazyNeighbourAcceptanceCriterion)}
    075     * before the neighbour is accepted by the search strategy.
    076     */
    077    public static interface LazyNeighbourAcceptanceCriterion<V extends Variable<V, T>, T extends Value<V, T>> {
    078        /** True when the currently assigned neighbour should be accepted (false means
    079         * that the change will be undone
    080         * @param neighbour neighbour that was assigned
    081         * @param value change in overall solution value
    082         * @return true if the neighbour can be accepted (false to undo the assignment)
    083         */
    084        public boolean accept(LazyNeighbour<V,T> neighbour, double value);
    085    }
    086}