Combinatorial Optimization with Environmental Applications

Aim

The course deals with mathematical tools for formulating, solving andanalyzing combinatorial optimization problems, often based ondifferent network and graph structures. Sustainable development andenvironmental aspects are prominent aspects in the applications thatare discussed. An important point is the ability to choose and usethe most efficient algorithm for each specific problem structure. Thealgorithms are intended to be suitable for large scale problems andimplementation on computer.After finishing the course, the student shall be able to:describe important types of combinatorial optimization problems.formulate combinatorial optimization problems as mathematical models,possibly with graph terminology, and determine the difficulty of the problems with the help of complexity theory.explain the design of and the principles behind efficient solution methods and choose and use the methods for solving different types of combinatorial optimization problems.use available software for solving optimization problems.take part of development of software for optimization problems.develop heuristics for certain structured combinatorial optimization problems.explain and use basic concepts, such as local and global optimality, convexity, extreme point, complexity, duality, heuristic, branch-and-bound, cutting planes, and basic graph theory, especially trees and cycles of different kinds.give examples of how combinatorial optimization can be used to promote sustainable development and improve the environment.

Content

Introduction to optimization, problem formulation, graphical solution,computational complexity, problem complexity. The simplex method, linear duality and sensitivity analysis. Basic graph theory andoverview of different optimization problems in graphs. Models andmethods for finding minimal spanning tree, minimum cost travelingsalesman tour, minimum cost postman tour, shortest path, minimum costassignment, minimum cost flow and maximal flow. Methods for integerprogramming, especially branch-and-bound, cutting planes and dynamicprogramming. Heuristics for hard combinatorial optimization problems.Examples on applications that concern different aspects withinsustainable development, for instance concerning a scenario that iscommon for several courses.