A lineáris optimalizálási számok egésze (OLNE) (vagy lineáris számok egész programozása (MILP) vagy egész programozás (IP) vagy Integer Linear Programming (ILP)) a matematika és az elméleti számítástechnika területe , amelyben egy adott optimalizálási problémát vizsgálunk. forma. Ezeket a problémákat költségfüggvény és lineáris kényszerek, valamint egész változók írják le.
Bizonyos problémák, különösen algoritmikus feladatok modellezéséhez szükség van a változók integráltságának korlátozására, amely megkülönbözteti az OLNE-t a klasszikus lineáris optimalizálástól . Ez a további korlát azonban összetettebbé teszi a problémát, és speciális technikákat igényel.
Az optimalizálási probléma egy matematikai probléma, ahol egy változóhalmaz és az ezekre a változókra vonatkozó korlátozások ismeretében meg kell találni egy olyan hozzárendelést, amely maximalizálja (vagy minimalizálja) egy bizonyos költségfüggvényt. Lineáris problémáról akkor beszélünk, amikor a korlátok és a költségfüggvény a változók lineáris kombinációja , a probléma pedig az egész szám, ha ezek a változók csak az egészek halmazában vehetnek fel értékeket.
A korlátot, amely a változókat egész értékek elfogadására kényszeríti, teljességi kényszernek nevezzük. Ha töröljük ezt a megszorítást, nyugodt problémáról vagy folyamatos relaxációról beszélünk, majd lineáris optimalizálási problémával foglalkozunk . Az optimális arányt a relaxált változatban és az egész változatban gyakran integrálási résnek nevezzük .
Az OLNE problémát két klasszikus formában lehet megfogalmazni: a kanonikus formában és a standard formában. A maximalizálás kanonikus formája:
,és a formanyomtatvány:
hol vannak vektorok, és egy egész értékű mátrix.
Példát adunk az OLNE problémára, amelyet a szemközti kép szemléltet.
Két változó létezik, tehát a megoldások egész számpárok. A piros pontok azok a párok, amelyek ellenőrzik a megszorításokat, a piros pontozott vonalak pedig e pontok domború burkolatát mutatják . A probléma optimális megoldása az (1,2) és (2,2).
A kék vonalak és az x tengely elhatárolják azokat a valós párokat, amelyek a teljesség korlátozása kivételével minden korlátot kielégítenek. Az optimális jobb ebben a nyugodt változatban.
Számos műveleti kutatás és algoritmikus probléma lefordítható OLNE problémává. Például a halmazok szerinti lefedettség problémája a következő. Adott egy halmaz egy , azt mondjuk, hogy egy elem e borítja Egy amennyiben e tartozik egy ; egy beállított U és a család S részhalmazainak U , a probléma abban áll, amely kiterjed az összes elem U és a lehető legkisebb alcsaládba S. Ez a probléma természetesen a következő formára változik:
minimalizálja: | (Minimalizálja az alhalmazok számát) | ||
mint például : | (Minden tétel lefedve) | ||
. | (Minden részhalmaz vagy a borítóban van, vagy nincs) |
A komplexitáselmélet értelmében az egész lineáris optimalizálást nehéznek tekintik, mivel NP-nehéz probléma . Ez a bonyolultság könnyen levezethető a beállított lefedettségi probléma NP-nehézségéből . Az egyik gyakorlati következmény az, hogy nagy problémák esetén a számítási idő nagyon hosszú lehet.
A komplexitás azonban polinom, ha a változók száma rögzített, amint azt Lenstra 1983-ban bemutatta .
Ha a megszorítások teljesen unimoduláris és egész mátrix formában vannak , akkor lehetséges egy polinomiális időfelbontás, mivel a relaxált feladat megoldása egész szám.
Ha a változók száma rögzített, akkor a probléma szintén polinom.
A felbontás klasszikus módszerei közül megemlíthetjük a szekundánsíkok módszerét (különösen a Gomory-szakaszok használatával), valamint az elkülönítés és értékelés elvét ( elágazás és kötött ). Az 1990-es évek óta a Gomory-szakaszok felvétele nagymértékben felgyorsította a szétválasztási és értékelési algoritmust. Ezzel új algoritmusosztály született, az úgynevezett elágazás és vágás .
A közelítő algoritmusok elmélete gyakran a problémák OLNE-megfogalmazását használja, és megpróbálja korlátozni az integrálási rést , hogy megközelítő megoldást nyújtson a polinom időben .
Ezt a fajta optimalizálást széles körben használják az operációs kutatásban . A bioinformatikában is klasszikus megközelítéssé vált .