Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


6.4. STOCHASTIC TECHNIQUES

Organizations are increasingly able to capture an up-to-date picture of their global resources, and they are seeking to optimize their use of these resources. However, for large organizations, this optimization problem is unmanageable: no algorithm could ever find the guaranteed best solution for the whole organization.

Stochastic techniques are a way of exploring very large solution spaces and finding good solutions even when it is only possible to visit a (vanishingly!) small proportion of the solutions. Well-known techniques include simulated annealing, genetic algorithms, and tabu search. A drawback is that for structured problems, where constraints impose complex dependencies between different parts of the solution, stochastic techniques are not able to enforce these constraints.

Recently, researchers have begun to explore ways of embedding constraint propagation in stochastic algorithms, thus ensuring that the solutions visited by the algorithm satisfy the problem constraints. To date, such hybrid algorithms have been rather loosely coupled. For example, the stochastic technique only works on a small subset of the problem variables, producing skeleton solutions. These are then fleshed out using constraint handling techniques, and the cost of the resulting full solution is calculated, and fed back to the stochastic algorithm which generates another skeleton solution.

Tightly integrated algorithms combining techniques from mathematical programming, constraint programming, and stochastic algorithms are now the vision of a growing research community. These algorithms may still not be the "golden bullet" that cuts through all forms of complexity, but they would certainly represent an important step in the right direction!

REFERENCES

A. Colmerauer. An introduction to Prolog III. Communications of the ACM, 33(7):69-90, July
1990.
J.-Y. Cras. A Review of Industrial Constraint Solving Tools ISBN 1-898804-001, AI
Intelligence, 1993.
M. Dincbas, H. Simonis, and P. Van Hentenryck. Solving large scheduling problems
in logic programming. In EURO-TIMS Joint Internation Conference on Operations Research and Management Science, Paris, July 1988.
T. Frühwirth, A. Herold, V. Küchenhoff, T. Le Provost, P. Lim, E. Monfroy, and M. Wallace.
Constraint logic programming: An informal introduction. Technical Report ECRC-93-5, ECRC, 1993.
J. Jaffar and J.-L. Lassez. Constraint logic programming. In POPL'87: Proceedings 14th
ACM Symposium on Principles of programming Languages, pages 111-119, Munich, January 1987. ACM.
V. A. Saraswat. Concurrent Constraint Programming. MIT Press, 1993.
E. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.
P. Van Hentenryck. Constraint Satisfaction in Logic Programming. Logic Programming
Series. MIT Press, Cambridge, MA, 1989.
M. G. Wallace. Practical applications of constraint programming. Constraints, 1(1), 1996.
M. Zweben and M. S. Fox, editors. Intelligent Scheduling. Morgan Kaufmann, 1994.


Previous Table of Contents Next

footer nav
Use of this site is subject certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.