Applied mathematics: Optimization and Network Models (3 cr)

Evaluation scale

0-5

Content scheduling

Six weeks:

1. Basics & course orientation
2. Network traversals, minimal spanning trees
3. Shortest paths
4. Scheduling via graph coloring
5. Min cost flow
6. More min cost flow.

Objective

Course objective

Network models and optimization is one of the alternatives for the applied mathematics courses of information and communication technology. In this course, you will focus your knowledge in systems sciences, i.e. operations research. You will learn about network optimization models that are actively used, e.g. in logistics and urban planning. You will also learn how to solve optimization problems programmatically using both network algorithms and more general linear algorithms.

Competences

EUR-ACE Knowledge and Understanding
- knowledge and understanding of natural scientific and mathematical principles in ICT
- knowledge and understanding of the own specialization field in engineering sciences at a level that enables achieving the other program outcomes including an understanding of requirements in your own field.

EUR-ACE Engineering Practice
- knowledge about the linear techniques and their limitations

Learning outcomes

You know the basic concepts related to networks. You know how to process networks programmatically and how to run optimization algorithms for networks. You understand how the elementary network algorithms work. You are able to formulate a linear optimization problem programmatically and find a solution for it. You understand the general principle of optimization and have familiarized yourself with some non-linear optimization problems.

Content

Directed and undirected graph. Graph coloring, scheduling problems. Minimal spanning tree, shortest path. Flow networks with applications. Linear optimization. Examples of non-linear optimization. Selected algorithms.

Location and time

Teaching in Dynamo (with Teams broadcast & recording).

Materials

Ahuja, Magnanti, Orlin. Network Flows. Theory, Algorithms, and Applications. Prentice-Hall 1993.

See also:
https://coral.ise.lehigh.edu/~ted/teaching/ie411/
https://towardsdatascience.com/graph-theory-and-deep-learning-know-hows-6556b0e9891b

Teaching methods

Weekly lectures and exercise sessions.

The course is completed by doing the weekly exercises (mostly python) and by peer-reviewing exercises done by the other students. Completing all the exercises is mandatory in order to pass the course. In addition, there is a final exam in the Exam system.

We use the networkx python library. A working python environment is installed on the student.labranet.jamk.fi server, and one can use just an SSH connection in order to do all the work.

Assessment criteria, approved/failed

You know the basic concepts related to networks. You know how to process networks programmatically and how to run optimization algorithms for networks. You understand how the elementary network algorithms work. You are able to formulate a linear optimization problem programmatically and find a solution for it. You understand the general principle of optimization and have familiarized yourself with some non-linear optimization problems.

Qualifications

Ohjelmoinnin perusosaaminen

Further information

No previous python experience is required, but the general process of editing and running computer code should be familiar from before.

More specific course conventions will be negotiated during the first week of the course.