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}