Quadratic assignment problem
ક્વોડ્રેટિક અસાઇનમેન્ટ પ્રોબ્લેમ (ક્યુએપી) એ ગણિતમાં ઓપ્ટિમાઇઝેશન અથવા ઓપરેશન્સ રિસર્ચની શાખામાં મૂળભૂત સંયુક્ત ઓપ્ટિમાઇઝેશન સમસ્યાઓમાંની એક છે, જે કૂપમેન્સ અને બેકમેન દ્વારા સૌપ્રથમ રજૂ કરવામાં આવેલી સુવિધાઓના સ્થાનની સમસ્યાઓની શ્રેણીમાંથી છે. આ સમસ્યા નીચેની વાસ્તવિક જીવનની સમસ્યાનું મોડેલ બનાવે છેઃ તેમાં n સુવિધાઓનો સમૂહ અને n સ્થાનોનો સમૂહ છે. સ્થાનોની દરેક જોડી માટે, અંતર નિર્દિષ્ટ કરવામાં આવે છે અને સુવિધાઓની દરેક જોડી માટે વજન અથવા પ્રવાહ નિર્દિષ્ટ કરવામાં આવે છે (દા. ત., બે સુવિધાઓ વચ્ચે પરિવહન કરાયેલ પુરવઠાની માત્રા). સમસ્યા એ છે કે સંબંધિત પ્રવાહ દ્વારા ગુણાકાર કરેલા અંતરના સરવાળાને ઘટાડવાના ધ્યેય સાથે વિવિધ સ્થળોએ તમામ સુવિધાઓ સોંપવામાં આવે. સાહજિક રીતે, ખર્ચ કાર્ય એકબીજા વચ્ચે ઊંચા પ્રવાહ સાથેની સુવિધાઓને એકબીજાની નજીક મૂકવા માટે પ્રોત્સાહિત કરે છે. સમસ્યાનું નિવેદન સોંપણીની સમસ્યા જેવું જ છે, સિવાય કે ખર્ચનું કાર્ય દ્વિઘાત અસમાનતાના સંદર્ભમાં વ્યક્ત કરવામાં આવે છે, તેથી તેનું નામ છે. ઔપચારિક ગાણિતિક વ્યાખ્યા દ્વિઘાત સોંપણી સમસ્યાની ઔપચારિક વ્યાખ્યા નીચે મુજબ છેઃ સમાન કદના બે સમૂહો, P ("સુવિધાઓ") અને L ("સ્થાનો"), એકસાથે વજન વિધેય w: P × P → R અને અંતર વિધેય d: L × L → R સાથે. સામાન્ય રીતે વજન અને અંતર કાર્યોને ચોરસ વાસ્તવિક મૂલ્યના મેટ્રિક્સ તરીકે જોવામાં આવે છે, જેથી કિંમત કાર્યને આ રીતે લખવામાં આવે છેઃ મેટ્રિક્સ નોટેશનમાંઃ જ્યાં ક્રમચય મેટ્રિક્સનો સમૂહ છે, તે વજન મેટ્રિક્સ છે અને તે અંતર મેટ્રિક્સ છે. કોમ્પ્યુટેશનલ જટિલતા સમસ્યા એન. પી.-હાર્ડ છે, તેથી બહુપદી સમયમાં આ સમસ્યાને હલ કરવા માટે કોઈ જાણીતું અલ્ગોરિધમ નથી, અને નાના ઉદાહરણોમાં પણ લાંબા ગણતરી સમયની જરૂર પડી શકે છે. તે પણ સાબિત થયું હતું કે સમસ્યામાં કોઈ પણ (અચળ) પરિબળ માટે બહુપદી સમયમાં ચાલી રહેલું અંદાજિત અલ્ગોરિધમ નથી, સિવાય કે P = NP. ટ્રાવેલિંગ સેલ્સમેન પ્રોબ્લેમ (ટી. એસ. પી.) ને ક્યુ. એ. પી. ના વિશેષ કેસ તરીકે જોવામાં આવી શકે છે જો કોઈ એવું ધારે કે પ્રવાહ તમામ સુવિધાઓને માત્ર એક જ રિંગ સાથે જોડે છે, તો તમામ પ્રવાહોનું સમાન બિન-શૂન્ય (સ્થિર) મૂલ્ય હોય છે અને તમામ અંતર ટી. એસ. પી. ઉદાહરણના સંબંધિત અંતર સમાન હોય છે. પ્રમાણભૂત સંયુક્ત ઓપ્ટિમાઇઝેશન સમસ્યાઓની અન્ય ઘણી સમસ્યાઓ આ સ્વરૂપમાં લખી શકાય છે. મૂળ પ્લાન્ટ સ્થાન રચના ઉપરાંત, ક્યુએપી એ પ્રિન્ટેડ સર્કિટ બોર્ડ પર અથવા માઇક્રોચિપ પર એકબીજા સાથે જોડાયેલા ઇલેક્ટ્રોનિક ઘટકોને મૂકવાની સમસ્યા માટેનું એક ગાણિતિક મોડેલ છે, જે ઇલેક્ટ્રોનિક્સ ઉદ્યોગમાં કમ્પ્યુટર સહાયિત ડિઝાઇનના સ્થળ અને માર્ગ તબક્કાનો ભાગ છે. ચતુર્ભુજ અવરોધ સોંપણી સમસ્યા સંદર્ભો નોંધો સ્ત્રોતો A2.5: ND43, pg.218 પણ જુઓ. બાહ્ય કડીઓ https://www.opt.math.tugraz.at/qaplib QAPLIB-એક ચતુર્ભુજ સોંપણી સમસ્યા પુસ્તકાલય http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal MAOS-QAP-જાવા આધારિત ચતુર્ભુજ સોંપણી સમસ્યા ઉકેલનાર https://CRAN.R-project.org/package=qap-R પેકેજ qAP: ચતુર્ભુજ સોંપણી સમસ્યા માટે સંશોધનો https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ-વિન્ડોઝ માટે મેટાહેરિસ્ટિક QAP ઉકેલનાર 10/11 NP-હાર્ડ સમસ્યાઓ સંયોજન ઑપ્ટિમાઇઝેશન