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