001package net.sf.cpsolver.ifs.perturbations; 002 003import java.util.Collection; 004import java.util.Map; 005 006import net.sf.cpsolver.ifs.model.Model; 007import net.sf.cpsolver.ifs.model.Value; 008import net.sf.cpsolver.ifs.model.Variable; 009import net.sf.cpsolver.ifs.solution.Solution; 010import net.sf.cpsolver.ifs.solver.Solver; 011 012/** 013 * Counter of perturbation penalty (minimal perturbation problem). <br> 014 * <br> 015 * Many real-life problems are dynamic, with changes in the problem definition 016 * occurring after a solution to the initial formulation has been reached. A 017 * minimal perturbation problem incorporates these changes, along with the 018 * initial solution, as a new problem whose solution must be as close as 019 * possible to the initial solution. The iterative forward search algorithm is 020 * also made to solve minimal perturbation problems. <br> 021 * <br> 022 * To define the minimal perturbation problem, we will consider an initial 023 * (original) problem, its solution, a new problem, and some distance function 024 * which allows us to compare solutions of the initial and the new problem. 025 * Subsequently we look for a solution of the new problem with minimal distance 026 * from the initial solution. This distance is expressed by this 027 * PerturbationCounter 028 * 029 * @see Solver 030 * @see Solution 031 * @see Variable 032 * 033 * @version IFS 1.2 (Iterative Forward Search)<br> 034 * Copyright (C) 2006 - 2010 Tomáš Müller<br> 035 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 036 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 037 * <br> 038 * This library is free software; you can redistribute it and/or modify 039 * it under the terms of the GNU Lesser General Public License as 040 * published by the Free Software Foundation; either version 3 of the 041 * License, or (at your option) any later version. <br> 042 * <br> 043 * This library is distributed in the hope that it will be useful, but 044 * WITHOUT ANY WARRANTY; without even the implied warranty of 045 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 046 * Lesser General Public License for more details. <br> 047 * <br> 048 * You should have received a copy of the GNU Lesser General Public 049 * License along with this library; if not see 050 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 051 */ 052public interface PerturbationsCounter<V extends Variable<V, T>, T extends Value<V, T>> { 053 /** Initialization */ 054 public void init(Solver<V, T> solver); 055 056 /** 057 * Returns perturbation penalty, i.e., the distance between current solution 058 * and the solution of the initial problem (see 059 * {@link Variable#getInitialAssignment()}). 060 * 061 * @param model 062 * current model 063 */ 064 public double getPerturbationPenalty(Model<V, T> model); 065 066 /** 067 * Returns perturbation penalty, i.e., the distance between current solution 068 * and the solution of the initial (only include variables from the given 069 * set) problem (see {@link Variable#getInitialAssignment()}). 070 * 071 * @param model 072 * current model 073 */ 074 public double getPerturbationPenalty(Model<V, T> model, Collection<V> variables); 075 076 /** 077 * Returns perturbation penalty of the solution which become from the 078 * current solution when given conflicting values are unassigned and the 079 * selected value is assigned. Since this penalty is used for comparison of 080 * different candidate values in the value selection criterion, it is fully 081 * acceptable to just return a difference between current and the altered 082 * solution (which might be easied for computation that the whole 083 * perturbation penalty). 084 * 085 * @param model 086 * current model 087 * @param selectedValue 088 * value to be selected in the next iteration 089 * @param conflicts 090 * conflicting values to be unassigned in the next iteration 091 */ 092 public double getPerturbationPenalty(Model<V, T> model, T selectedValue, Collection<T> conflicts); 093 094 /** 095 * Some (perturbation) information about the solution might be returned 096 * here. 097 * 098 * @param info 099 * resultant info table 100 * @param model 101 * current model 102 */ 103 public void getInfo(Map<String, String> info, Model<V, T> model); 104 105 /** 106 * Some (perturbation) information about the solution might be returned here 107 * (only include variables from the given set). 108 * 109 * @param info 110 * resultant info table 111 * @param model 112 * current model 113 */ 114 public void getInfo(Map<String, String> info, Model<V, T> model, Collection<V> variables); 115}