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}