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 Tomáš Müller<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     * Return acceptance criterion (to be used by a search strategy before the 
053     * neighbour is accepted, so that it can be undone if desired)  
054     * @return acceptance criterion
055     */
056    public LazyNeighbourAcceptanceCriterion<V,T> getAcceptanceCriterion() {
057        return iCriterion;
058    }
059    
060    /**
061     * Assign neighbour, check given acceptance criterion, and undo
062     * assignment if the change is not accepted. 
063     */
064    @Override
065    public void assign(Assignment<V, T> assignment, long iteration) {
066        double before = getModel().getTotalValue(assignment);
067        doAssign(assignment, iteration);
068        double after = getModel().getTotalValue(assignment);
069        if (!iCriterion.accept(assignment, this, after - before)) undoAssign(assignment, iteration);
070    }
071    /**
072     * Return -1 (neighbour is always accepted). The search strategy that
073     * is using this neighbour must implement {@link LazyNeighbourAcceptanceCriterion}.
074     */
075    @Override
076    public double value(Assignment<V, T> assignment) { return -1; }
077    
078    /** Perform assignment 
079     * @param assignment current assignment
080     * @param iteration current iteration
081     **/
082    protected abstract void doAssign(Assignment<V, T> assignment, long iteration);
083    
084    /** Undo assignment
085     * @param assignment current assignment
086     * @param iteration current iteration
087     **/
088    protected abstract void undoAssign(Assignment<V, T> assignment, long iteration);
089    
090    /** Return problem model (it is needed in order to be able to get
091     * overall solution value before and after the assignment of this neighbour) 
092     * @return problem model
093     **/
094    public abstract Model<V,T> getModel();
095    
096    /** Neighbour acceptance criterion interface (to be implemented
097     * by search strategies that are using {@link LazyNeighbour}. 
098     * It is also required to call {@link LazyNeighbour#setAcceptanceCriterion(LazyNeighbour.LazyNeighbourAcceptanceCriterion)}
099     * before the neighbour is accepted by the search strategy. 
100     * @param <V> Variable
101     * @param <T> Value
102     */ 
103    public static interface LazyNeighbourAcceptanceCriterion<V extends Variable<V, T>, T extends Value<V, T>> {
104        /** True when the currently assigned neighbour should be accepted (false means
105         * that the change will be undone
106         * @param assignment current assignment
107         * @param neighbour neighbour that was assigned
108         * @param value change in overall solution value
109         * @return true if the neighbour can be accepted (false to undo the assignment)
110         */
111        public boolean accept(Assignment<V, T> assignment, LazyNeighbour<V,T> neighbour, double value);
112    }
113}