integer programming

integer programming (tsz. integer programmings)

1. (informatika) egészértékű programozás

A egészértékű programozás (angolul: Integer Programming, röviden IP) az optimalizálási problémák egyik speciális osztálya, amelyben a döntési változóknak egész számoknak kell lenniük. Ez a megszorítás rendkívül fontos olyan valós életbeli problémák modellezéséhez, ahol a változók nem vehetnek fel tört értéket — például darabszámok, 0–1 döntések, gépek száma, stb.

Mivel a változók diszkrét értékeket vehetnek fel, az IP-problémák megoldása jellemzően sokkal nehezebb, mint a folytonos (valós számokon értelmezett) lineáris programozási (LP) problémáké. A legtöbb IP-probléma NP-nehéz, azaz nem ismert polinomiális idejű megoldásuk.

Egy általános egészértékű programozási feladat formálisan így néz ki:

Cél:

$${\displaystyle {\text{Maximalizálni vagy minimalizálni: }}Z=c_{1}x_{1}+c_{2}x_{2}+\dots +c_{n}x_{n}}$$

Feltételek:

$${\displaystyle {\begin{cases}a_{11}x_{1}+a_{12}x_{2}+\dots +a_{1n}x_{n}\leq b_{1}\\\vdots \\a_{m1}x_{1}+a_{m2}x_{2}+\dots +a_{mn}x_{n}\leq b_{m}\\x_{1},x_{2},\dots ,x_{n}\in \mathbb {Z} \end{cases}}}$$

Ahol:

• ${\textstyle x_{i}}$ → döntési változók (egész számok)
• ${\textstyle c_{i}}$, ${\textstyle a_{ij}}$, ${\textstyle b_{j}}$ → paraméterek
• ${\textstyle Z}$ → célfüggvény (értéke maximalizálandó vagy minimalizálandó)

Minden változó csak egész szám lehet.

Csak néhány változónak kell egész számnak lennie, mások lehetnek valós számok is.

A változók csak 0 vagy 1 értéket vehetnek fel → döntési problémák, logikai modellek.

Valóságban sok döntés nem értelmezhető törtszámként:

• Nem gyárthatunk 3.7 autót → csak 3 vagy 4
• Nem lehet 1.2 dolgozónk → csak egész számú személy
• Egy döntés vagy megtörténik (1), vagy nem (0)

Gyártási feladat:

• Termék A egységhozam: 10, időigény: 5 óra
• Termék B egységhozam: 7, időigény: 3 óra
• Összesen 40 munkaóra áll rendelkezésre

Cél: Maximalizálni a nyereséget Feltétel: Ne gyártsunk tört darabszámokat

• ${\textstyle x}$: termék A darabszáma
• ${\textstyle y}$: termék B darabszáma

$${\displaystyle {\begin{aligned}{\text{Max: }}&Z=10x+7y\\{\text{Subject to: }}&5x+3y\leq 40\\&x,y\in \mathbb {Z} _{\geq 0}\end{aligned}}}$$

Ez egy egészértékű programozási feladat. LP-relaxációval (az egészség elhagyásával) megoldható gyorsan, de az optimális LP-megoldás nem biztos, hogy egész, ezért speciális módszerekre van szükség.

Mivel az IP-problémák nem oldhatók meg közvetlenül a klasszikus lineáris programozási módszerekkel, speciális algoritmusok szükségesek:

Elhagyjuk az egészértékűségi korlátokat, és megoldjuk LP-vel. Ez ad egy felső vagy alsó korlátot, de nem biztosít érvényes megoldást.

A megoldási tartományt részekre bontjuk (ágaztatás), és kizárjuk a rosszabb régiókat (becslések alapján). Ez az egyik legelterjedtebb módszer.

Új lineáris egyenlőtlenségeket adunk a modellhez, amelyek kizárják a tört LP-megoldásokat, de az egész megoldásokat nem.

A B&B és a vágások kombinációja – a legmodernebb módszer.

Közelítő, de gyors megoldások: genetikus algoritmus, tabu search, simulated annealing.

A modern optimalizálási szoftverek hatékonyan kezelik az IP-problémákat:

• CPLEX
• Gurobi
• SCIP
• CBC (COIN-OR)
• GLPK
• Excel Solver (egyszerűbb IP-re is alkalmas)

• NP-nehéz problémák: A számítási idő exponenciálisan nőhet.
• Megoldáskeresés hosszadalmas lehet nagy változószám és sok korlát mellett.
• Optimalitás bizonyítása: Nem elég jó megoldást találni — azt is bizonyítani kell, hogy nincs jobb.

• Raktárkiosztás, járműútvonal optimalizálás (pl. TSP)

• Gépidő és nyersanyag beosztás
• Ütemezés

• Minimális lefedő fa (MST), hálózati áramlás (flow)

• Választási problémák, projektkiválasztás

• Munkaerő beosztás, létszámoptimalizálás

Speciális eset: a változók csak 0 vagy 1 értéket vehetnek fel.

Például:

• ${\textstyle x=1}$: az adott projektet kiválasztjuk
• ${\textstyle x=0}$: az adott projektet kihagyjuk

Ez a logikai döntéshozatal erőteljes eszköze.

Az egészértékű programozás egy nélkülözhetetlen eszköz a valós életben előforduló optimalizálási problémák megoldására, ahol a változók csak egész értékeket vehetnek fel.

• A változók diszkrétek, nem folytonosak
• A megoldás keresése sokkal nehezebb, mint LP-nél
• Speciális algoritmusok (Branch and Bound, Cutting Plane, Branch and Cut) szükségesek
• Számos iparági alkalmazása van

Bár a megoldás nem triviális, a modern számítógépes szoftverek és algoritmusok révén ma már rendkívül összetett IP-feladatokat is hatékonyan tudunk kezelni.

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