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}