Numerous problems in bioinformatics and other domains can be formulated as optimization tasks; we seek the shortest, cheapest, or longest among many possible solutions that satisfy certain constraints. For some problems, there is no known algorithm that can find the optimal solution efficiently, or the problem can be proved NP-hard. Even in such cases, we are interested in a solution that is as good as possible, to learn something about the underlying (biological) problem.
This course introduces fundamental techniques for modeling and solving combinatorial optimization problems. The first half of the course emphasizes exact methods, especially those based on (integer) linear programming. The second half explores heuristic and metaheuristic approaches, which provide practical solutions when exact methods become infeasible.
