001    package net.sf.cpsolver.ifs.heuristics;
002    
003    import net.sf.cpsolver.ifs.model.*;
004    import net.sf.cpsolver.ifs.solution.*;
005    import net.sf.cpsolver.ifs.solver.*;
006    
007    /**
008     * Variable selection criterion.
009     * <br><br>
010     * The IFS algorithm requires a function that selects a variable to be (re)assigned during 
011     * the current iteration step. This problem is equivalent to a variable selection criterion 
012     * in constraint programming. There are several guidelines for selecting a variable.
013     * In local search, the variable participating in the largest number of violations is 
014     * usually selected first. In backtracking-based algorithms, the first-fail principle is 
015     * often used, i.e., a variable whose instantiation is most complicated is selected first. 
016     * This could be the variable involved in the largest set of constraints or the variable 
017     * with the smallest domain, etc.
018     * <br><br>
019     * We can split the variable selection criterion into two cases. If some variables remain 
020     * unassigned, the “worst” variable among them is selected, i.e., first-fail principle is 
021     * applied. This may, for example, be the variable with the smallest domain or with the 
022     * highest number of hard and/or soft constraints.
023     * <br><br>
024     * The second case occurs when all variables are assigned. Because the algorithm does 
025     * not need to stop when a complete feasible solution is found, the variable selection 
026     * criterion for such case has to be considered as well. Here all variables are assigned 
027     * but the solution is not good enough, e.g., in the sense of violated soft constraints. 
028     * We choose a variable whose change of a value can introduce the best improvement of the 
029     * solution. It may, for example, be a variable whose value violates the highest number of 
030     * soft constraints.
031     * <br><br>
032     * It is possible for the solution to become incomplete again after such an iteration because 
033     * a value which is not consistent with all hard constraints can be selected in the value 
034     * selection criterion. This can also be taken into account in the variable selection 
035     * heuristics.
036     *
037     * @see Solver
038     *
039     * @version
040     * IFS 1.1 (Iterative Forward Search)<br>
041     * Copyright (C) 2006 Tomáš Müller<br>
042     * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
043     * Lazenska 391, 76314 Zlin, Czech Republic<br>
044     * <br>
045     * This library is free software; you can redistribute it and/or
046     * modify it under the terms of the GNU Lesser General Public
047     * License as published by the Free Software Foundation; either
048     * version 2.1 of the License, or (at your option) any later version.
049     * <br><br>
050     * This library is distributed in the hope that it will be useful,
051     * but WITHOUT ANY WARRANTY; without even the implied warranty of
052     * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
053     * Lesser General Public License for more details.
054     * <br><br>
055     * You should have received a copy of the GNU Lesser General Public
056     * License along with this library; if not, write to the Free Software
057     * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
058     **/
059    
060    public interface VariableSelection {
061        /** Initialization */
062        public void init(Solver solver);
063        /** Variable selection 
064         * @param solution current solution
065         */
066        public Variable selectVariable(Solution solution);
067    }