Кіріспе
Бүтін сандарға шектелген математикалық оңтайландыру проблемасы – айнымалыларының кейбірі немесе барлығы бүтін сандармен шектелген математикалық оңтайландыру немесе мүмкіндік туралы бағдарлама. Көп жағдайда бұл термин бүтін санды сызықтық бағдарламалауды (ILP) білдіреді, онда мақсаттық функция және шектеулер (бүтін сан шектеулерінен басқа) сызықтық болады. Бүтін санды бағдарламалау NP-толық. Атап айтқанда, белгісіздер екілік болып табылатын және тек шектеулерді қанағаттандыру қажеттілігі бар 0–1 бүтін санды сызықтық бағдарламалаудың ерекше жағдайы – Карптың 21 NP-толық проблемасының бірі. Егер кейбір шешім айнымалылары дискретті болмаса, онда бұл аралас бүтін санды бағдарламалау проблемасы деп аталады.
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear. Integer programming is NP complete. In particular, the special case of 0–1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP complete problems. If some decision variables are not discrete, the problem is known as a mixed integer programming problem.
Мысал
Оң жақтағы график келесі мәселені көрсетеді. Қолжетімді бүтін нүктелер қызыл түспен көрсетілген, ал қызыл үзіліс сызықтары олардың дөңгелек қабығын көрсетеді, яғни осы нүктелердің барлығын қамтитын ең кішкентай дөңгелек көпбұрыш. Көк сызықтар координаталық осьтермен бірге LP релаксациясының көпбұрышын анықтайды, ол бүтіндік шектеусіз теңсіздіктермен берілген. Оптимизацияның мақсаты – қара үзіліс сызығын полиэдрге жанасқан күйде мүмкін болғанша жоғары жылжыту. Бүтін сандық мәселенің оңтайлы шешімдері – нүктелер және олардың екеуінің де мақсаттық функциясының мәні 2-ге тең. Релаксацияның бірегей оңтайлы мәні 2,8 мақсаттық функциясының мәнімен. Егер релаксация шешімі ең жақын бүтін сандарға дейін дөңгеленетін болса, ол ILP үшін қабылдамайды.
NP-қаттылықтың дәлелі
Келесі, NP-нің қиындығын дәлелдеу үшін қолданылатын ең кішкентай төбелік жамылғыны бүтін сандық бағдарламалауға келтіру. Бұл бағытталмаған граф болсын. Сызықтық бағдарламаны былай анықтаймыз: шектеулер мәнін 0 немесе 1-ге дейін шектейтіндіктен, бүтін сандық бағдарламаның кез келген мүмкін шешімі – төбелердің ішкі жиыны. Бірінші шектеу әрбір қабырғаның кем дегенде бір соңғы нүктесі осы ішкі жиынға кіретінін көрсетеді. Сондықтан, шешім төбелік жамылғыны сипаттайды. Сонымен қатар, егер берілген төбелік жамылғы C болса, кез келген үшін 1-ге, ал үшін 0-ге тең қоюға болады, осылайша бүтін сандық бағдарламаның мүмкін шешімін аламыз. Осылайша, егер біз қосындысын азайтатын болсақ, онда ең кішкентай төбелік жамылғыны да табамыз.
Given that the constraints limit to either 0 or 1, any feasible solution to the integer program is a subset of vertices. The first constraint implies that at least one end point of every edge is included in this subset. Therefore, the solution describes a vertex cover. Additionally given some vertex cover C, can be set to 1 for any and to 0 for any thus giving us a feasible solution to the integer program. Thus we can conclude that if we minimize the sum of we have also found the minimum vertex cover.
Нұсқалар
Аралас бүтін санды сызықтық бағдарламалау (MILP) – айнымалылардың бір бөлігі ғана бүтін сан болуымен шектелген, ал қалғандары бүтін сан болмауы мүмкін мәселелерді қарастырады. Нөл-бір сызықтық бағдарламалау (немесе бинарлық бүтін санды бағдарламалау) – айнымалылардың 0 немесе 1 болуымен ғана шектелген мәселелерді қамтиды. Кез келген шектелген бүтін санды айнымалыны бинарлық айнымалылардың комбинациясы түрінде көрсетуге болады. Мысалы, егер берілген бүтін санды айнымалы болса, оны бинарлық айнымалылар арқылы келесідей өрнектеуге болады:
Өндірісті жоспарлау
Аралас бүтін сандық бағдарламалау өнеркәсіптік өндірісте көптеген қолданысқа ие, оның ішінде жұмыс орталықтарын модельдеу де бар. Маңызды мысал – ауыл шаруашылығы өндірісін жоспарлау, онда бірнеше дақылдар үшін өнімділікті анықтау қажет, олар бірдей ресурстарды пайдалана алады (мысалы, жер, еңбек, капитал, тұқым, тыңайтқыштар және т.б.). Мүмкін болатын мақсат – қолда бар ресурстар шегінде жалпы өндірісті максималды деңгейге жеткізу. Кейбір жағдайларда, мұны сызықтық бағдарлама түрінде бейнелеуге болады, бірақ айнымалылардың мәні бүтін санмен берілуі тиіс.
Жоспарлау
Бұл мәселелер көлік желілеріндегі қызмет көрсету және көлік құралдарын жоспарлаумен байланысты. Мысалы, бір мәселе автобустарды немесе метроны жеке маршруттарға тағайындауды, сондай-ақ оларды жүргізушілермен қамтамасыз етуді қамтиды. Мұнда екілік шешім айнымалылары автобус немесе метро маршрутқа тағайындалған-тағайындалмағандығын және жүргізушінің нақты пойызға немесе метроға тағайындалған-тағайындалмағандығын көрсетеді. ӨзараExclusive және/немесе технологиялық тұрғыдан тәуелді жобаларды таңдау мәселесін шешу үшін нөл-бір бағдарламалау әдісі табысты қолданылды. Бұл – барлық шешім айнымалылары бүтін сандар болатын бүтін санды бағдарламалаудың ерекше жағдайы. Айырмалы тек нөл немесе бір мәнін қабылдауы мүмкін.
Аумақтық бөлік
Аумақтық бөлу немесе аудандастыру мәселелері – географиялық аймақты әртүрлі критерийлер мен шектеулерді ескере отырып, кейбір операцияларды жоспарлау мақсатында аудандарға бөлуден тұрады. Осы мәселенің негізгі талаптары: аумақтың біртізділігі, ықшамдылығы, тепе-теңдігі немесе әділеттілігі, табиғи шекараларды сақтау және әлеуметтік-экономикалық жағынан біртектілік. Мұндай мәселелердің қолданылу салалары: сайлау округтерін құру, мектеп округтерін құру, денсаулық сақтау округтерін құру және қоқыс тастауды басқару округтерін құру.
Телекоммуникациялық желілер
Бұл мәселелердің мақсаты – белгіленген байланыс талаптарын қанағаттандырып, желінің жалпы құнын ең төменгі деңгейге түсіру үшін сызықтар желісін жобалау болып табылады. Бұл желі топологиясын оңтайландырумен қатар, әртүрлі сызықтардың сыйымдылығын анықтауды қажет етеді. Көп жағдайларда, сыйымдылықтар бүтін сандармен шектеледі. Әдетте, қолданылатын технологияға байланысты, бүтін немесе екілік айнымалылары бар сызықтық теңсіздіктер түрінде модельдеуге болатын қосымша шектеулер болады.
Ұялы байланыс желілері
GSM ұялы байланыс желілеріндегі жиілік жоспарлау міндеті қолданыстағы жиіліктерді антенналарға бөлу арқылы пайдаланушыларға қызмет көрсетуді және антенналар арасындағы кедергіні азайтуды қамтиды. Бұл мәселені екілік айнымалылары антеннаға жиілік тағайындалғандығын көрсететін бүтін сандық сызықтық бағдарлама ретінде қоюға болады.
Алгоритмдер
ILP-ді шешудің ең қарапайым жолы – x-тің бүтін сан болуын талап ететін шектеуді алып тастап, сәйкес келетін LP-ні шешу (бұл ILP-нің LP-ге дейін жеңілдетілген түрі деп аталады), содан кейін LP-ге дейін жеңілдетілген түрінің шешіміндегі мәндерді дөңгелектеу. Бірақ, мұндай шешім ең жақсысы болмауы мүмкін, тіпті орындалмай да қалуы мүмкін; яғни, ол кейбір шектеулерді бұзуы мүмкін.
Нақты алгоритмдер
Матрица толығымен модульді емес болған жағдайда, бүтін сандық сызықтық бағдарламаларды нақты шешу үшін қолданылатын әртүрлі алгоритмдер бар. Алгоритмдердің бір класы – жазықтықтарды кесу әдістері, олар сызықтық бағдарламаның (LP) жеңілдетілген түрін шешіп, содан кейін кез келген бүтін мүмкін болатын нүктені жоймай, шешімді бүтін санға жақындататын сызықтық шектеулер қосады. Алгоритмдердің тағы бір класы – тармақталу және шектеу әдісінің түрлері. Мысалы, тармақталу және кесу әдісі, ол тармақталу және шектеу әдістерін біріктіреді. Тармақталу және шектеу алгоритмдері жазықтықтарды кесу арқылы ғана шешетін алгоритмдерге қарағанда бірнеше артықшылықтарға ие. Бір артықшылығы – алгоритмдер ертерек тоқтатылуы мүмкін, және ең болмағанда бір бүтін шешім табылған жағдайда, мүмкін, бірақ міндетті түрде оңтайлы емес шешім қайтарылуы мүмкін. Бұдан өзге, сызықтық бағдарламаның жеңілдетілген түрінің шешімдері қайтарылған шешімнің оңтайлылықтан қаншалықты алшақ екенін бағалау үшін қолданылуы мүмкін. Соңында, тармақталу және шектеу әдістері бірнеше оңтайлы шешімдерді қайтару үшін де қолданылуы мүмкін.
Кіші сандағы айнымалылар үшін нақты алгоритмдер
М н н бүтін сан матрицасы және м н 1 бүтін сан векторы деп алайық. Біз мүмкіндік туралы проблемаға назар аударамыз, яғни n x 1 векторды қанағаттандыратын n бар ма, жоқ па, анықтауға арналған. V – матрицадағы коэффициенттердің ең жоғары абсолюттік мәні болсын. Егер n (айнымалылар саны) тұрақты шама болса, онда мүмкіндік туралы проблема m және log V полиномымен өлшенетін уақытта шешіледі. Бұл n=1 жағдайы үшін тривиальды. n=2 жағдайы 1981 жылы Герберт Скарфпен шешілді. Жалпы жағдай 1983 жылы Хендрик Ленстра Ласло Ловас пен Питер ван Эмде Боастың идеяларын біріктіріп шешті. Дойньон теоремасы бойынша, егер шектеулердің кез келген ішкі жиыны мүмкін болса, онда бүтін сандық бағдарлама мүмкін болады. Бұл нәтижені LP типтес проблемаларға арналған алгоритмдермен біріктіретін әдіс, бүтін сандық бағдарламаларды m-ға сызықты және n-ға қатысты тұрақты параметрлік (бірақ ықтимал екі экспоненциалды) уақытта шешуге мүмкіндік береді, бұл уақыттың ұзақтығына тәуелді емес.
0-1 ILP ерекше жағдайында Ленстра алгоритмі толық санауға тең: барлық мүмкін шешімдердің саны белгілі (2n), және әр шешімнің мүмкіндігін тексеру poly(m, log V) уақытында орындалуы мүмкін. Жалпы жағдайда, әр айнымалы кез келген бүтін сан болуы мүмкін болғандықтан, толық санау мүмкін емес. Бұл жерде Ленстра алгоритмі сандар геометриясынан алынған идеяларды қолданады. Ол бастапқы мәселені келесі қасиеті бар эквивалентті мәселеге түрлендіреді: шешімнің болуы анық немесе n-ші айнымалының мәні n функциясымен шектелген интервалға жатады. Соңғы жағдайда, мәселе төмен өлшемді мәселелердің шектелген санына дейін қысқартылады. Алгоритмнің орындалу уақытының күрделілігі бірнеше рет жақсартылды:
Let V be the maximum absolute value of the coefficients in and If n (the number of variables) is a fixed constant, then the feasibility problem can be solved in time polynomial in m and log V. This is trivial for the case n=1. The case n=2 was solved in 1981 by Herbert Scarf. The general case was solved in 1983 by Hendrik Lenstra, combining ideas by László Lovász and Peter van Emde Boas. Doignon's theorem asserts that an integer program is feasible whenever every subset of constraints is feasible; a method combining this result with algorithms for LP type problems can be used to solve integer programs in time that is linear in and fixed parameter tractable (but possibly doubly exponential) in , with no dependence on
In the special case of 0 1 ILP, Lenstra's algorithm is equivalent to complete enumeration: the number of all possible solutions is fixed (2n), and checking the feasibility of each solution can be done in time poly(m, log V). In the general case, where each variable can be an arbitrary integer, complete enumeration is impossible. Here, Lenstra's algorithm uses ideas from Geometry of numbers. It transforms the original problem into an equivalent one with the following property: either the existence of a solution is obvious, or the value of (the n th variable) belongs to an interval whose length is bounded by a function of n. In the latter case, the problem is reduced to a bounded number of lower dimensional problems. The run time complexity of the algorithm has been improved in several steps:
Ленстраның бастапқы алгоритмі орындалу уақытын жақсарған алгоритммен ұсынды.
Франк пен Тардос орындалу уақытын жақсарған алгоритммен ұсынды.
Дадуш орындалу уақытын жақсарған алгоритммен ұсынды.
Рейс пен Ротвосс орындалу уақытын жақсарған алгоритммен ұсынды.
Dadush presented an improved algorithm with run time
Reis and Rothvoss presented an improved algorithm with run time .
Бөлшекті бүтін сандарды бағдарламалау
Көп жағдайларда, бүтін сандар бағдарламасын анықтайтын матрица сиректеу болады. Әсіресе, бұл матрицаның блок құрылымы болған кезде орын алады, және мұндай жағдай көптеген қолданыстарда кездеседі. Матрицаның сиректігін былай өлшеуге болады: графиктің төбелері матрицаның бағаналарына сәйкес келеді, егер матрицаның бір қатарында екі бағанның да нөлден өзге жазбалары болса, онда олардың арасында жиек пайда болады. Балама ретінде, төбелер айнымалыларға сәйкес келеді, және егер екі айнымалы бір теңсіздікте кездессе, онда олардың арасында жиек пайда болады. Матрицаның сиректік өлшемі – матрица графигінің ағаш тереңдігі мен оның транспозының графигінің ағаш тереңдігінің ең кішісі. Матрицаның сандық өлшемі – оның кез келген жазбасының абсолюттік мәнінің максималдығы. Бүтін сандар бағдарламасының айнымалыларының саны болсын. 2018 жылы бүтін сандар бағдарламасының күшті полиномиалды және параметрленген уақытта шешілуі мүмкін екендігі көрсетілді, параметр ретінде сиректік өлшемі қолданылады. Яғни, есептеуге болатын қандай да бір функция және тұрақты үшін, бүтін сандар бағдарламасы уақыт ішінде шешіледі. Атап айтқанда, бұл уақыт оң жақ бөлігі мен мақсаттық функцияға тәуелсіз. Сонымен қатар, классикалық Ленстра нәтижесінен айырмашылығы, онда айнымалылардың саны параметр болып табылады, мұнда айнымалылардың саны кірістің өзгермелі бөлігі болып табылады.