ELTE - Operációkutatás Számítógépes Módszerei

2025/2026-os tanév II. (tavaszi) félév.

A tárgy célja

A tárgy célja, hogy a hallgatók a félév során megismerkedjenek különféle optimalizációs feladatok gyakorlati, számítógépes megoldásának lehetőségeivel.

A félév nagy részében egészértékű programozási módszerekkel foglalkozunk: alapvető feladatok (hátizsák feladat, utazóügynök feladat, stb.); alapvető modellezési technikák; vágás-generálás (utazóügynök feladat, gépütemezés, stb.); oszlop-generálás (ládapakoláso feladat, stb.); Benders-dekompozíció (párhuzamos gépes ütemezés, stb.), stb. Röviden - pár feladat erejéig - szó lesz még korlátozás programozásról, és lokális keresésen alapuló heurisztikák is előkerülnek majd.

A gyakorlatokon a feladatok megoldásához a Python programozási nyelvet használjuk.

Követelmények

A hallgatóknak a félév során két beadandó feladatot kell teljesíteniük a gyakorlati jegy megszerzéséhez.

A félév menete

Csütörtök 8:30-10:00, D 3.105 (Grafika labor) | Ha valaki a saját laptopján szeretné az órai munkát végezni, nyugodtan hozza magával. Sőt!

[1] 2026.02.05. (Regisztrációs időszak)

[2] 2026.02.12.

Korlátozás programozás: bevezetés.
alldifferent constraint

sendmoremoney.py sudoku.py queens.py

[3] 2026.02.19.

Korlátozás programozás: ütemezés és pakolás.
interval variables, non-overlapping constraints

scheduling.py (scheduling_instances.py) rectangle.py

[4] 2026.02.26.

Egészértékű programozás: bevezetés.
constraint generation

knapsack.py (packing_instances.py) sudoku.py queens.py

[5] 2026.03.05.

Egészértékű programozás: az utazóügynök feladat (TSP) különböző formulációi.
constraint generation, extended formulation, big-M formulation, lifting inequalities

tsp_mip.py (tsp_instances.py)

Első beadandó feladat ismertetése.

[6] 2026.03.12.

Egészértékű programozás: vágás-és-szétválasztás az utazóügynök problémára és egy egygépes ütemezési feladatra.
branch-and-cut

tsp_mip.py (tsp_instances.py) singlemachine.py (scheduling_instances.py)

[7] 2026.03.19.

Egészértékű programozás: Benders dekompozíció egy ütemezési feladatra párhuzamos gépekkel.
Benders decomposition

parallelmachines.py (scheduling_instances.py)

[8] 2026.03.26.

Egészértékű programozás: oszlopgenerálás a ládapakolási feladatra.
column generation

binpacking.py (packing_instances.py)

[9] 2026.04.02. (Tavaszi szünet)

[10] 2026.04.09.

Első beadandó feladat bemutatása.

[11] 2026.04.16.

[12] 2026.04.23.

[13] 2026.04.30.

[14] 2026.05.07. (Eötvös nap)

[15] 2026.05.14.

Elérhetőség

📧 marko.horvath (kukac) sztaki (pont) hu

📍 SZTAKI (1111 Budapest, Kende utca 13-17.), K518

📅 Fogadóórák előre egyeztetett időpontban.

Technikai dolgok

Visual Studio Code

Az órán Visual Studio Code-ban mutatom a példákat, de persze, mindenki használhatja a kedvenc szerkesztőjét.

Python

A következő csomagokat fogjuk használni:

Google OR-Tools

Korlátozás programozáshoz a CP-SAT-ot, egészértékű programozáshoz a MathOpt csomagot használjuk majd.

python -m pip install ortools

A MathOpt jó pár solver-t támogat, de ezek nem mindegyike jön automatikusan a telepítéskor. Érdemes ezért telepíteni valamelyiket a következők közül:

• HiGHS: Nyílt forráskodó megoldó (MIP, QP).

• SCIP: Nyílt forráskodó megoldó (MIP, MINLP, CIP).

• Gurobi: Kereskedelmi megoldó, de tudtok diák licence-t igényelni hozzá. A 12-es verziót érdemes telepíteni, mert a MathOpt annál újabbat egyelőre nem támogat.

Egyéb csomagok

Matplotlib. Rajzolni.

python -m pip install matplotlib

NetworkX. Gráfokhoz.

python -m pip install networkx