001 package net.sf.cpsolver.ifs.model;
002
003 import net.sf.cpsolver.ifs.model.Model;
004 import net.sf.cpsolver.ifs.model.Neighbour;
005 import net.sf.cpsolver.ifs.model.Value;
006 import 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 Tomas Muller<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 */
035 public 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 }