Overview
Stocs is our stochastic local-search CSP solver. In local search algorithms, the solver selects an initial assignment for the variables and then gradually improves the assignment toward a solution, until a solution is reached. Since searching all complete assignments may be a prohibitively large task, the solver must decide which complete assignments to consider. To this end a 'cost' is defined for every complete assignment. The cost expresses the proximity of a particular assignment to a solution of the CSP. Various heuristics such as Tabu search and simulated annealing are used to guide the search towards minimal cost. Stocs uses the Simulated Variable Range Hopping heuristic, which is based on learning the topography of the specific CSP during the solution process and using this information to guide the search.
Further heuristics are employed by Stocs in a preprocessing stage that uses inference and smart initialization to simplify the CSP before starting the stochastic search.
It can handle large CSP problems with many thousands of variables and constraints. Stocs can also solve problems in which optimization is required, in addition to constraint satisfaction.
Stocs has a programming API and a textual input language interface for quick prototyping. When using the API, each constraint must implement a cost-function, and can implement additional guiding heuristics. Hence, Stocs is a purely constraint-based local search solver.
Stocs is used in vehicle configuration, floating point verification and floorplanning.
Contact: Merav Aharoni (merav@il.ibm.com)
