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