18-01-2012, 12:42 PM
STOCHASTIC LOCAL SEARCH FOUNDATIONS AND APPLICATIONS
[attachment=16217]
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
[attachment=16217]
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