Contemporary Heuristic Techniques

Due to high computational complexity of many practical problems, there is a need to use approximate algorithms to obtain good results in resonable time. Heuristic is a technique which seeks good ( i.e. near-optimal) solutions in acceptable time. The lecture presents modern inteligent heuristics. The students learn about specific techniques that are available, thought the application of computer algorithms. Second they understand when
each of these methods should and should not be used. Applications contain: Travelling Salesman Problem, Boolean Satisfiability Problem, The 0-1 Knapsack Problem, The Vehicle Routing Problem, Graph coloring.



Lecture contents

1. Introduction. Why some problems are difficult to solve?


2. Computational complexity.


• NP-complete, NP-hard problems.


3. Local and global search


• Approximate solutions


4. Quality of heuristics solutions.


• Worst case, average case


5. Exhaustive search


• backtracking methods


• dynamic programming


• branch and bound method


6. Heuristics for some combinatorial problems (greedy, heuristics dedicated to the specific problems).


• Travelling Salesman Problem (algorithms and bounds), applications


• Boolean Satisfiability Problem (SAT)


• Graph Coloring Problem,


• String Alignment Problem


7. Local search methods,


• k-opt methods


• applications TSP, SAT


8. Simulating annealing,


• applications.


• Examples


• Tuning


9. Tabu Search.


• Comparison with Simulating Annealing


10. Evolutionary computation.


• Coding


• Genetic operators,


• selection methods


• Applications: TSP, SAT, design of telecommunication networks.


11. Swarm Intelligence. Routing in Telecommunication Networks.


12. Parastic Computing


13. Fuzzy sets.



Projects contents
During the project students implement one the techniques described during the lecture. The obtained results are compared with simple greedy technique. Students are encouraged to propose their own problems which are suitable to the topic of the lecture.