TY - GEN
T1 - A local search algorithm for balanced incomplete block designs
AU - Prestwich, Steven
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2003.
PY - 2003
Y1 - 2003
N2 - Local search is often able to solve larger problems than systematic backtracking. To apply it to a constraint satisfaction problem, the problem is often treated as an optimization problem in which the search space is the set of total assignments, and the number of constraint violations is to be minimized to zero. Though often successful, this approach is sometimes unsuitable for structured problems with few solutions. An alternative is to explore the set of consistent partial assignments, minimizing the number of unassigned variables to zero. A local search algorithm of this type violates no constraints and can exploit cost and propagation techniques. This paper describes such an algorithm for balanced incomplete block design generation. On a large set of instances it out-performs several backtrackers and a neural network with simulated annealing.
AB - Local search is often able to solve larger problems than systematic backtracking. To apply it to a constraint satisfaction problem, the problem is often treated as an optimization problem in which the search space is the set of total assignments, and the number of constraint violations is to be minimized to zero. Though often successful, this approach is sometimes unsuitable for structured problems with few solutions. An alternative is to explore the set of consistent partial assignments, minimizing the number of unassigned variables to zero. A local search algorithm of this type violates no constraints and can exploit cost and propagation techniques. This paper describes such an algorithm for balanced incomplete block design generation. On a large set of instances it out-performs several backtrackers and a neural network with simulated annealing.
UR - https://www.scopus.com/pages/publications/7044249167
U2 - 10.1007/3-540-36607-5_10
DO - 10.1007/3-540-36607-5_10
M3 - Conference proceeding
AN - SCOPUS:7044249167
SN - 9783540366072
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 132
EP - 143
BT - Recent Advances in Constraints - Joint ERCIM/CologNet International Workshop on Constraint Solving and Constraint Logic Programming, Selected Papers
A2 - O'Sullivan, Barry
PB - Springer Verlag
T2 - Joint ERCIM/CologNet International Workshop on Constraint Solving and Constraint Logic Programming, 2002
Y2 - 19 June 2002 through 21 June 2002
ER -