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}