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