Optimal kidney exchange
ઓપ્ટિમલ કિડની એક્સચેન્જ (OKE) એ કિડની જોડી દાન માટેના કાર્યક્રમો (જેને કિડની એક્સચેન્જ પ્રોગ્રામ્સ પણ કહેવાય છે) દ્વારા સામનો કરવામાં આવતી ઓપ્ટિમાઇઝેશન સમસ્યા છે. આવા કાર્યક્રમોમાં દર્દી-દાતા જોડીનો મોટો ડેટાબેઝ હોય છે, જ્યાં દાતા દર્દીને મદદ કરવા માટે કિડની દાન કરવા તૈયાર હોય છે, પરંતુ તબીબી અસંગતતાને કારણે આમ કરી શકતા નથી. કેન્દ્રો આવી જોડી વચ્ચે વિનિમય ગોઠવવાનો પ્રયાસ કરે છે. ઉદાહરણ તરીકે, જોડી A માં દાતા જોડી B માં દર્દીને દાન કરે છે, જોડી B માં દાતા જોડી C માં દર્દીને દાન કરે છે, અને જોડી C માં દાતા જોડી A માં દર્દીને દાન કરે છે. OKE સમસ્યાનો ઉદ્દેશ આવા વિનિમયની શ્રેષ્ઠ વ્યવસ્થા શોધવાનો છે. "શ્રેષ્ઠ" નો સામાન્ય રીતે અર્થ થાય છે કે પ્રત્યારોપણની સંખ્યા શક્ય તેટલી મોટી છે, પરંતુ અન્ય ઉદ્દેશો પણ હોઈ શકે છે. આ ઓપ્ટિમાઇઝેશન સમસ્યામાં એક નિર્ણાયક અવરોધ એ છે કે દાતા માત્ર ત્યારે જ કિડની આપે છે જ્યારે તેના દર્દીને સુસંગત કિડની મળે, જેથી કોઈ પણ જોડી ભાગ લેવાથી કિડની ગુમાવશે નહીં. આ જરૂરિયાતને કેટલીકવાર વ્યક્તિગત તર્કસંગતતા કહેવામાં આવે છે. OKE સમસ્યામાં ઘણા પ્રકારો છે, જે દરેક વિનિમયના માન્ય કદ, ઉદ્દેશ્ય કાર્ય અને અન્ય પરિબળોમાં અલગ પડે છે. વ્યાખ્યાઓ ઇનપુટ OKE ના ઉદાહરણને સામાન્ય રીતે નિર્દેશિત આલેખ તરીકે વર્ણવવામાં આવે છે. દરેક નોડ દર્દી-દાતા જોડીનું પ્રતિનિધિત્વ કરે છે. જોડી A થી જોડી B સુધી નિર્દેશિત ચાપનો અર્થ એ છે કે જોડી A માં દાતા જોડી B માં દર્દી સાથે તબીબી રીતે સુસંગત છે (સુસંગતતા દાતા અને દર્દીના લોહીના પ્રકારો, તેમજ તેમના લોહીમાં ચોક્કસ એન્ટિજેન્સ જેવા અન્ય પરિબળોના આધારે નક્કી કરવામાં આવે છે). સુસંગતતા આલેખમાં નિર્દેશિત ચક્ર સંભવિત વિનિમયને રજૂ કરે છે. કદ 2 નું નિર્દેશિત ચક્ર (દા. ત. એ-> બી-> એ) સંભવિત જોડી મુજબના વિનિમયને રજૂ કરે છે-જોડીની જોડી વચ્ચેનું વિનિમય. ઓ. કે. ઈ. નો વધુ સામાન્ય પ્રકાર બીજા પ્રકારનાં ગાંઠોને પણ ધ્યાનમાં લે છે, જે પરોપકારી દાતાઓનું પ્રતિનિધિત્વ કરે છે-દાતાઓ કે જેઓ દર્દી સાથે જોડાયેલા નથી, અને કોઈપણ સુસંગત દર્દીને કિડની દાન કરવા તૈયાર છે. અલ્ટ્રુસ્ટિક ડોનર નોડ્સમાં માત્ર આઉટગોઇંગ આર્ક્સ હોય છે. પરોપકારી દાતાઓ સાથે, માત્ર ચક્રો સાથે જ નહીં પણ સાંકળો સાથે પણ વિનિમયની વ્યવસ્થા કરવી શક્ય છે, જે પરોપકારી દાતાથી શરૂ થાય છે. આલેખમાં ચાપમાં વજન હોઈ શકે છે, જે પ્રતિનિધિત્વ કરે છે, દા. ત. સામેલ પ્રત્યારોપણની સફળતાની સંભાવના. તેમની પ્રાથમિકતાઓ પણ નિર્ધારિત હોઈ શકે છે, દા. ત. તબીબી તાકીદે અથવા દર્દી પ્રત્યારોપણની કતારમાં રાહ જુએ ત્યાં સુધીમાં. આઉટપુટ OKE નું આઉટપુટ એ જોડી મુજબ-અલગ નિર્દેશિત ચક્રોનો સમૂહ છે (અને સંભવતઃ નિર્દેશિત સાંકળો, જો પરોપકારી દાતાઓ ઉપલબ્ધ હોય તો). ઓ. કે. ઈ. નો સૌથી સરળ ઉદ્દેશ કિડની મેળવનારા દર્દીઓની સંખ્યા વધારવાનો છે. અન્ય સામાન્ય ઉદ્દેશો છેઃ કિડની વિનિમયના ભારિત સરવાળાને મહત્તમ બનાવવોઃ આલેખમાં દરેક ધારનું વજન હોય છે, અને ધ્યેય એક વિનિમય શોધવાનો હોય છે જે વિનિમયમાં ઉપયોગમાં લેવાતી તમામ ધાર પર વજનનો સરવાળો મહત્તમ કરે. ટ્રાન્સપ્લાન્ટ ઉમેદવારોની અપેક્ષિત આયુષ્ય અથવા તેમની ગુણવત્તા-સમાયોજિત અપેક્ષિત આયુષ્યને મહત્તમ બનાવવું. અનિયંત્રિત ચક્રની લંબાઈ શરૂઆતમાં, વિનિમય ચક્રની લંબાઈ પર કોઈ બંધન વિના સમસ્યાનો અભ્યાસ કરવામાં આવ્યો હતો. રોથ, સોનમેઝ અને અનવરે પેરેટો-શ્રેષ્ઠ અને પ્રોત્સાહન-સુસંગત રીતે વિનિમય ચક્ર શોધવા માટે ટોચની વેપાર ચક્ર વ્યવસ્થાના વિસ્તરણના આધારે એક પદ્ધતિ રજૂ કરી હતી. અબ્રાહમ, બ્લમ અને સેન્ડહોલ્મ દર્શાવે છે કે, અમર્યાદિત ચક્ર લંબાઈ સાથે, બહુપદી સમયમાં મહત્તમ-કાર્ડિનાલિટી અને મહત્તમ-વજનનું વિનિમય મળી શકે છે. ઉદાહરણ તરીકે, મૂળ નિર્દેશિત આલેખ G આપવામાં આવેલ મહત્તમ-કાર્ડિનાલિટી વિનિમય શોધવા માટે, એક દિશાહીન દ્વિપક્ષી આલેખ H (X + Y, E) બનાવો જેમાંઃ G માં દરેક જોડી j પાસે બે ગાંઠો છેઃ xj (દાતાનું પ્રતિનિધિત્વ) અને yj (દર્દીનું પ્રતિનિધિત્વ). તેઓ વજન 1 ની ધાર દ્વારા જોડાયેલા છે. G માં દરેક ધાર i-> j માટે, H માં એક ધાર xi-- yj વજન 1 + 1/n ઉમેરો. એચમાં મહત્તમ-વજન મેળ ખાય છે તે શોધો. જીમાં દરેક મહત્તમ-કાર્ડિનાલિટી વિનિમય એચમાં મહત્તમ-વજન મેળ ખાય છે. નોંધ કરો કે વજન બાંયધરી આપે છે કે એચમાં દરેક મહત્તમ-વજન મેળ ખાય છે તે સંપૂર્ણ છે, જેથી દરેક દર્દી સુસંગત દાતા સાથે અથવા તેના પોતાના દાતા સાથે મેળ ખાય છે. તેથી કોઈ પણ દાતા જ્યાં સુધી તેના દર્દીને કિડની ન મળે ત્યાં સુધી કિડની આપતો નથી, જે વ્યક્તિગત તર્કસંગતતાની જરૂરિયાતને સંતોષે છે. આ અલ્ગોરિધમનો મહત્તમ વજનના વિનિમય સુધી વિસ્તાર કરવો અને પરોપકારી દાતાઓનો સમાવેશ કરવો સરળ છે. જોડી મુજબની કિડનીની અદલાબદલી 2004માં ન્યૂ ઇંગ્લેન્ડમાં કિડની વિનિમય કાર્યક્રમના અમલીકરણ તરફની ચર્ચામાં જાણવા મળ્યું હતું કે, લોજિસ્ટિક રીતે, માત્ર જોડી મુજબની અદલાબદલી શક્ય છે. આનું કારણ એ છે કે વિનિમયમાં તમામ કામગીરીઓ એક સાથે થવી જોઈએ. આ જરૂરિયાતનો ઉદ્દેશ વ્યક્તિગત તર્કસંગતતાના અવરોધને સુનિશ્ચિત કરવાનો છે-દાતા તેના દર્દીને કિડની મળ્યા પછી દાન કરવાનો ઇનકાર કરે છે તે જોખમને ટાળવા માટે. k કદના વિનિમય ચક્ર માટે 2k એક સાથે કામગીરીની જરૂર પડે છે. તે સમયે, 4 થી વધુ એક સાથે કામગીરીની વ્યવસ્થા કરવી વ્યવહારુ ન હતી, તેથી ચક્રોનું કદ 2 સુધી મર્યાદિત હતું. આ સેટિંગમાં, નિર્દેશિત સુસંગતતા આલેખને દિશાહીન આલેખમાં ઘટાડવાનું શક્ય છે, જ્યાં જોડી A અને B જો અને માત્ર ત્યારે જ જોડાયેલા હોય જો A-> B અને B-> A હોય. મહત્તમ-કાર્ડિનાલિટી જોડી મુજબનું વિનિમય શોધવું એ તે દિશાહીન આલેખમાં મહત્તમ કાર્ડિનાલિટી મેળ શોધવા સમાન છે. વધુમાં, જ્યારે માત્ર જોડી મુજબના વિનિમયને મંજૂરી આપવામાં આવે છે, ત્યારે મેળ ખાતું પેરેટો-કાર્યક્ષમ હોય છે જો અને માત્ર ત્યારે જ જો તેમાં મહત્તમ કાર્ડિનાલિટી હોય. તેથી, આવા વિનિમય બહુપદી સમયમાં મળી શકે છે. રોથ, સોનમેઝ અને અનવર સરળ મહત્તમ-કાર્ડિનાલિટી વિનિમયના બે વિસ્તરણોનો અભ્યાસ કરે છેઃ દર્દીઓ અથવા પ્રત્યારોપણ પર અગ્રતાના ક્રમને જોતાં, બહુપદી સમયમાં અગ્રતા મેળ ખાતી શોધવાનું શક્ય છે-એક મેળ જે તમામ મહત્તમ-કાર્ડિનાલિટી મેળમાં, ઉચ્ચ-અગ્રતાના દર્દીઓની સંખ્યાને મહત્તમ કરે છે. વધુમાં, આ અલ્ગોરિધમ્સને એ અર્થમાં પ્રોત્સાહન-સુસંગત બનાવી શકાય છે કે દરેક દર્દી સિસ્ટમમાં શક્ય તેટલા દાતાઓને લાવીને અને શક્ય તેટલી કિડની સ્વીકારવા માટે સંમત થઈને તેની મેળ ખાવાની તકને મહત્તમ કરે છે. પુરાવાઓ આલેખ સિદ્ધાંતમાંથી વિભાવનાઓનો ઉપયોગ કરે છે, જેમ કે ગેલાઈ-એડમંડ્સ વિઘટન. સ્ટોકેસ્ટિક એક્સચેન્જ શોધવું શક્ય છે, જ્યાં તમામ મહત્તમ-કાર્ડિનાલિટી મેચિંગમાંથી રેન્ડમ રીતે મેચિંગ પસંદ કરવામાં આવે છે. સમતાવાદી પદ્ધતિનો ઉદ્દેશ દર્દીને કિડની મળવાની સૌથી ઓછી સંભાવના વધારવાનો છે. સમાનતાવાદી મિકેનિઝમ એ જ અર્થમાં પ્રોત્સાહન-સુસંગત છે જે અગ્રતા મિકેનિઝમ છે. લંબાઈ k ના ચક્ર પછીના વર્ષોમાં, લોજિસ્ટિક સુધારાઓએ એક સાથે મોટી સંખ્યામાં કામગીરીઓ ચલાવવાની મંજૂરી આપી. તદનુસાર, ત્રણ અથવા વધુ જોડીનો સમાવેશ કરતા વિનિમય ચક્રને શક્ય બનાવવામાં આવ્યા હતા. મહત્તમ-કાર્ડિનાલિટી વિનિમય શોધવાને ગ્રાફ સૈદ્ધાંતિક દ્રષ્ટિએ, મહત્તમ ચક્ર પેકિંગ કહેવામાં આવે છે. કોઈપણ નિશ્ચિત k ≤ 3 માટે મહત્તમ k લંબાઈના ચક્ર સાથે મહત્તમ ચક્ર પેકિંગ એ NP-હાર્ડ કોમ્પ્યુટેશનલ સમસ્યા છે (આ હાયપરગ્રાફમાં 3-પરિમાણીય મેળની સમસ્યામાંથી ઘટાડો કરીને સાબિત કરી શકાય છે). અબ્રાહમ, બ્લમ અને સેન્ડહોલ્મ મહત્તમ ચક્ર પેકિંગ માટે બે તકનીકો રજૂ કરે છેઃ સ્તંભ નિર્માણ અને અવરોધ નિર્માણ. તેઓ અહેવાલ આપે છે કે કોલમ જનરેશન સ્કેલ વધુ સારી છે. તેમનું અલ્ગોરિધમ જોડીદાર કિડની દાન માટે જોડાણમાં લાગુ કરવામાં આવ્યું છે. બીરો, મેનલોવ અને રિઝી ધાર પર વજન હોય ત્યારે પણ આ સમસ્યાનું સમાધાન કરવા માટે બે અભિગમો સૂચવે છે (આ કિસ્સામાં તેને મહત્તમ-વજન ચક્ર પેકિંગ કહેવામાં આવે છે): મહત્તમ-વજન સ્વતંત્ર સમૂહ માટે જાણીતા અંદાજ અલ્ગોરિધમ્સ પર આધારિત એક અંદાજ અલ્ગોરિધમ; એક ચોક્કસ અલ્ગોરિધમ, ચક્રના હાયપરગ્રાફને ગ્રાફમાં રૂપાંતરિત કરવાની તમામ રીતોને વ્યવસ્થિત રીતે તપાસે છે. અલ્ગોરિધમ સમયસર ચાલે છે, જ્યાં s એ દરેક 3-ચક્રમાંથી એક ચાપ ધરાવતા સમૂહનું કદ છે. લંબાઈ k ના ચક્રો અને અમર્યાદિત લંબાઈની સાંકળો પરોપકારી દાતાઓનો ઉપયોગ વિનિમયની સાંકળ શરૂ કરવા માટે કરી શકાય છે, જે એક ચક્ર નથી. આવી સાંકળમાં, શસ્ત્રક્રિયાઓ એક સાથે કરવાની જરૂર નથીઃ દરેક દર્દીને ખાતરી આપવી શક્ય છે કે તેના દાતા કિડની આપે તે પહેલાં તેને કિડની મળે છે. જો દાતા ખામી ધરાવે છે, તો તે સાંકળ તોડી નાખે છે, પરંતુ તે એવા દર્દીઓને નુકસાન પહોંચાડતો નથી કે જેમના દાતાએ પહેલેથી જ કિડની આપી દીધી હોય, તેથી તે વ્યક્તિગત સમજદારીને તોડતો નથી. એન્ડરસન, એશલાગી, ગામાર્નિક અને રોથ મહત્તમ k અને અમર્યાદિત લંબાઈની સાંકળોના ચક્રમાં મહત્તમ-કાર્ડિનાલિટી પેકિંગ શોધવા માટે બે અલ્ગોરિધમ્સ રજૂ કરે છેઃ એક પૂર્ણાંક રેખીય પ્રોગ્રામિંગ અને અવરોધ પેઢી પર આધારિત છે; અન્ય મુસાફરી સેલ્સમેન સમસ્યાના ઉકેલ પર આધારિત છે. અનિશ્ચિત પ્રત્યારોપણ OKE માં પ્રારંભિક સૈદ્ધાંતિક કાર્યોએ ધાર્યું હતું કે, એકવાર વિનિમયનો સમૂહ નક્કી થઈ જાય, તે બધાને અમલમાં મૂકવામાં આવશે. વ્યવહારમાં, જોકે, પ્રત્યારોપણ રદ થઈ શકે છે. ઉદાહરણ તરીકે, પ્રત્યારોપણ પહેલાં કરવામાં આવેલી તબીબી તપાસ દર્શાવે છે કે દાતા દર્દી સાથે અસંગત છે, તેમ છતાં ડેટાબેઝમાં તેઓ સુસંગત તરીકે નોંધાયેલા છે. તેથી, નવા કાર્યોનો ઉદ્દેશ પ્રત્યારોપણની અપેક્ષિત સંખ્યાને મહત્તમ કરવાનો છે. ઉદાહરણ તરીકે, એલ્વેલોસ, ક્લિમેંટોવા અને વિયાના આ સમસ્યા માટે શાખા અને કિંમતનું અલ્ગોરિધમ રજૂ કરે છે. વધુ સંદર્ભો કિડની વિનિમય માટે પૂર્ણાંક-પ્રોગ્રામિંગ મોડેલ્સ. સંદર્ભો ઓપ્ટિમાઇઝેશન અલ્ગોરિધમ્સ અને પદ્ધતિઓ અંગ દાન