001    package net.sf.cpsolver.ifs.perturbations;
002    
003    import java.util.Collection;
004    import java.util.Map;
005    
006    import net.sf.cpsolver.ifs.model.Model;
007    import net.sf.cpsolver.ifs.model.Value;
008    import net.sf.cpsolver.ifs.model.Variable;
009    import net.sf.cpsolver.ifs.solution.Solution;
010    import 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 Tomas Muller<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     */
052    public 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    }