Tyto počty lineární optimalizace celé (Olne) (nebo lineární čísla celočíselné programování (MILP) nebo programovací číslo (IP) nebo Integer Linear Programming (IPK)) je oblast matematiky a teoretické informatiky , ve kterém uvažujeme optimalizační problémy konkrétního formulář. Tyto problémy jsou popsány nákladovou funkcí a lineárními omezeními a celočíselnými proměnnými.
Omezení integrity proměnných, které odlišuje OLNE od klasické lineární optimalizace, je nutné k modelování určitých problémů, zejména algoritmických problémů. Ale toto další omezení činí problém složitějším a vyžaduje speciální techniky.
Optimalizační problém je matematický problém, kde vzhledem k sadě proměnných a omezením těchto proměnných je třeba najít přiřazení, které maximalizuje (nebo minimalizuje) určitou nákladovou funkci. Mluvíme o lineárním problému, když omezení a nákladová funkce jsou lineární kombinace proměnných a problémem jsou celá čísla, pokud tyto proměnné mohou nabývat hodnot pouze v množině celých čísel.
Omezení, které nutí proměnné přijímat celé hodnoty, se nazývá omezení úplnosti. Když toto omezení smažeme, mluvíme o uvolněném nebo nepřetržitém relaxačním problému a máme pak problém s lineární optimalizací . Poměr mezi optimálním v uvolněné verzi a v celé verzi se často nazývá propast celistvosti .
OLNE problém lze dát do dvou klasických forem: kanonické formy a standardní formy. Kanonická forma pro maximalizaci je:
,a standardní formulář je:
kde jsou vektory a je matice s celočíselnými hodnotami.
Uvádíme příklad problému OLNE ilustrovaný obrázkem naproti.
Existují dvě proměnné, takže řešení jsou dvojice celých čísel. Červené body jsou páry, které ověřují omezení, a červené tečkované čáry ukazují konvexní obálku těchto bodů. Optimální řešení tohoto problému jsou (1,2) a (2,2).
Modré čáry a osa x ohraničují dvojice realů, které splňují všechna omezení kromě omezení úplnosti. Optimum je v této uvolněné verzi lepší.
Mnoho problémů operačního výzkumu a algoritmických problémů lze přeložit do problému OLNE. Například problém pokrytí sadami je následující. Vzhledem k množině A říkáme, že prvek e je pokryt A, pokud e patří k A ; pro množinu U a rodinu S podmnožin U problém spočívá v pokrytí všech prvků U nejmenší možnou podrodinou S. Tento problém se přirozeně překládá do následující podoby:
minimalizovat: | (Minimalizujte počet podmnožin) | ||
jako : | (Všechny položky jsou pokryty) | ||
. | (Každá podmnožina je buď v obálce, nebo ne) |
Ve smyslu teorie složitosti je celočíselná lineární optimalizace považována za obtížnou, protože se jedná o NP-obtížný problém . Tuto složitost lze snadno odvodit z NP obtížnosti nastaveného problému pokrytí . Jedním z praktických důsledků je, že u velkých problémů může být doba výpočtu velmi velká.
Složitost je však polynomická, když je počet proměnných pevný, jak ukazuje Lenstra v roce 1983.
Když mají omezení podobu zcela unimodulární a celočíselné matice , je možné polynomiální časové rozlišení, protože řešení uvolněné úlohy jsou celá čísla.
Pokud je počet proměnných pevný, pak je problém také polynomický.
Z klasických metod řešení lze zmínit metodu sečnaných rovin (zejména pomocí Gomoryho řezů) a princip separace a hodnocení ( větvený a vázaný ). Od 90. let 20. století začlenění sekcí Gomory značně zrychlilo separační a vyhodnocovací algoritmus. Tím se zrodila nová třída algoritmů zvaná větve a řezy .
Teorie aproximačních algoritmů často používá OLNE formulaci problémů a pokouší se omezit mezeru v integritě, aby získala přibližné řešení v polynomiálním čase .
Tento typ optimalizace je široce používán v operačním výzkumu . Stal se také klasickým přístupem v bioinformatice .