18-01-2012, 12:42 PM
STOCHASTIC LOCAL SEARCH FOUNDATIONS AND APPLICATIONS
Optimization.pdf (Size: 778.92 KB / Downloads: 161)
Combinatorial Problems
Combinatorial problems arise in many areas
of computer science and application domains:
finding shortest/cheapest round trips (TSP)
finding models of propositional formulae (SAT)
planning, scheduling, time-tabling
internet data packet routing
protein structure prediction
combinatorial auctions winner determination
Stochastic
Every decision problem has two variants:
Search variant: Find a solution for given problem instance
(or determine that no solution exists)
Decision variant: Determine whether solution
Variants of optimisation problems:
Search variant: Find a solution with optimal
objective function value for given problem instance
Evaluation variant: Determine optimal objective function
value for given problem instance
for given problem instance exists