LP-type problem
એલ્ગોરિધમ્સના અભ્યાસમાં, એલ. પી.-પ્રકારની સમસ્યા (જેને સામાન્યીકૃત રેખીય પ્રોગ્રામ પણ કહેવાય છે) એ એક ઓપ્ટિમાઇઝેશન સમસ્યા છે જે ઓછા-પરિમાણીય રેખીય પ્રોગ્રામ્સ સાથે ચોક્કસ ગુણધર્મો વહેંચે છે અને તે સમાન અલ્ગોરિધમ્સ દ્વારા ઉકેલી શકાય છે. એલ. પી.-પ્રકારની સમસ્યાઓમાં ઘણી મહત્વપૂર્ણ ઓપ્ટિમાઇઝેશન સમસ્યાઓનો સમાવેશ થાય છે જે પોતે રેખીય કાર્યક્રમો નથી, જેમ કે આપેલ સમતલીય બિંદુઓનો સમૂહ ધરાવતું સૌથી નાનું વર્તુળ શોધવાની સમસ્યા. તેઓ સમસ્યાને વ્યાખ્યાયિત કરતા તત્વોની સંખ્યામાં રેખીય અને સમસ્યાના પરિમાણમાં સબએક્સપોનેન્શિયલ હોય તેવા સમયની માત્રામાં રેન્ડમાઇઝ્ડ અલ્ગોરિધમ્સના સંયોજન દ્વારા ઉકેલી શકાય છે. વ્યાખ્યા એલ. પી.-પ્રકારની સમસ્યાઓને એવી સમસ્યાઓ તરીકે વ્યાખ્યાયિત કરવામાં આવી હતી જેમાં એકને ઇનપુટ તરીકે ઘટકોના મર્યાદિત સમૂહ તરીકે આપવામાં આવે છે, અને એક કાર્ય કે જે સંપૂર્ણપણે ક્રમબદ્ધ સમૂહમાંથી મૂલ્યોના સબસેટ્સને મેપ કરે છે. કાર્ય બે મુખ્ય ગુણધર્મોને સંતોષવા માટે જરૂરી છેઃ એકવિધતાઃ દરેક બે સમૂહો માટે, f (A) ≤ f (B) ≤ f (S). સ્થાનઃ દરેક બે સમૂહો માટે અને દરેક ઘટક માટે, જો, તો. એલ. પી.-પ્રકારની સમસ્યાનો આધાર એ ગુણધર્મ સાથેનો સમૂહ છે કે જેનો દરેક યોગ્ય સબસેટ તેના કરતા નાનું મૂલ્ય ધરાવે છે, અને એલ. પી.-પ્રકારની સમસ્યાના પરિમાણ (અથવા સંયુક્ત પરિમાણ) ને આધારની મહત્તમ મુખ્યતા તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. એવું માનવામાં આવે છે કે ઓપ્ટિમાઇઝેશન અલ્ગોરિધમ ફક્ત એવા સમૂહો પર કાર્યનું મૂલ્યાંકન કરી શકે છે જે પોતે આધાર છે અથવા જે આધારમાં એક તત્વ ઉમેરીને રચાય છે. વૈકલ્પિક રીતે, અલ્ગોરિધમ બે આદિમ કામગીરીઓ સુધી મર્યાદિત હોઈ શકે છેઃ એક ઉલ્લંઘન પરીક્ષણ જે આધાર અને તત્વ માટે નક્કી કરે છે કે નહીં, અને એક આધાર ગણતરી કે જે (સમાન ઇનપુટ્સ સાથે)} નો આધાર શોધે છે. અલ્ગોરિધમ માટેનું કાર્ય ફક્ત આ પ્રતિબંધિત મૂલ્યાંકન અથવા પ્રિમિટિવ્સનો ઉપયોગ કરીને મૂલ્યાંકન કરવાનું છે. ઉદાહરણો અને ઉપયોગો એક રેખીય કાર્યક્રમને બિન-નકારાત્મક વાસ્તવિક ચલની પ્રણાલી દ્વારા વ્યાખ્યાયિત કરી શકાય છે, જે રેખીય અસમાનતાના અવરોધોને આધિન હોય છે, સાથે સાથે બિન-નકારાત્મક રેખીય ઉદ્દેશ્ય કાર્યને ઘટાડી શકાય છે. આને એલ. પી.-પ્રકારની સમસ્યાઓના માળખામાં અવરોધોનો સમૂહ બનાવીને મૂકી શકાય છે, અને (અવરોધોના સબસેટ માટે) દ્વારા વ્યાખ્યાયિત નાના રેખીય પ્રોગ્રામના લઘુતમ ઉદ્દેશ્ય કાર્ય મૂલ્ય તરીકે વ્યાખ્યાયિત કરી શકાય છે. યોગ્ય સામાન્ય સ્થિતિ ધારણાઓ સાથે (સમાન શ્રેષ્ઠ ઉદ્દેશ્ય કાર્ય મૂલ્ય ધરાવતા બહુવિધ ઉકેલ બિંદુઓને રોકવા માટે), આ એલ. પી.-પ્રકારની સમસ્યાની એકવિધતા અને સ્થાનની જરૂરિયાતોને સંતોષે છે, અને ચલની સંખ્યા જેટલું સંયુક્ત પરિમાણ ધરાવે છે. તેવી જ રીતે, એક પૂર્ણાંક પ્રોગ્રામ (રેખીય પ્રોગ્રામની જેમ રેખીય અવરોધોનો સંગ્રહ અને રેખીય ઉદ્દેશ્ય કાર્ય ધરાવે છે, પરંતુ વધારાના પ્રતિબંધ સાથે કે ચલોએ માત્ર પૂર્ણાંક મૂલ્યો જ લેવા જોઈએ) એક એલ. પી.-પ્રકારની સમસ્યાની એકવિધતા અને સ્થાનિક ગુણધર્મો બંનેને, રેખીય પ્રોગ્રામ્સની જેમ જ સામાન્ય સ્થિતિ ધારણાઓ સાથે સંતોષે છે. ના સિદ્ધાંતો અને દર્શાવે છે કે, ચલ સાથેના પૂર્ણાંક પ્રોગ્રામ માટે, સંયોજન પરિમાણ મહત્તમ છે. કોમ્પ્યુટેશનલ ભૂમિતિમાં ઘણી કુદરતી ઓપ્ટિમાઇઝેશન સમસ્યાઓ એલ. પી.-પ્રકાર છેઃ વર્તુળની સૌથી નાની સમસ્યા એ છે કે સમતલમાં આપેલ બિંદુઓનો સમૂહ ધરાવતા વર્તુળની લઘુતમ ત્રિજ્યા શોધવાની સમસ્યા છે. તે એકવિધતાને સંતોષે છે (વધુ બિંદુઓ ઉમેરવાથી માત્ર વર્તુળ મોટું થઈ શકે છે) અને સ્થાન (જો સમૂહ માટેના સૌથી નાના વર્તુળમાં અને હોય, તો તે જ વર્તુળમાં પણ હોય છે). કારણ કે સૌથી નાનું વર્તુળ હંમેશા કેટલાક ત્રણ બિંદુઓ દ્વારા નક્કી કરવામાં આવે છે, સૌથી નાનું વર્તુળ સમસ્યા સંયુક્ત પરિમાણ ત્રણ ધરાવે છે, તેમ છતાં તેને દ્વિ-પરિમાણીય યુક્લિડિયન ભૂમિતિ દ્વારા વ્યાખ્યાયિત કરવામાં આવે છે. વધુ સામાન્ય રીતે, પરિમાણોમાં બિંદુઓનો સૌથી નાનો ઘેરાયેલો દડો સંયુક્ત પરિમાણની એલ. પી.-પ્રકારની સમસ્યા બનાવે છે. વર્તુળની સૌથી નાની સમસ્યાને દડાઓના સમૂહને ઘેરતા સૌથી નાના દડા, દડાઓના દરેક સમૂહને સ્પર્શતા અથવા તેની આસપાસ ફરતા સૌથી નાના દડા, ભારિત 1-કેન્દ્રની સમસ્યા અથવા બ્રેગમેન વિચલન દ્વારા વ્યાખ્યાયિત અંતર સાથેની જગ્યા જેવી બિન-યુક્લિડિયન જગ્યાઓમાં સમાન નાના ઘેરાયેલા દડાની સમસ્યાઓને સામાન્ય બનાવી શકાય છે. સૌથી નાનું ઘેરાયેલું લંબગોળ શોધવાની સંબંધિત સમસ્યા પણ એલ. પી.-પ્રકારની સમસ્યા છે, પરંતુ મોટા સંયોજન પરિમાણ સાથે. ચાલો-પરિમાણીય યુક્લિડિયન અવકાશમાં બહિર્મુખ સમૂહોનો ક્રમ હોઈએ, અને ધારો કે આપણે આ ક્રમનો સૌથી લાંબો ઉપસર્ગ શોધવા માંગીએ છીએ જે સામાન્ય આંતરછેદ બિંદુ ધરાવે છે. આને એલ. પી.-પ્રકારની સમસ્યા તરીકે વ્યક્ત કરી શકાય છે જેમાં જ્યાં કી એ નો પ્રથમ સભ્ય છે જે એ ના છેદતા ઉપસર્ગ સાથે સંબંધિત નથી, અને જ્યાં જો આવા કોઈ સભ્ય ન હોય તો. આ પ્રણાલીનું સંયુક્ત પરિમાણ છે. ધારો કે આપણને ત્રિ-પરિમાણીય જગ્યામાં અક્ષ-સંરેખિત લંબચોરસ બોક્સનો સંગ્રહ આપવામાં આવ્યો છે, અને જગ્યાના હકારાત્મક અષ્ટકમાં નિર્દેશિત એક રેખા શોધવા માંગીએ છીએ જે તમામ બોક્સમાંથી પસાર થાય છે. આને સંયુક્ત પરિમાણ 4 સાથે એલ. પી. પ્રકારની સમસ્યા તરીકે વ્યક્ત કરી શકાય છે. બે બહિર્મુખ પોલીટોપ વચ્ચેનું સૌથી નજીકનું અંતર શોધવાની સમસ્યા, જે તેમના શિરોબિંદુઓના સમૂહ દ્વારા નિર્દિષ્ટ કરવામાં આવે છે, તેને એલ. પી.-પ્રકારની સમસ્યા તરીકે રજૂ કરી શકાય છે. આ રચનામાં, સમૂહ એ બંને પોલીટોપ્સમાં તમામ શિરોબિંદુઓનો સમૂહ છે, અને કાર્ય મૂલ્ય એ બે પોલીટોપ્સમાં શિરોબિંદુઓના બે સબસેટ્સના બહિર્મુખ પત્થરો વચ્ચેના સૌથી નાના અંતરની નકારાત્મકતા છે. સમસ્યાનું સંયુક્ત પરિમાણ એ છે કે જો બે પોલીટોપ વિચ્છેદિત હોય, અથવા જો તેમની પાસે બિન-ખાલી આંતરછેદ હોય. ચાલો} ક્વાસીકોનવેક્સ કાર્યોનો સમૂહ બનીએ. પછી પોઇન્ટવાઇઝ મેક્સિમમ પોતે જ ક્વાસીકોનવેક્સ છે, અને તેનું લઘુતમ મૂલ્ય શોધવાની સમસ્યા એ એલ. પી.-પ્રકારની સમસ્યા છે. તેમાં મહત્તમ સંયુક્ત પરિમાણ હોય છે, જ્યાં કાર્યોના ક્ષેત્રનું પરિમાણ હોય છે, પરંતુ પૂરતા પ્રમાણમાં સરળ કાર્યો માટે સંયુક્ત પરિમાણ સૌથી ઓછું હોય છે. અન્ય ઘણી એલ. પી.-પ્રકારની સમસ્યાઓ પણ આ રીતે ક્વાસીકોનવેક્સ કાર્યોનો ઉપયોગ કરીને વ્યક્ત કરી શકાય છે; દાખલા તરીકે, સૌથી નાની ઘેરાયેલી વર્તુળની સમસ્યા એ છે કે જ્યાં દરેક કાર્ય આપેલ બિંદુઓમાંથી એકથી યુક્લિડિયન અંતરને માપે છે. એલ. પી.-પ્રકારની સમસ્યાઓનો ઉપયોગ એલ્ગોરિધમિક રમત સિદ્ધાંતમાં ચોક્કસ રમતોના શ્રેષ્ઠ પરિણામો નક્કી કરવા, મર્યાદિત તત્વ પદ્ધતિ મેશમાં શિરોબિંદુ પ્લેસમેન્ટમાં સુધારો કરવા, સુવિધાના સ્થાનની સમસ્યાઓનું સમાધાન કરવા, ચોક્કસ ઘાતાંકીય-સમય શોધ અલ્ગોરિધમ્સની સમય જટિલતાનું વિશ્લેષણ કરવા અને તેમની દ્વિ-પરિમાણીય છબીઓમાંથી વસ્તુઓની ત્રિ-પરિમાણીય સ્થિતિઓનું પુનઃનિર્માણ કરવા માટે પણ કરવામાં આવે છે. અલ્ગોરિધમ્સ સીડેલ એ ઓછા-પરિમાણીય રેખીય પ્રોગ્રામિંગ માટે એક અલ્ગોરિધમ આપ્યું હતું જે એલ. પી.-પ્રકારના સમસ્યા માળખામાં અનુકૂળ થઈ શકે છે. સીડેલનું અલ્ગોરિધમ સમૂહને ઇનપુટ તરીકે લે છે અને શ્રેષ્ઠ આધાર સાથે સંબંધિત હોવાનું જાણીતાં તત્વોનો એક અલગ સમૂહ (શરૂઆતમાં ખાલી) લે છે. તે પછી બાકીના તત્વોને એક પછી એક અવ્યવસ્થિત ક્રમમાં ધ્યાનમાં લે છે, દરેક માટે ઉલ્લંઘન પરીક્ષણો કરે છે અને પરિણામના આધારે, જાણીતા આધાર તત્વોના મોટા સમૂહ સાથે સમાન અલ્ગોરિધમનો પુનરાવર્તિત કૉલ કરે છે. તેને નીચેના સ્યુડોકોડ સાથે વ્યક્ત કરી શકાય છેઃ ફંક્શન સેઇડલ (S, f, X) એ R: = ખાલી સમૂહ B: = X માટે x માટે S ના રેન્ડમ ક્રમચયમાંઃ જો f (B) §f (B ≤ {x}): B: = સેઇડલ (R, f, X ≤ {x}) R: = R ≤ {x} વળતર B સંયુક્ત પરિમાણ સાથેની સમસ્યામાં, અલ્ગોરિધમનો ત્રીજો પુનરાવર્તન ઉલ્લંઘન પરીક્ષણ ત્યારે જ નિષ્ફળ જાય છે જ્યારે બાકીના આધાર ઘટકોમાંથી એક હોય, જે મહત્તમ સંભાવના સાથે થાય છે. આ ગણતરીના આધારે, તે દર્શાવી શકાય છે કે અલ્ગોરિધમ દ્વારા કરવામાં આવતા ઉલ્લંઘન પરીક્ષણોની એકંદર અપેક્ષિત સંખ્યા, રેખીય છે પરંતુ ઘાતાંકીય કરતાં વધુ ખરાબ છે. ક્લાર્કસન બે અલ્ગોરિધમ્સને વ્યાખ્યાયિત કરે છે, એક રિકર્સિવ અલ્ગોરિધમ અને એક ઇટરેટિવ અલ્ગોરિધમ, રેન્ડમ સેમ્પલિંગ તકનીકો પર આધારિત રેખીય પ્રોગ્રામિંગ માટે, અને બંનેનું સંયોજન સૂચવે છે જે રિકર્સિવ અલ્ગોરિધમમાંથી ઇટરેટિવ અલ્ગોરિધમ કહે છે. પુનરાવર્તિત અલ્ગોરિધમ વારંવાર રેન્ડમ નમૂનાઓ પસંદ કરે છે જેનું કદ લગભગ ઇનપુટ કદના વર્ગમૂળ જેટલું હોય છે, નમૂનાની સમસ્યાને પુનરાવર્તિત રીતે હલ કરે છે, અને પછી બાકીના ઘટકોનો સબસેટ શોધવા માટે ઉલ્લંઘન પરીક્ષણોનો ઉપયોગ કરે છે જેમાં ઓછામાં ઓછું એક આધાર તત્વ શામેલ હોવું જોઈએઃ કાર્ય પુનરાવર્તિત (S, f) એ X: = ખાલી સમૂહ પુનરાવર્તન R: = કદ d σnB સાથે S નો રેન્ડમ સબસેટઃ = R ≤ X માટે આધાર, પુનરાવર્તિત રીતે ગણતરી કરવામાં આવે છે V: = {x | f (B) ≤ f (B ≤ x)} X: = X ≤ V જ્યાં સુધી V ખાલી ન હોય ત્યાં સુધી દરેક પુનરાવર્તનમાં, તેનું અપેક્ષિત કદ છે, અને જ્યારે પણ બિન-ખાલી હોય ત્યારે તેમાં ઓછામાં ઓછું એક સમાવેશ થાય છે. તેથી, અલ્ગોરિધમ મોટાભાગના પુનરાવર્તનો કરે છે, જેમાંથી દરેક ઉલ્લંઘન પરીક્ષણો કરે છે અને કદની પેટા સમસ્યા માટે એક જ પુનરાવર્તિત કૉલ કરે છે. ક્લાર્કસનનું પુનરાવર્તિત અલ્ગોરિધમ દરેક તત્વને વજન સોંપે છે, શરૂઆતમાં તે બધા સમાન હોય છે. તે પછી રેન્ડમમાંથી તત્વોનો સમૂહ પસંદ કરે છે, અને સમૂહોની ગણતરી કરે છે અને અગાઉના અલ્ગોરિધમની જેમ. જો નું કુલ વજન મોટાભાગે નું કુલ વજન હોય (જેમ કે સતત સંભાવના સાથે થાય છે) તો અલ્ગોરિધમ દરેક તત્વના વજનને બમણો કરે છે, અને પહેલાની જેમ તે ખાલી થાય ત્યાં સુધી આ પ્રક્રિયાને પુનરાવર્તન કરે છે. દરેક પુનરાવર્તનમાં, શ્રેષ્ઠ આધારનું વજન કુલ વજન કરતાં વધુ દરે વધતું દર્શાવી શકાય છે, જેમાંથી તે અનુસરે છે કે અલ્ગોરિધમ પુનરાવર્તનની અંદર સમાપ્ત થવું જોઈએ. આપેલ સમસ્યાને ઉકેલવા માટે પુનરાવર્તિત અલ્ગોરિધમનો ઉપયોગ કરીને, તેના પુનરાવર્તિત કૉલ્સ માટે પુનરાવર્તિત અલ્ગોરિધમ પર સ્વિચ કરીને, અને પછી પુનરાવર્તિત અલ્ગોરિધમ દ્વારા કરવામાં આવેલા કૉલ્સ માટે ફરીથી સીડેલના અલ્ગોરિધમ પર સ્વિચ કરીને, ઉલ્લંઘન પરીક્ષણોનો ઉપયોગ કરીને આપેલ એલ. પી.-પ્રકારની સમસ્યાનું સમાધાન શક્ય છે. જ્યારે રેખીય પ્રોગ્રામ પર લાગુ કરવામાં આવે છે, ત્યારે આ અલ્ગોરિધમને ડ્યુઅલ સિમ્પ્લેક્સ પદ્ધતિ તરીકે અર્થઘટન કરી શકાય છે. ઉલ્લંઘન પરીક્ષણ અને બેસિસ કોમ્પ્યુટેશન પ્રિમિટિવ્સની બહાર અમુક વધારાના કોમ્પ્યુટેશનલ પ્રિમિટિવ્સ સાથે, આ પદ્ધતિને નિર્ધારક બનાવી શકાય છે. માટોસેક, શારિર અને વેલ્ઝલ એક એલ્ગોરિધમનું વર્ણન કરે છે જે રેખીય કાર્યક્રમોના વધારાના ગુણધર્મનો ઉપયોગ કરે છે જે હંમેશા અન્ય એલ. પી.-પ્રકારની સમસ્યાઓ દ્વારા રાખવામાં આવતા નથી, કે તમામ પાયા એકબીજાની સમાન મુખ્યતા ધરાવે છે. જો એલ. પી.-પ્રકારની સમસ્યામાં આ ગુણધર્મ ન હોય, તો તેને નવા ડમી ઘટકો ઉમેરીને અને કાર્યમાં ફેરફાર કરીને તેના જૂના મૂલ્ય અને સંખ્યાના ક્રમબદ્ધ જોડીને લેક્સિકોગ્રાફિક રીતે પરત કરવા માટે બનાવી શકાય છે. એક સમયે એસ વનના ઘટકો ઉમેરવાને બદલે, અથવા તત્વોના નમૂના શોધવાને બદલે, એક એલ્ગોરિધમનું વર્ણન કરો જે એક સમયે એક તત્વને દૂર કરે છે. દરેક તબક્કે તે એક આધાર જાળવે છે જે શરૂઆતમાં ડમી તત્વોનો સમૂહ હોઈ શકે છે. તેને નીચેના સ્યુડોકોડ સાથે વર્ણવી શકાય છેઃ ફંક્શન એમ. એસ. ડબલ્યુ. (એસ, એફ, સી) એ છે કે જો એસ = સી હોય તો રીટર્ન સી એ રેન્ડમ એલિમેન્ટ x પસંદ કરે છે જે એસ \સી. બી = એમ. એસ. ડબલ્યુ. (એસ \ક્સ, એફ, સી) જો એફ (બી) ષ્ણુત એફ (બી ષ્ણુત x) હોય તો બીઃ = બેસિસ (બી ષ્ણુત x) બીઃ = એમ. એસ. ડબલ્યુ. (એસ, એફ, બી) રીટર્ન બી. અલ્ગોરિધમના મોટાભાગના રિકર્સિવ કોલ્સમાં, ઉલ્લંઘન પરીક્ષણ સફળ થાય છે અને આઇ. એફ. સ્ટેટમેન્ટ છોડવામાં આવે છે. જો કે, ઓછી સંભાવના સાથે ઉલ્લંઘન પરીક્ષણ નિષ્ફળ જાય છે અને અલ્ગોરિધમ વધારાની આધાર ગણતરી કરે છે અને પછી વધારાના પુનરાવર્તિત કૉલ કરે છે. લેખકો દર્શાવે છે તેમ, અલ્ગોરિધમનો અપેક્ષિત સમય n માં રેખીય અને ના વર્ગમૂળમાં ઘાતાંકીય છે. આ પદ્ધતિને ક્લાર્કસનની પુનરાવર્તિત અને પુનરાવર્તિત પ્રક્રિયાઓ સાથે જોડીને, સમય અવલંબનના આ બે સ્વરૂપોને એકબીજાથી અલગ કરી શકાય છે, પરિણામે એક અલ્ગોરિધમ જે બાહ્ય પુનરાવર્તિત અલ્ગોરિધમમાં O (dn) ઉલ્લંઘન પરીક્ષણો કરે છે અને એક સંખ્યા જે ઘાતાંકીય હોય છે. ભિન્નતાઓ આઉટલાયર્સ સાથે ઓપ્ટિમાઇઝેશન એલ. પી.-પ્રકારની ઓપ્ટિમાઇઝેશન સમસ્યાઓની વિવિધતાને ધ્યાનમાં લે છે જેમાં સમૂહ અને ઉદ્દેશ્ય કાર્ય, એક સંખ્યા સાથે આપવામાં આવે છે; બાકીના સમૂહ પરના ઉદ્દેશ્ય કાર્યને શક્ય તેટલું નાનું બનાવવા માટે તેમાંથી તત્વોને દૂર કરવાનું કાર્ય છે. દાખલા તરીકે, જ્યારે સૌથી નાની વર્તુળ સમસ્યા પર લાગુ કરવામાં આવે છે, ત્યારે આ સૌથી નાનું વર્તુળ આપશે જેમાં આપેલ સમતલીય બિંદુઓના સમૂહ સિવાયના તમામનો સમાવેશ થાય છે. તેઓ દર્શાવે છે કે, તમામ બિન-વિકૃત એલ. પી.-પ્રકારની સમસ્યાઓ માટે (એટલે કે, જે સમસ્યાઓમાં તમામ પાયાના અલગ મૂલ્યો હોય છે) આ સમસ્યાનું સમાધાન સમયસર થઈ શકે છે, એલ. પી.-પ્રકારની સમસ્યાઓના ઉપગણ દ્વારા વ્યાખ્યાયિત સમૂહને હલ કરીને. કેટલીક ભૌમિતિક ઓપ્ટિમાઇઝેશન સમસ્યાઓને એલ. પી.-પ્રકારની સમસ્યાઓ તરીકે વ્યક્ત કરી શકાય છે જેમાં એલ. પી.-પ્રકારની રચનામાં તત્વોની સંખ્યા ઓપ્ટિમાઇઝેશન સમસ્યા માટે ઇનપુટ ડેટા મૂલ્યોની સંખ્યા કરતાં નોંધપાત્ર રીતે વધારે હોય છે. ઉદાહરણ તરીકે, સમતલમાં બિંદુઓના સંગ્રહને ધ્યાનમાં લો, દરેક સ્થિર વેગ સાથે આગળ વધી રહ્યા છે. કોઈપણ સમયે, આ પ્રણાલીનો વ્યાસ તેના બે બિંદુઓ વચ્ચેનું મહત્તમ અંતર છે. જે સમયે વ્યાસ ઘટાડવામાં આવે છે તે સમય શોધવાની સમસ્યાને સમયના કાર્ય તરીકે જોડી વચ્ચેના યુક્લિડિયન અંતરને માપવા માટે, બિંદુઓની દરેક જોડી માટે એક, ક્વાસીકોનવેક્સ કાર્યોના બિંદુ મુજબ મહત્તમને ઘટાડવા તરીકે ઘડી શકાય છે. આમ, તેને તત્વોના સમૂહ પર સંયુક્ત પરિમાણ બે ની એલ. પી.-પ્રકારની સમસ્યા તરીકે ઉકેલી શકાય છે, પરંતુ આ સમૂહ ઇનપુટ બિંદુઓની સંખ્યા કરતા નોંધપાત્ર રીતે મોટો છે. આ જેવી સ્પષ્ટ રીતે વ્યાખ્યાયિત એલ. પી.-પ્રકારની સમસ્યાઓને ઉકેલવા માટે એક અલ્ગોરિધમનું વર્ણન કરે છે જેમાં દરેક એલ. પી.-પ્રકારનું તત્વ કેટલાક અચળાંક માટે ઇનપુટ મૂલ્યોના-ટુપલ દ્વારા નક્કી કરવામાં આવે છે. તેમના અભિગમને લાગુ કરવા માટે, એક નિર્ણય અલ્ગોરિધમ અસ્તિત્વમાં હોવું જોઈએ જે આપેલ એલ. પી.-પ્રકાર આધાર અને ઇનપુટ મૂલ્યોના સમૂહ માટે નક્કી કરી શકે છે કે એલ. પી.-પ્રકાર સમસ્યા માટેનો આધાર શું છે. ચાનનું અલ્ગોરિધમ નીચેના પગલાંઓ કરે છેઃ જો ઇનપુટ મૂલ્યોની સંખ્યા અમુક થ્રેશોલ્ડ મૂલ્યથી ઓછી હોય, તો એલ. પી.-પ્રકારનાં તત્વોનો સમૂહ શોધો જે તે નક્કી કરે છે અને પરિણામી સ્પષ્ટ એલ. પી.-પ્રકારની સમસ્યાનું સમાધાન કરે છે. નહિંતર, ઇનપુટ મૂલ્યોને સમાન કદના ઉપગણ કરતાં મોટી યોગ્ય સંખ્યામાં વિભાજીત કરો. જો ગર્ભિત રીતે વ્યાખ્યાયિત એલ. પી.-પ્રકારની સમસ્યાનું નિરાકરણ લાવવા માટેનું ઉદ્દેશ્ય કાર્ય હોય, તો પછી એવા કાર્યને વ્યાખ્યાયિત કરો કે જે સંગ્રહના જોડાણ પરના મૂલ્ય સાથે ઉપગણોના સંગ્રહને મેપ કરે. પછી ઉપગણોનો સંગ્રહ અને ઉદ્દેશ્ય કાર્ય પોતે જ એલ. પી.-પ્રકારની સમસ્યાને વ્યાખ્યાયિત કરે છે, જે ઉકેલવાની ગર્ભિત સમસ્યાના સમાન પરિમાણની હોય છે. ક્લાર્કસનના અલ્ગોરિધમનો ઉપયોગ કરીને વ્યાખ્યાયિત (સ્પષ્ટ) એલ. પી.-પ્રકારની સમસ્યાનું સમાધાન કરો, જે ઉલ્લંઘન પરીક્ષણોની રેખીય સંખ્યા અને પાયાના મૂલ્યાંકનની બહુપત્નીકીય સંખ્યા કરે છે. આના માટે આધાર મૂલ્યાંકન ચાનના અલ્ગોરિધમ પર પુનરાવર્તિત કૉલ્સ દ્વારા કરી શકાય છે, અને ઉલ્લંઘન પરીક્ષણો નિર્ણય અલ્ગોરિધમ પર કૉલ્સ દ્વારા કરી શકાય છે. એવી ધારણા સાથે કે નિર્ણય અલ્ગોરિધમ થોડો સમય લે છે જે ઇનપુટ કદના કાર્ય તરીકે ઓછામાં ઓછું બહુપદી રીતે વધે છે, ચાન દર્શાવે છે કે સ્પષ્ટ એલ. પી. રચના પર સ્વિચ કરવા માટેનો થ્રેશોલ્ડ અને પાર્ટીશનમાં સબસેટ્સની સંખ્યા એવી રીતે પસંદ કરી શકાય છે કે ગર્ભિત એલ. પી.-પ્રકાર ઓપ્ટિમાઇઝેશન અલ્ગોરિધમ પણ સમયસર ચાલે છે. દાખલા તરીકે, ફરતા બિંદુઓના લઘુતમ વ્યાસ માટે, નિર્ણય અલ્ગોરિધમને માત્ર નિશ્ચિત સમયે બિંદુઓના સમૂહના વ્યાસની ગણતરી કરવાની જરૂર છે, એક સમસ્યા જે ફરતી કેલિપર્સ તકનીકનો ઉપયોગ કરીને સમયસર ઉકેલી શકાય છે. તેથી, જે સમયે વ્યાસ ઘટાડવામાં આવે છે તે શોધવા માટે ચાનના અલ્ગોરિધમનો પણ સમય લે છે. ચાન આ પદ્ધતિનો ઉપયોગ સમયની સાથે-પરિમાણીય યુક્લિડિયન અવકાશમાં બિંદુઓના આપેલ સંગ્રહમાં મહત્તમ ટુકી ઊંડાઈના બિંદુને શોધવા માટે કરે છે. બહિર્મુખ બહુકોણ પર સમાન વિતરણ માટે મહત્તમ ટુકી ઊંડાઈના બિંદુને શોધવા માટે સમાન તકનીકનો ઉપયોગ કરવામાં આવ્યો હતો. ઇતિહાસ અને સંબંધિત સમસ્યાઓ રેખીય પ્રોગ્રામિંગ માટે રેખીય સમય અલ્ગોરિધમ્સની શોધ અને નિરીક્ષણ કે સમાન અલ્ગોરિધમ્સનો ઉપયોગ ઘણા કિસ્સાઓમાં ભૌમિતિક ઓપ્ટિમાઇઝેશન સમસ્યાઓને ઉકેલવા માટે થઈ શકે છે જે રેખીય પ્રોગ્રામ્સ ન હતા, ઓછામાં ઓછા, જેમણે ત્રણ-ચલ રેખીય પ્રોગ્રામ્સ અને સૌથી નાના વર્તુળ સમસ્યા બંને માટે રેખીય અપેક્ષિત સમય અલ્ગોરિધમ આપ્યો હતો. જો કે, મેગિડોએ રેખીય પ્રોગ્રામિંગના સામાન્યીકરણને સંયોજનને બદલે ભૌમિતિક રીતે, સમૂહોની પ્રણાલીઓ પર અમૂર્ત સમસ્યાને બદલે બહિર્મુખ ઓપ્ટિમાઇઝેશન સમસ્યા તરીકે ઘડ્યું હતું. તેવી જ રીતે, અને ક્લાર્કસન (1988ના પરિષદ સંસ્કરણમાં) એ અવલોકન કર્યું હતું કે તેમની પદ્ધતિઓ બહિર્મુખ કાર્યક્રમો તેમજ રેખીય કાર્યક્રમો પર લાગુ કરી શકાય છે. દર્શાવ્યું હતું કે લઘુત્તમ સંલગ્ન લંબગોળ સમસ્યાને પણ નાની સંખ્યામાં બિન-રેખીય અવરોધો ઉમેરીને બહિર્મુખ ઓપ્ટિમાઇઝેશન સમસ્યા તરીકે ઘડી શકાય છે. ઓછા પરિમાણીય રેખીય પ્રોગ્રામિંગ અને સંબંધિત સમસ્યાઓ માટે સમયમર્યાદામાં સુધારો કરવા માટે રેન્ડમાઇઝેશનનો ઉપયોગ ક્લાર્કસન અને દ્વારા કરવામાં આવ્યો હતો. સ્થાન અને એકવિધતાના સ્વયંસિદ્ધ સિદ્ધાંતોને સંતોષતા કાર્યોની દ્રષ્ટિએ એલ. પી.-પ્રકારની સમસ્યાઓની વ્યાખ્યા અહીંથી છે, પરંતુ તે જ સમયમર્યાદામાં અન્ય લેખકોએ રેખીય કાર્યક્રમોના વૈકલ્પિક સંયુક્ત સામાન્યીકરણની રચના કરી હતી. દાખલા તરીકે, દ્વારા વિકસિત માળખામાં, કાર્યને ઉપગણ પર કુલ ક્રમ દ્વારા બદલવામાં આવે છે. કુલ ક્રમ બનાવવા માટે એલ. પી.-પ્રકારની સમસ્યામાં સંબંધોને તોડવા શક્ય છે, પરંતુ માત્ર સંયુક્ત પરિમાણમાં વધારાના ભોગે. વધુમાં, એલ. પી.-પ્રકારની સમસ્યાઓની જેમ, ગાર્ટનર તત્વોના સબસેટ પર ગણતરીઓ કરવા માટે ચોક્કસ આદિકાળને વ્યાખ્યાયિત કરે છે; જો કે, તેમના ઔપચારિકરણમાં સંયોજન પરિમાણનું એનાલોગ નથી. રેખીય કાર્યક્રમો અને રેખીય પૂરકતા સમસ્યાઓ બંનેનું અન્ય અમૂર્ત સામાન્યીકરણ, જે અન્ય કેટલાક લેખકો દ્વારા ઘડવામાં આવ્યું હતું અને પછીથી તેનો અભ્યાસ કરવામાં આવ્યો હતો, તે હાયપરક્યુબની ધારની દિશાઓ સાથે સંબંધિત છે કે હાયપરક્યુબના દરેક ચહેરા (ચહેરા તરીકે સમગ્ર હાયપરક્યુબ સહિત) એક અનન્ય સિંક ધરાવે છે, એક શિરોબિંદુ જેમાં કોઈ આઉટગોઇંગ ધાર નથી. આ પ્રકારની દિશા એલ. પી.-પ્રકારની સમસ્યામાંથી હાયપરક્યુબના શિરોબિંદુઓ સાથે એસના ઉપગણને એવી રીતે અનુરૂપ કરીને રચાઈ શકે છે કે જો અને માત્ર જો અનુરૂપ શિરોબિંદુઓ અડીને હોય તો જ બે ઉપગણ એક તત્વ દ્વારા અલગ પડે છે, અને પડોશી સમૂહો વચ્ચેની ધારને જો અને અન્યથા તરફ નિર્દેશિત કરીને. પરિણામી અભિગમમાં વધારાનો ગુણધર્મ છે કે તે નિર્દેશિત એસાયક્લિક ગ્રાફ બનાવે છે, જેમાંથી તે બતાવી શકાય છે કે રેન્ડમાઇઝ્ડ અલ્ગોરિધમ સમગ્ર હાયપરક્યુબ (એલ. પી.-પ્રકારની સમસ્યાનો શ્રેષ્ઠ આધાર) ના અનન્ય સિંકને સંખ્યાબંધ પગલાંઓમાં શોધી શકે છે. ઉલ્લંઘનકર્તા જગ્યાઓનું તાજેતરમાં વિકસિત માળખું એલ. પી.-પ્રકારની સમસ્યાઓને સામાન્ય બનાવે છે, તે અર્થમાં કે દરેક એલ. પી.-પ્રકારની સમસ્યાને ઉલ્લંઘનકર્તા જગ્યા દ્વારા મોડેલ કરી શકાય છે પરંતુ જરૂરી નથી કે તેનાથી ઊલટું હોય. ઉલ્લંઘનકર્તા જગ્યાઓને એલ. પી.-પ્રકારની સમસ્યાઓની જેમ જ વ્યાખ્યાયિત કરવામાં આવે છે, એક કાર્ય દ્વારા જે ઉદ્દેશ્ય કાર્ય મૂલ્યોને સુયોજિત કરે છે, પરંતુ તેના મૂલ્યો ક્રમબદ્ધ નથી. ઓર્ડરિંગનો અભાવ હોવા છતાં, દરેક સમૂહમાં પાયાનો સારી રીતે વ્યાખ્યાયિત સમૂહ હોય છે (સમગ્ર સમૂહની સમાન કિંમત સાથેનો ન્યૂનતમ સમૂહ) જે એલ. પી.-પ્રકારની સમસ્યાઓ માટે ક્લાર્કસનના અલ્ગોરિધમ્સની વિવિધતાઓ દ્વારા શોધી શકાય છે. ખરેખર, ઉલ્લંઘનકર્તા જગ્યાઓ ક્લાર્ક્સનના અલ્ગોરિધમ્સ દ્વારા ઉકેલી શકાય તેવી સિસ્ટમોની ચોક્કસ લાક્ષણિકતા દર્શાવવામાં આવી છે. નોંધો સંદર્ભો. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . કોમ્પ્યુટેશનલ ભૂમિતિ રેખીય પ્રોગ્રામિંગ