|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
public interface VariableSelection
Variable selection criterion.
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.
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.
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.
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.
Solver
Method Summary | |
---|---|
void |
init(Solver solver)
Initialization |
Variable |
selectVariable(Solution solution)
Variable selection |
Method Detail |
---|
void init(Solver solver)
Variable selectVariable(Solution solution)
solution
- current solution
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |