Opetussuunnitelmat

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), Jan-Feb 2023

Oppimateriaali ja suositeltava kirjallisuus

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.

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.

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.

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.

Evaluation scale

0-5

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

Tavoitteet

Opintojakson tarkoitus 

Verkkomallit ja optimointi on vaihtoehto tieto- ja viestintätekniikan sovelletun matematiikan opintojaksoksi. Tällä opintojaksolla suuntaat osaamistasi systeemitieteisiin eli operaatiotutkimukseen. Tutustut verkko-optimointimalleihin, joita käytetään aktiivisesti mm. logistiikassa ja kaupunkisuunnittelussa. Opit myös optimointiongelmien ratkaisemista ohjelmallisesti sekä verkkoalgoritmien että yleisempien lineaaristen algoritmien avulla.

Opintojakson osaamiset

EUR-ACE Tieto ja ymmärrys
- tiedot ja ymmärrys tieto- ja viestintätekniikan luonnontieteellisistä ja matemaattisista periaatteista
- tiedot ja ymmärrys oman erikoistumisalan perustana olevista insinööritieteistä sillä tasolla, joka mahdollistaa muiden ohjelman tulosten saavuttamisen mukaan lukien käsityksen tulevaisuuden vaatimuksista omalla alalla

EUR-ACE Tekniikan soveltaminen käytäntöön
- ymmärrys soveltuvista tekniikoista ja menetelmistä sekä niiden rajoituksista


Opintojakson osaamistavoite 

Tunnet verkkoihin liittyvät peruskäsitteet. Osaat käsitellä verkkoja ohjelmallisesti ja ajaa verkoille optimointialgoritmeja. Ymmärrät alkeellisten verkkoalgoritmien toimintaperiaatteet. Kykenet muotoilemaan lineaarisen optimointiongelman ohjelmallisesti ja etsiä sille ratkaisun. Ymmärrät optimoinnin yleisen periaatteen ja olet tutustunut joihinkin epälineaarisiin optiointiongelmiin.

Sisältö

Suunnattu ja suuntaamaton verkko. Verkon väritys, aikataulutusongelmat. Minimaalinen virittäjäpuu, lyhin reitti. Virtausverkot sovelluksineen. Lineaarinen optimointi. Epälineaarisen optimoinnin alkeita. Valittuja algoritmeja.

Aika ja paikka

Dynamolla (Teams-tallennus).

Opetusmenetelmät

Viikoittain luentoja ja harjoituksia.

Kurssi suoritetaan tekemällä viikoittaisia harjoituksia (lähinnä python) ja vertaisarvioimalla muiden suorituksia. Kaikkien harjoitusten suorittaminen on pakollista kurssin läpäisemiseksi. Lisäksi on Exam-loppukoe.

Käytämme networkx python -kirjastoa. Student.labranet.jamk.fi-palvelimelle on asennettu toimiva python-ympäristö, jonka tekemiseen voidaan käyttää vain SSH-yhteyttä.

Sisällön jaksotus

Kuusi viikkoa:

1. Perusteet ja orientaatio
2. Verkon läpikäynti, minimaalinen virittäjäpuu
3. Lyhin polku
4. Aikataulutus ja väritykset
5. Maksimivirtaus minimikustannuksin
6. Maksimivirtaus minimikustannuksin & lineaarinen optimointi.

Lisätietoja opiskelijoille

Aikaisempaa python-kokemusta ei vaadita, mutta se on hyödyksi. Sama pätee Linux basics -kokemukseen (työskentelemme student-palvelimella).

Tarkemmista kurssikokouksista sovitaan kurssin ensimmäisen viikon aikana.

Arviointiasteikko

0-5

Arviointikriteeri, hyväksytty/hylätty

Tunnet verkkoihin liittyvät peruskäsitteet. Osaat käsitellä verkkoja ohjelmallisesti ja ajaa verkoille optimointialgoritmeja. Ymmärrät alkeellisten verkkoalgoritmien toimintaperiaatteet. Kykenet muotoilemaan lineaarisen optimointiongelman ohjelmallisesti ja etsiä sille ratkaisun. Ymmärrät optimoinnin yleisen periaatteen ja olet tutustunut joihinkin epälineaarisiin optiointiongelmiin.

Esitietovaatimukset

Ohjelmoinnin perusosaaminen

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), Jan-Feb 2023

Oppimateriaali ja suositeltava kirjallisuus

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.

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.

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.

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.

Evaluation scale

0-5

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

Tavoitteet

Opintojakson tarkoitus 

Verkkomallit ja optimointi on vaihtoehto tieto- ja viestintätekniikan sovelletun matematiikan opintojaksoksi. Tällä opintojaksolla suuntaat osaamistasi systeemitieteisiin eli operaatiotutkimukseen. Tutustut verkko-optimointimalleihin, joita käytetään aktiivisesti mm. logistiikassa ja kaupunkisuunnittelussa. Opit myös optimointiongelmien ratkaisemista ohjelmallisesti sekä verkkoalgoritmien että yleisempien lineaaristen algoritmien avulla.

Opintojakson osaamiset

EUR-ACE Tieto ja ymmärrys
- tiedot ja ymmärrys tieto- ja viestintätekniikan luonnontieteellisistä ja matemaattisista periaatteista
- tiedot ja ymmärrys oman erikoistumisalan perustana olevista insinööritieteistä sillä tasolla, joka mahdollistaa muiden ohjelman tulosten saavuttamisen mukaan lukien käsityksen tulevaisuuden vaatimuksista omalla alalla

EUR-ACE Tekniikan soveltaminen käytäntöön
- ymmärrys soveltuvista tekniikoista ja menetelmistä sekä niiden rajoituksista


Opintojakson osaamistavoite 

Tunnet verkkoihin liittyvät peruskäsitteet. Osaat käsitellä verkkoja ohjelmallisesti ja ajaa verkoille optimointialgoritmeja. Ymmärrät alkeellisten verkkoalgoritmien toimintaperiaatteet. Kykenet muotoilemaan lineaarisen optimointiongelman ohjelmallisesti ja etsiä sille ratkaisun. Ymmärrät optimoinnin yleisen periaatteen ja olet tutustunut joihinkin epälineaarisiin optiointiongelmiin.

Sisältö

Suunnattu ja suuntaamaton verkko. Verkon väritys, aikataulutusongelmat. Minimaalinen virittäjäpuu, lyhin reitti. Virtausverkot sovelluksineen. Lineaarinen optimointi. Epälineaarisen optimoinnin alkeita. Valittuja algoritmeja.

Oppimateriaali ja suositeltava kirjallisuus

Opettaja antaa materiaalit opintojakson alussa / aikana.

Opetusmenetelmät

Luennot ja ohjaukset alkuviikosta luokassa, loppuviikosta Zoomissa (samat asiat kuin alkuviikosta, tallennetaan).

Viikoittaiset tehtävät, palautetaan kirjallisesti.

Lopputesti.

Läpäisykriteerit: kaikki tehtävät hyväksytysti palautettu, lopputesti läpäisty.

Python-koodia ja student-palvelinta käytetään havainnollistamaan algoritmeja. Aiempaa python-kokemusta ei tarvita.

Opiskelijan ajankäyttö ja kuormitus

Ohjaukset 30h, itsenäinen työskentely 51h.

Arviointiasteikko

Hyväksytty/Hylätty

Arviointikriteeri, hyväksytty/hylätty

Tunnet verkkoihin liittyvät peruskäsitteet. Osaat käsitellä verkkoja ohjelmallisesti ja ajaa verkoille optimointialgoritmeja. Ymmärrät alkeellisten verkkoalgoritmien toimintaperiaatteet. Kykenet muotoilemaan lineaarisen optimointiongelman ohjelmallisesti ja etsiä sille ratkaisun. Ymmärrät optimoinnin yleisen periaatteen ja olet tutustunut joihinkin epälineaarisiin optiointiongelmiin.

Esitietovaatimukset

Ohjelmoinnin perusosaaminen