Graver basis
લાગુ ગણિતમાં, ગ્રેવર પાયા બહુપદી સમયમાં રેખીય અને વિવિધ બિનરેખીય પૂર્ણાંક પ્રોગ્રામિંગ સમસ્યાઓના પુનરાવર્તિત ઉકેલોને સક્ષમ કરે છે. તેઓ જેક ઇ. ગ્રેવર દ્વારા રજૂ કરવામાં આવ્યા હતા. ગ્રોબનર પાયાના સિદ્ધાંત સાથેના તેમના જોડાણની ચર્ચા બર્ન્ડ સ્ટર્મફેલ્સ દ્વારા કરવામાં આવી હતી. ગ્રેવર પાયાના અલ્ગોરિધમિક સિદ્ધાંત અને પૂર્ણાંક પ્રોગ્રામિંગમાં તેના ઉપયોગનું વર્ણન શ્મુએલ ઓન દ્વારા કરવામાં આવ્યું છે. ઔપચારિક વ્યાખ્યા m × n પૂર્ણાંક મેટ્રિક્સનો ગ્રેવર આધાર એ ક્યારે અને બધા i માટે વ્યાખ્યાયિત કરેલ સારા આંશિક ક્રમ હેઠળ સમૂહમાં ન્યૂનતમ તત્વોનો મર્યાદિત સમૂહ છે. ઉદાહરણ તરીકે, ગ્રેવર બેસિસમાં વેક્ટર (2, −1,0), (0, −1,2), (1,0, −1), (1, −1,1) અને તેમની નકારાત્મકતાઓનો સમાવેશ થાય છે. ગ્રેવર બેઝ ઇન્ટિજર પ્રોગ્રામિંગનો ઉપયોગ કરીને ઇન્ટિજર પ્રોગ્રામિંગને ઉકેલવું એ રેખીય અસમાનતાઓની પ્રણાલીને સંતોષતા પૂર્ણાંક બિંદુઓના સમૂહ પર રેખીય અથવા બિનરેખીય ઉદ્દેશ્ય કાર્યને શ્રેષ્ઠ બનાવવાની સમસ્યા છે. ઔપચારિક રીતે, તેને પ્રમાણભૂત સ્વરૂપમાં નીચે મુજબ લખી શકાય છેઃ તે સૌથી મૂળભૂત સ્વતંત્ર ઓપ્ટિમાઇઝેશન સમસ્યાઓમાંની એક છે અને તેમાં ખૂબ જ વ્યાપક મોડેલિંગ શક્તિ અને વિવિધ ક્ષેત્રોમાં અસંખ્ય એપ્લિકેશનો છે, પરંતુ નીચે નોંધ્યા મુજબ સામાન્ય રીતે ખૂબ જ સખત ગણતરીત્મક છે. જો કે, ગ્રેવર આધારને જોતાં, રેખીય અને વિવિધ બિનરેખીય ઉદ્દેશ્ય કાર્યો સાથેની સમસ્યાને આગળ સમજાવ્યા મુજબ બહુપદી સમયમાં ઉકેલી શકાય છે. લીનિયર ઇન્ટિજર પ્રોગ્રામિંગ સૌથી વધુ અભ્યાસ કરાયેલ કેસ, જેમાં સંપૂર્ણ રીતે સારવાર કરવામાં આવે છે, તે લીનિયર ઇન્ટિજર પ્રોગ્રામિંગનો છે, એવું માની શકાય છે કે તમામ ચલ નીચે અને ઉપરથી બંધાયેલા છેઃ આવી સીમાઓ કાં તો હાથમાં એપ્લિકેશનમાં કુદરતી રીતે દેખાય છે, અથવા કોઈપણ શ્રેષ્ઠ ઉકેલો ગુમાવ્યા વિના લાગુ કરી શકાય છે. પરંતુ, રેખીય ઉદ્દેશ્ય કાર્યો સાથે પણ સમસ્યા એન. પી.-હાર્ડ છે અને તેથી સંભવતઃ બહુપદી સમયમાં ઉકેલી શકાતી નથી. જો કે, ગ્રેવર આધાર નીચેની મિલકત ધરાવે છે. દરેક શક્ય બિંદુ x માટેઃ ક્યાં તો x શ્રેષ્ઠ છે (એટલે કે, મર્યાદાઓને ધ્યાનમાં રાખીને તેને ઘટાડે છે); અથવા ત્યાં એક વેક્ટર g અસ્તિત્વમાં છે, જેમ કે x + g શક્ય છે અને (એટલે કે, x ને તેમાં ગ્રેવર આધારનો એક ઘટક ઉમેરીને સુધારી શકાય છે). તેથી, ગ્રેવર આધારને જોતાં, આઇએલપીને નીચેના સરળ પુનરાવર્તિત અલ્ગોરિધમનો ઉપયોગ કરીને બહુપદી સમયમાં ઉકેલી શકાય છે. પહેલા ધારો કે કેટલાક પ્રારંભિક શક્ય બિંદુ x આપવામાં આવ્યા છે. શક્ય હોય ત્યારે, નીચેના પુનરાવર્તનનું પુનરાવર્તન કરોઃ હકારાત્મક પૂર્ણાંક q અને તત્વ g ને એવી રીતે શોધો કે જેથી x + qg સીમાનું ઉલ્લંઘન ન કરે અને શ્રેષ્ઠ શક્ય સુધારો આપે; x: = x + qg ને અપડેટ કરો અને આગામી પુનરાવર્તન તરફ આગળ વધો. છેલ્લો બિંદુ x શ્રેષ્ઠ છે અને પુનરાવર્તનોની સંખ્યા બહુપદી છે. પ્રારંભિક શક્ય મુદ્દો શોધવા માટે, એક યોગ્ય સહાયક કાર્યક્રમ સ્થાપિત કરી શકાય છે અને સમાન રીતે ઉકેલી શકાય છે. બિનરેખીય પૂર્ણાંક પ્રોગ્રામિંગ સામાન્ય ઉદ્દેશ્ય વિધેયો f ના કિસ્સામાં વળવું, જો ચલો અમર્યાદિત હોય તો સમસ્યા હકીકતમાં અસંબદ્ધ હોઈ શકે છેઃ તે હિલ્બર્ટની 10 મી સમસ્યાના ઉકેલમાંથી અનુસરે છે (જુઓ), કે ત્યાં કોઈ અલ્ગોરિધમ અસ્તિત્વમાં નથી, જે 58 ચલોમાં ડિગ્રી 8 ની પૂર્ણાંક બહુપદી f આપવામાં આવે છે, તે નક્કી કરે છે કે તમામ 58-પરિમાણીય પૂર્ણાંક વેક્ટર પર f નું લઘુતમ મૂલ્ય 0 છે કે નહીં. જો કે, જ્યારે ચલ બંધાયેલા હોય, ત્યારે સમસ્યાને બહુપદી સમયમાં ગ્રેવર બેસિસનો ઉપયોગ કરીને કેટલાક બિનરેખીય ઉદ્દેશ્ય કાર્યો માટે ઉકેલી શકાય છે, જેમાં નીચેનાનો સમાવેશ થાય છેઃ સ્વરૂપના અલગ કરી શકાય તેવા-બહિર્મુખ કાર્યો; ખાસ કરીને દરેક હકારાત્મક પૂર્ણાંક p માટે p-ધોરણ; સંયુક્ત-કોન્કેવ કાર્યો f (x) = g (Wx), જ્યાં W એ d નિશ્ચિત સાથે d × n પૂર્ણાંક મેટ્રિક્સ છે, અને જ્યાં g એ d-ચલ અંતર્મુખ કાર્ય છે; ચોક્કસ (in)-નિશ્ચિત વર્ગાત્મક અને ઉચ્ચ ડિગ્રી બહુપદી કાર્યો. કેટલીક એપ્લિકેશનો બહુ-પરિમાણીય કોષ્ટકો ત્રણ-પરિમાણીય કોષ્ટકો પર નીચેની ઓપ્ટિમાઇઝેશન સમસ્યાને ધ્યાનમાં લો, જેમાં, બિન-નકારાત્મક પૂર્ણાંકો (જેનું મહત્તમ મૂલ્ય સ્પષ્ટપણે ઉપરના તમામ ચલોને બંધાય છે) સાથે નિર્ધારિત રેખા રકમ હોય છે. આ પ્રણાલીના વ્યાખ્યાયિત મેટ્રિક્સને (lm + ln + mn) × (lmn) દ્વારા દર્શાવો. નોંધ લો કે આ મેટ્રિક્સ સામાન્ય રીતે સંપૂર્ણપણે એકરૂપ નથી. તેમ છતાં, તેમાં દર્શાવવામાં આવ્યું હતું કે દરેક નિશ્ચિત l અને m માટે, તેના ગ્રેવર આધારની ગણતરી તે સમયે કરી શકાય છે જે n માં બહુપદી છે. ઉપર ઉલ્લેખિત પરિણામો પછી આ સમસ્યાને નિશ્ચિત l અને m અને ચલ n માટે બહુપદી સમયમાં ઉકેલવા માટે પરવાનગી આપે છે. નોંધ લો કે જો કોષ્ટકની માત્ર એક બાજુ l નિશ્ચિત હોય (l = 3 સાથે પણ) જ્યારે m અને n બંને ચલ હોય, તો સમસ્યા NP સખત છે, જેમ કે તેમાં બતાવ્યા પ્રમાણે. વધુ સામાન્ય રીતે, સમાન હકારાત્મક પરિણામો ઉચ્ચ-પરિમાણીય કોષ્ટક સમસ્યાઓ માટે હોય છે (માં રજૂ કરાયેલ): દરેક નિશ્ચિત d માટે અને, ચલ n અને નિર્ધારિત માર્જિનવાળા કોષ્ટકો પર (બિન)-રેખીય ઓપ્ટિમાઇઝેશન બહુપદી સમયમાં કરી શકાય છે. આ આંકડાકીય ડેટાબેઝમાં સુરક્ષા સમસ્યાઓ અને ગોપનીયતા દાખલ કરવા માટે વધુ એપ્લિકેશનો ધરાવે છે. મલ્ટી-કોમોડિટી પ્રવાહો પુરવઠો, વપરાશ અને ક્ષમતાની મર્યાદાઓને આધિન m સપ્લાયરો પાસેથી n ગ્રાહકો સુધી k પ્રકારની પૂર્ણાંક કોમોડિટીના રૂટની પૂર્ણાંક મલ્ટી-કોમોડિટી પ્રવાહ સમસ્યાને ધ્યાનમાં લો, જેથી ચાપ પર રેખીય અથવા ભીડ-આધારિત બહિર્મુખ ખર્ચનો સરવાળો ઘટાડી શકાય. પછી દરેક નિશ્ચિત k અને m માટે, વ્યાખ્યાયિત પ્રણાલીના ગ્રેવર આધારની ગણતરી કરી શકાય છે અને પરિણામી વિભાજીત-બહિર્મુખ ઉદ્દેશ્ય કાર્યને સમયસર ઘટાડી શકાય છે જે ગ્રાહકોની ચલ સંખ્યા n માં બહુપદી છે અને બાકીના ડેટામાં છે. અન્ય એપ્લિકેશનો ગ્રેવર પાયાના અલ્ગોરિધમિક સિદ્ધાંતની ઘણી એપ્લિકેશનોમાં પણ સમાવેશ થાય છેઃ સ્ટોકેસ્ટિક ઇન્ટિજર પ્રોગ્રામિંગ, એન-ફોલ્ડ ઇન્ટિજર પ્રોગ્રામિંગ, એન-ફોલ્ડ 4-બ્લોક ડિકોમ્પોઝેબલ ઇન્ટિજર પ્રોગ્રામિંગ, ક્લસ્ટરિંગ, આંકડાકીય ડેટાબેઝમાં જાહેરાત નિયંત્રણ અને અવિભાજ્ય વસ્તુઓની વાજબી ફાળવણી. આમાંની કેટલીક એપ્લિકેશનોમાં સંબંધિત ગ્રેવર આધારની ગણતરી બહુપદી સમયમાં કરી શકાતી નથી, પરંતુ પરોક્ષ રીતે તેનો ઉપયોગ કરી શકાય છે જે તેને બહુપદી સમયમાં ઉપયોગ કરવાની મંજૂરી આપે છે. સર્વવ્યાપકતા અને પરિમાણ તે દર્શાવવામાં આવ્યું હતું કે દરેક (બંધાયેલ) પૂર્ણાંક પ્રોગ્રામિંગ સમસ્યા ચોક્કસપણે 3 × m × n કોષ્ટકની સમસ્યાની સમકક્ષ છે જે કેટલાક m અને n અને કેટલાક રેખા સરવાળા માટે ઉપર ચર્ચા કરવામાં આવી છે. આમ, આવી 3 × m × n કોષ્ટક સમસ્યાઓ પૂર્ણાંક પ્રોગ્રામિંગ માટે સાર્વત્રિક છે. વધુમાં, દરેક નિશ્ચિત m માટે, પૂર્ણાંક કાર્યક્રમોના પરિણામી વર્ગને ઉપર વર્ણવેલ પુનરાવર્તિત ગ્રેવર આધાર પદ્ધતિ દ્વારા બહુપદી સમયમાં ઉકેલી શકાય છે. તેથી કોષ્ટકની પહોળાઈ m તમામ પૂર્ણાંક પ્રોગ્રામિંગ સમસ્યાઓનું પરિમાણ પ્રદાન કરે છે. પૂર્ણાંક પ્રોગ્રામિંગ માટે અંદાજોની પદાનુક્રમ ઉપર ચર્ચા કરાયેલ સાર્વત્રિક 3 × m × n કોષ્ટક સમસ્યાને વ્યાખ્યાયિત કરતા મેટ્રિક્સના ગ્રેવર આધાર દ્વારા સૂચવવામાં આવે છે. ના ઘટકો 3 × m × n કોષ્ટકો છે જેમાં તમામ રેખાનો સરવાળો 0 ની બરાબર છે. આવા કોષ્ટકનો પ્રકાર તેના બિન-શૂન્ય 3 × m સ્તરોની સંખ્યા છે. તે તારણ આપે છે કે ત્યાં એક મર્યાદિત ગ્રેવર જટિલતા વિધેય g (m) છે જેમ કે કોઈપણ n માટે, ગ્રેવર આધારના કોઈપણ તત્વનો પ્રકાર મહત્તમ g (m) હોય છે. તે અનુસરે છે કે ગ્રેવર આધાર એ ગ્રેવર આધારની યોગ્ય રીતે જડિત નકલોનું જોડાણ છે. મનસ્વી પૂર્ણાંક પ્રોગ્રામિંગ સમસ્યાને વ્યવહારમાં લગભગ ઉકેલવા માટે, નીચે પ્રમાણે આગળ વધો. ઉપર નોંધ્યું છે તે સર્વવ્યાપકતા દ્વારા સક્ષમ કરાયેલ યોગ્ય 3 × m × n કોષ્ટક સમસ્યામાં પ્રથમ તેને એમ્બેડ કરો. હવે અંદાજોની નીચેની પદાનુક્રમ લાગુ કરો. આ પદાનુક્રમના સ્તર k પર, ચાલો મહત્તમ k પર માત્ર તે જ પ્રકારનાં તત્વોનો સમાવેશ કરતો સબસેટ બનીએ; 3 × m × n કોષ્ટક સમસ્યામાં જડિત પૂર્ણાંક પ્રોગ્રામિંગ સમસ્યા માટે શક્ય તેટલું સારું શક્ય બિંદુ મેળવવા માટે શક્ય તેટલા લાંબા સમય સુધી પુનરાવર્તિત અલ્ગોરિધમમાં આ અંદાજનો ઉપયોગ કરો; જો આ બિંદુનું ઉદ્દેશ્ય કાર્ય મૂલ્ય સંતોષકારક હોય (કહો, રેખીય પ્રોગ્રામિંગ છૂટછાટના મૂલ્યની તુલનામાં), તો આ બિંદુનો ઉપયોગ કરો; અન્યથા k માં વધારો કરો અને પદાનુક્રમના આગલા સ્તર પર આગળ વધો. તે દર્શાવી શકાય છે કે કોઈપણ નિશ્ચિત સ્તર k માટે, ગ્રેવર આધારનો અંદાજ બહુપદી કાર્ડિનાલિટી ધરાવે છે અને તેટલા સમયમાં ગણતરી કરી શકાય છે. ફિક્સ્ડ પેરામીટર ટ્રેક્ટેબિલિટીઃ બહુપદીથી ક્યુબિક સમયની જટિલતા ઉપર ચર્ચા કરવામાં આવેલી કેટલીક એપ્લિકેશનોને હલ કરવાની સમય જટિલતા, જેમ કે બહુ-પરિમાણીય કોષ્ટક સમસ્યાઓ, બહુ-સુસંગતતા પ્રવાહ સમસ્યાઓ અને એન-ફોલ્ડ પૂર્ણાંક પ્રોગ્રામિંગ સમસ્યાઓ, સંબંધિત ગ્રેવર આધારની મુખ્યતા દ્વારા પ્રભુત્વ ધરાવે છે, જે સામાન્ય રીતે મોટા ડિગ્રી જી સાથે બહુપદી છે જે સિસ્ટમની યોગ્ય ગ્રેવર જટિલતા છે. વધુ ઝડપી અલ્ગોરિધમ રજૂ કરવામાં આવે છે, જે દરેક પુનરાવર્તન પર ક્યૂ પોઝિટિવ પૂર્ણાંક સાથે x + qg અને જી તત્વને સ્પષ્ટપણે ગ્રેવર આધાર બનાવ્યા વિના, ઘન સમયમાં શોધી કાઢે છે, સિસ્ટમને ધ્યાનમાં લીધા વગર. પરિમાણિત જટિલતાની પરિભાષામાં, આ સૂચવે છે કે આ બધી સમસ્યાઓ યોગ્ય રીતે પરિમાણિત છે, અને ખાસ કરીને l × m × n કોષ્ટકની સમસ્યાઓ l અને m દ્વારા પરિમાણિત છે, જે નિશ્ચિત પરિમાણો છે. ગોર્ડનનું લેમ્મા પણ જુઓ-પૂર્ણાંક મેટ્રિસીસના શૂન્ય સમૂહો સાથે સંબંધિત અન્ય સાધન. સંદર્ભો રેખીય પ્રોગ્રામિંગ