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}