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