discrete optimization

Angol

Főnév

discrete optimization (tsz. discrete optimizations)

(informatika) diszkrét optimalizálás

Discrete optimization (diszkrét optimalizálás) egy olyan optimalizálási ág, ahol a döntési változók csak diszkrét értékeket vehetnek fel – tipikusan egész számokat, bináris értékeket (0/1), vagy véges halmazból származó választásokat. Ez a megközelítés különösen fontos a valós életbeli kombinatorikus problémák megoldásában, ahol a döntések nem lehetnek folytonosak (pl. „igen/nem”, „melyik útvonal”).

🧠 1. Alapfogalom

Általános diszkrét optimalizálási probléma:

${\begin{aligned}&\min /\max \quad f(x)\\&{\text{alatt:}}\quad x\in D\subset \mathbb {Z} ^{n}\\&{\text{további feltételek: }}g_{i}(x)\leq 0,\quad h_{j}(x)=0\end{aligned}}$

ahol:

${\textstyle f(x)}$ : célfüggvény
${\textstyle x}$ : döntési változók (egészek vagy binárisak)
${\textstyle D}$ : diszkrét halmaz (pl. ${\textstyle \{0,1\}^{n}}$ , vagy egész intervallum)

📊 2. Alapvető diszkrét optimalizálási típusok

Típus	Példa
Integer Programming (IP)	Minden változó egész
Binary Integer Programming (BIP)	Csak 0 vagy 1 lehet
Mixed Integer Programming (MIP)	Egyes változók folytonosak, mások egész
Combinatorial optimization	Kombinációk, útvonalak, hozzárendelések
Constraint Satisfaction Problem (CSP)	Véges értéktartományon, korlátokkal

🎯 3. Jellemző problémák

Probléma	Leírás
Knapsack problem	Válassz tárgyakat, hogy érték maximális legyen, súly ne lépjen túl
Travelling Salesman Problem (TSP)	Legrövidebb körút
Vehicle Routing Problem (VRP)	Járművek útvonalainak tervezése
Job Scheduling	Feladatok beosztása időre
Set Cover, SAT	Kombinatorikus logikai/halmaz fedések
Graph coloring	Minimális szín a szomszédos csúcsok különbözéséhez

🧮 4. Megoldási módszerek

🔁 Exakt algoritmusok

Módszer	Leírás
Branch and Bound	Megoldástér rekurzív bontása, alsó-felső korlátok
Branch and Cut	Vágóélek + BnB kombinálása
Dynamic Programming	Kis részproblémák összeépítése
Integer Linear Programming (ILP)	LP-relaxáció, majd visszakényszerítés egész értékekre
Constraint Programming (CP)	Korlátok alapján kizárás, propagáció

🎲 Heurisztikus / metaheurisztikus módszerek

Módszer	Alkalmazás
Greedy algoritmusok	Gyors, lokális választás
Genetikus algoritmusok	Evolúciós megközelítés
Simulated Annealing	Sztochasztikus, energia alapú keresés
Ant Colony Optimization	Kölcsönhatáson alapuló keresés
Tabu Search	Tiltólista az ismétlés elkerülésére
Particle Swarm Optimization	(kiegészítve bináris változókra is)

🧰 5. Szoftveres eszközök

Eszköz / Könyvtár	Típus
CPLEX, Gurobi	IP/MIP solver
CBC, GLPK	Nyílt forráskódú IP megoldók
MiniZinc	Constraint programming nyelv
OR-Tools (Google)	TSP, VRP, CSP, IP megoldások
Pyomo	Python modellező eszköz
Z3 Solver	Logikai formulák, SAT/SMT megoldás

📈 6. Példa – 0–1 hátizsák probléma ILP-vel (Python + `pulp`)

from pulp import *

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50

x = [LpVariable(f"x{i}", cat="Binary") for i in range(len(values))]
prob = LpProblem("Knapsack", LpMaximize)

prob += lpSum(x[i]*values[i] for i in range(len(x)))
prob += lpSum(x[i]*weights[i] for i in range(len(x))) <= capacity

prob.solve()
print("Max value:", value(prob.objective))
print("Selected:", [i for i in range(len(x)) if x[i].value() == 1])

📦 7. Előnyök és hátrányok

✅ Előnyök	❌ Hátrányok
Valósághű, bináris döntések	NP-teljes problémák gyakoriak
Gazdag modellezési lehetőség	Méret növekedésével gyorsan bonyolult
Sok eszköz, solver létezik	Paraméterhangolás bonyolult lehet

🧾 8. Összefoglalás

Fogalom	Leírás
Diszkrét optimalizálás	Nem-folytonos, véges értékkészlettel rendelkező optimalizálás
Típusai	ILP, BIP, CSP, kombinatorikus
Megoldás	Exakt vagy heurisztikus módszerekkel
Használat	Ütemezés, útvonaltervezés, hozzárendelés
Szoftverek	CPLEX, Gurobi, OR-Tools, MiniZinc, Pyomo

További információk

discrete optimization - Szótár.net (en-hu)
discrete optimization - Sztaki (en-hu)
discrete optimization - Merriam–Webster
discrete optimization - Cambridge
discrete optimization - WordNet
discrete optimization - Яндекс (en-ru)
discrete optimization - Google (en-hu)
discrete optimization - Wikidata
discrete optimization - Wikipédia (angol)