package ifs.heuristics;

import ifs.model.*;
import ifs.solution.*;
import ifs.solver.*;

/**
 * Variable selection criterion.
 * <br><br>
 * The IFS algorithm requires a function that selects a variable to be (re)assigned during 
 * the current iteration step. This problem is equivalent to a variable selection criterion 
 * in constraint programming. There are several guidelines for selecting a variable.
 * In local search, the variable participating in the largest number of violations is 
 * usually selected first. In backtracking-based algorithms, the first-fail principle is 
 * often used, i.e., a variable whose instantiation is most complicated is selected first. 
 * This could be the variable involved in the largest set of constraints or the variable 
 * with the smallest domain, etc.
 * <br><br>
 * We can split the variable selection criterion into two cases. If some variables remain 
 * unassigned, the “worst” variable among them is selected, i.e., first-fail principle is 
 * applied. This may, for example, be the variable with the smallest domain or with the 
 * highest number of hard and/or soft constraints.
 * <br><br>
 * The second case occurs when all variables are assigned. Because the algorithm does 
 * not need to stop when a complete feasible solution is found, the variable selection 
 * criterion for such case has to be considered as well. Here all variables are assigned 
 * but the solution is not good enough, e.g., in the sense of violated soft constraints. 
 * We choose a variable whose change of a value can introduce the best improvement of the 
 * solution. It may, for example, be a variable whose value violates the highest number of 
 * soft constraints.
 * <br><br>
 * It is possible for the solution to become incomplete again after such an iteration because 
 * a value which is not consistent with all hard constraints can be selected in the value 
 * selection criterion. This can also be taken into account in the variable selection 
 * heuristics.
 *
 * @see Solver
 *
 * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomas Muller</a>
 * @version 1.0
 **/

public interface VariableSelection {
    /** Initialization */
    public void init(Solver solver);
    /** Variable selection 
     * @param solution current solution
     */
    public Variable selectVariable(Solution solution);
}
