    001    package ifs.heuristics;
    002
    003    import ifs.model.*;
    004    import ifs.solution.*;
    005    import 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     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    040     * @version 1.0
    041     **/
    042
    043    public interface VariableSelection {
    044        /** Initialization */
    045        public void init(Solver solver);
    046        /** Variable selection
    047         * @param solution current solution
    048         */
    049        public Variable selectVariable(Solution solution);
    050    }