Целобројно програмирање

Целобројно програмирање је проблем математичке оптимизације или изводљивост програма у којем све или неке променљиве су ограничене да буду целобројне. У многим срединама термин се односи на целобројно линерано програмирање (ЦЛП), у којем објектна функција и ограничења (осим целобројног ограничења) су линеарни.

Целобројно програмирање је НП-проблем. Посебан случај је један од Карпових 21 комплетних проблема, тј. 0-1 целобројно линеарно програмирање, у коме су непознате бинарни бројеви, а ограничења морају бити задовољена,

Кананочка и стандардна форма за ЦЛП

Целобројно програмирање у каноничкој форми је представљено као:^[1]

{\begin{aligned}&{\text{maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\\&{\text{and}}&&\mathbf {x} \in \mathbb {Z} ^{n},\end{aligned}}

,

и ЦЛП у стандардној форми је представљен као

{\begin{aligned}&{\text{maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&{\text{and}}&&\mathbf {x} \in \mathbb {Z} ^{n},\end{aligned}}

где су $\mathbf {c} ,\mathbf {b}$ вектори и $A$ матрица, која има целобројне вредности. Приметити да је слично линеарном програмирању, ЦЛП који није у стандардној форми се може превести у стандардну форму елиминисањем неједнакости увођењем слабе промењиве ( $\mathbf {s}$ ) и заменом промењивих које нису знаком ограничене са разликом двеју промењивих ограничених знаком.

Пример

IP polytope with LP relaxation

Граф са десне стране показује проблем.

{\begin{aligned}\max &{\text{ }}y\\-x+y&\leq 1\\3x+2y&\leq 12\\2x+3y&\leq 12\\x,y&\geq 0\\x,y&\in \mathbb {Z} \end{aligned}}

Изводљиве целобројне тачке приказане су црвеном, а црвене испрекидане линије приказују њиховз конвексну љуску, која је најмањи полиедар који садржи све ове тачке. Плаве линије заједно са координатама икса дефинише полиедар ЛП релаксације, која је дата неједнакошћу без целовитог ограничења. Циљ оптимизације је померити црну испрекидану линију што више нагоре, док додирује полиедар. Оптимална решења целобројног проблема су тачке $(1,2)$ и $(2,2)$ које обе имају стварну вредности 2. Јединствени оптимум релаксације је $(1.8,2.8)$ са стварним вредностима 2.8. Приметити да ако је решење заокружено на најближи цео број, није изводљиво за ЦЛП.

Доказ НП-проблема

Следи смањење са минималног чвора прекривача на целобројно програмирање које ће користити као доказ за НП-проблем.

Нека $G=(V,E)$ буде неоријентисани граф. Дефинисати линеарни програм на следећи начин:

{\begin{aligned}\min \sum _{v\in V}y_{v}\\y_{v}+y_{u}&\geq 1&&\forall uv\in E\\y_{v}&\geq 0&&\forall v\in V\\y_{v}&\in \mathbb {Z} &&\forall v\in V\end{aligned}}

С обзиром на ограничења $y_{v}$ на 0 или 1, било које изводљиво решење целобројног програмирања је подскуп чворова. Прво ограничење упућује да је макар једна крајња тачка сваке гране укључена у подскуп. Због тога решење описује прекривача чвора. Поред тога дати неки чвор покривача C, $y_{v}$ може бити 1 за било које $v\in C$ и до 0 за било које $v\not \in C$ па нам даје изводљиво решење за целобројно програмирање. Тако можемо закључити да ако се смањи сума $y_{v}$ такође ћемо наћи минимум чвора прекривача.^[2]

Варијанте

Мешано целобројно линеарно програмирање (МЦЛП) укључује проблеме у којима само неке промењиве , $x_{i}$ , ограничене да буду целобројне, док је другим дозвољено да буду нецелобројне.

0-1 линеарно програмирање укључује проблеме у којима промењиве могу бити 0 или 1. Приметити да било која заокружена целобројна промењива може бити приказана као комбинација бинарних промењивих.^[3] На пример, дата целобројна промењива, $0\leq x\leq U$ , може бити изражена користећи $\lfloor \log _{2}U\rfloor +1$ бинарних промењивих:

x=x_{1}+2x_{2}+4x_{3}+\ldots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\rfloor +1}.

Примери проблема који се могу формулисати као ЦЛП

Велики број проблема се може формулисати као ЦЛП. Ту спадају

Проблем трговачког путника
Покривач чворова и други Проблем покривања
САТ проблем

Пошто је крајња верзија целобројно линеарног програмирања у НП (решења се могу наћи у полиномијалном времену) и ту су НП-потпуни проблеми који се могу полиномијално смањити на ЦЛП, последња верзија целобројног линеарног програмирања је НП-комплетни проблем.

Апликације

Постоје два главна разлога за коришћење целобројних константи приликом моделирања проблема као линеарног програма:

Целобројне промењиве представљају колићине које могу бити само цели бројеви. На пример, не могуће је направити 3.7 аутомобила.
Целобројне вредности представњају одлуке па треба да имају само решења са вредношћу 0 или 1 .

Ова разматрања се често јављају у пракси, и због тога целобројно линеарно програмирање може да се користи у многим областима апликација, од којих су неки укратко описани у наставку.

Производно планирање

Мешано целобројно програмирање има разне апликације у индустријској производњи, укључујући посао-куповине моделовања. Један важан пример се дешава у пољопривредном производном планирању које укључује одређивање производње приноса за неколико усева које могу да деле изворе (на пример, земљу, рад, капитал, семење, ђубриво, итд). Могућ циљ је максимализовати укупну производњу, без прекорачења расположивих ресурса. У неким случајевима, ово се може изразити у смислу линеарног програмирања, али промењиве морају да буду целобројне.

Планирање

Ови проблеми укључују сервисирање и распоређивање возила у саобраћајним мрежама. На пример, проблем може да укључи додељивање аутобуса или подземних железница на појединим правцима тако да сатница буде испуњена, и такође да их опреми са возачима. Овде бинарне промењиве одлуке показују да ли је аутобус или метро добио руту вожње и да ли је возач добио одређени воз или метро.

Телекомуникационе мреже

Циљ ових проблема је осмислити и инсталирати мрежу линија тако да унапред дефинисани услови комуникације буду испуњени и укупан трошак мреже буде минималан.^[4] Ово захтева оптимизацију и топологије мреже заједно са постављањем капацитета различитих линија. У многим случајевима, капацитети су ограничени да буду целобројне величине. Обично постоје, у зависности од технологије која се користи, додатне рестрикције које могу бити моделовање као линеарне неједнакости са целобројним вредностима или бинарним промењивима.

Мобилне мреже

Задатак планирања фреквенције у мобилној ГСМ мрежи укључује расподелу доступних фреквенција кроз антену тако да корисник може да се услужи, и да је интерференција сведена на минимум између антена.^[5] Овај проблем може бити формулисан као целобројно линеарно програмирање у којем бинарне промењиве показују да ли је фреквенција додељена.

Алгоритми

Наиван начин за решење ЦЛП је једноставно брисање ограничења да је x интеграл, решење одговарајућег ЛП (које се зове ЛП релаксација ЦЛП), и затим заокружити унос решења на ЛП релаксацију. Али, не само да ово решење можда неће бити оптимално, можда чак ниће бити ни изводљиво, то оно што може нарушити нека ограничења.

Коришћење укупне немодуларности

Док у већини решења ЛП неће бити засигурно оптимално, ако ЦЛП има облик $\max \mathbf {c} ^{\mathrm {T} }\mathbf {x}$ такву да $A\mathbf {x} =\mathbf {b}$ где $A,\mathbf {b} ,$ и $\mathbf {c}$ имају све целобројне улазе и $A$ је скроз унимодуларан, онда свако онсовно изводљиво решење је интеграл. Сходно томе, решење добијено симплекс алгоритмом ће сигурно бити интеграл. Да би доказали да свако изводљиво решење је интеграл, нека $\mathbf {x}$ буде произвољно основно и изводљиво решење. Пошто $\mathbf {x}$ је изводљиво, знамо да $A\mathbf {x} =\mathbf {b}$ . Нека $\mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]$ буде елемент који одговара бази колона за основна решења $\mathbf {x}$ . По дефиницији базе , постоји неки корен подматрице $B$ од $A$ са линеарном независношћу колоне такве да $B\mathbf {x} _{0}=\mathbf {b}$ .

Пошто колоне $B$ су линеарно независне и $B$ је корен, $B$ је неважан, и зато по претпоставци, $B$ је унимодуларно и $\det(B)=\pm 1$ . Такође, пошто је $B$ неважна, инвертибилна је и зато $\mathbf {x} _{0}=B^{-1}\mathbf {b}$ . По дефиницији, $B^{-1}={\frac {B^{adj}}{\det(B)}}=\pm B^{adj}$ . Приметите да $B^{adj}$ означава адјуговану матрицу $B$ и интеграл је зато што је $B$ интеграл. Због тога,

{\begin{aligned}&\Rightarrow B^{-1}=\pm B^{adj}{\text{ is integral.}}\\&\Rightarrow x_{0}=B^{-1}b{\text{ is integral.}}\\&\Rightarrow {\text{Every basic feasible solution is integral.}}\end{aligned}}

Према томе, ако је матрица $A$ ЦЛП-а скроз унимодуларна, она ће уместо коришћења ЦЛП алгоритма користити симплекс алгоритам да би се решила ЛП релаксација, а да би решење било целобројно.

Тачни алгоритми

Када матрица $A$ није скроз унимодуларна, постоје разноврсни алгоритми који се могу искористити да се тачно реши целобројно линеарно програрмирање. Једна група алгоритама је метода сечења авиона која ради тако што реши ЛП релаксацију и онда додаје ленаерна ограничења, која воде решења напред, тако да буду целобројна и без изузимања било које изводљиве тачке.

Друга група алгоритама су варијанте методе сепарација и евалуација. На пример, метод грана и рез који користи метод сепарације и евалуације и методу сечења авиона. Метод сепарације и евалуације има неке предности у односу на алгоритме који само користе методу сечења авиона. Једна од предности је да се алгоритам може завршити раније и све док не буде бар једно видљиво интеграл решење пронађено, иако није неопходно да буде оптимално, решење треба да се врати. Даље, метода сепарације и евалуације могу се користити да врате више оптималних решења.

Ленстра је 1983 показао^[6] да, када је број промењивих фиксиран, целобројно програмирање се може решити у полиномијалном времену.

Хеуристички методи

Пошто је целобројно линеарно програмирања НП-тешко, многи примери проблема су сложени и због тога неке хеуристичке методе морају да се користе. На пример, табу претрага се може користити за налажење решења за ЦЛП.^[7] Да би се користио табу претрага за решавање ЦЛП-а, кретања могу бити дефинисана као инкрементирање или декрементирање целобројно ограничене промењиве изводљивог решења, док би остале целобројно ограничене промењиве биле константне. Неограничене промењиве су онда решене. Краткорочна меморија се може састојати од претходних пробаних решења док средњорочна меморија се може састојати од вредности за целобројно ограничене промењиве које су резултирале високо објективним вредностима (под претпоставком да је ЦЛП проблем максимизације). На крају, дугорочна меморија може водити до претраге целобројних вредности, која нису претходно пробана.

Друге хеуристичке методе које могу применити ЦЛП

Планинарење
Симулирано жарење
Реактивна претрага оптимизације
Мрављи алгоритам
"Hopfield" неуралне мреже

Такође постоји велики број других специфичних хеуристичких проблема, као на пример проблем тргговачког путника. Приметите да мане хеуристичких метода јесу то да ако не нађу решење, онда се не може знати да ли је то зато што нема изводљивог решења или зато што алгоритам не може да пронађе решење. Даље, обично је немогуће да се израчуна колико је близу оптималног решења, решење које је добијеном овом методом.

Референце

^ Papadimitriou, C. H.; Steiglitz, K. (1998). Combinatorial optimization: algorithms and complexity. Mineola, NY: Dover. ISBN 978-0-486-40258-1.
^ Erickson, J. (2015). „Integer Programming Reduction” (PDF).
^ Williams, H.P. (2009). Logic and integer programming. International Series in Operations Research & Management Science. 130. ISBN 978-0-387-92280-5.
^ Borndörfer, R.; Grötschel, M. (2012). „Designing telecommunication networks by integer programming” (PDF).
^ Sharma, Deepak (2010). „Frequency Planning”.
^ H.W. Lenstra, "Integer programming with a fixed number of variables", Mathematics of operations research, Vol 8, No 8, November 1983
^ Glover, F. (1989). „Tabu search-Part II”. ORSA Journal on computing. 1 (3): 4—32. doi:10.1287/ijoc.2.1.4.

Литература

George L. Nemhauser; Wolsey, Laurence A. (1988). Integer and combinatorial optimization. Wiley. ISBN 978-0-471-82819-8.
Schrijver, Alexander (1998). Theory of linear and integer programming. John Wiley and Sons. ISBN 978-0-471-98232-6.
Wolsey, Laurence A. (1998). Integer programming. Wiley. ISBN 978-0-471-28366-9.
Bertsimas, Dimitris; Weismantel, Robert (2005). Optimization over integers. Dynamic Ideas. ISBN 978-0-9759146-2-5.
Karlof, John K. (2006). Integer programming: theory and practice. CRC Press. ISBN 978-0-8493-1914-3.
H. Paul Williams (2009). Logic and Integer Programming. Springer. ISBN 978-0-387-92279-9.
Michael Jünger; Thomas M. Liebling; Denis Naddef; George Nemhauser; William R. Pulleyblank; Gerhard Reinelt; Giovanni Rinaldi; Laurence A. Wolsey, ур. (2009). 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art. Springer. ISBN 978-3-540-68274-5.
Der-San Chen; Batson, Robert G.; Dang, Yu (2010). Applied Integer Programming: Modeling and Solution. John Wiley and Sons. ISBN 978-0-470-37306-4.

Спољашње везе

A Tutorial on Integer Programming Архивирано на сајту Wayback Machine (5. септембар 2009)
Integer Programming and Combinatorial Optimization, IPCO
The Aussois Combinatorial Optimization Workshop

[optBook-1] Papadimitriou, C. H.; Steiglitz, K. (1998). Combinatorial optimization: algorithms and complexity. Mineola, NY: Dover. ISBN 978-0-486-40258-1.

[2] Erickson, J. (2015). „Integer Programming Reduction” (PDF).

[3] Williams, H.P. (2009). Logic and integer programming. International Series in Operations Research & Management Science. 130. ISBN 978-0-387-92280-5.

[4] Borndörfer, R.; Grötschel, M. (2012). „Designing telecommunication networks by integer programming” (PDF).

[5] Sharma, Deepak (2010). „Frequency Planning”.

[6] H.W. Lenstra, "Integer programming with a fixed number of variables", Mathematics of operations research, Vol 8, No 8, November 1983

[7] Glover, F. (1989). „Tabu search-Part II”. ORSA Journal on computing. 1 (3): 4—32. doi:10.1287/ijoc.2.1.4.

[1]

[2]

[3]

[4]

[5]

[6]

[7]