Optimal kidney exchange
অপ্টিম্যাল কিডনি এক্সচেঞ্জ (ও. কে. ই) হল একটি অপ্টিমাইজেশন সমস্যা যা কিডনি জোড়া দানের জন্য প্রোগ্রামগুলির সম্মুখীন হয় (যাকে কিডনি এক্সচেঞ্জ প্রোগ্রামও বলা হয়)। এই ধরনের প্রোগ্রামগুলিতে রোগী-দাতা জুটির বিশাল ডাটাবেস রয়েছে, যেখানে দাতা রোগীকে সাহায্য করার জন্য একটি কিডনি দান করতে ইচ্ছুক, কিন্তু চিকিৎসা সংক্রান্ত অসামঞ্জস্যতার কারণে তা করতে পারে না। কেন্দ্রগুলি এই ধরনের জোড়াগুলির মধ্যে বিনিময়ের ব্যবস্থা করার চেষ্টা করে। উদাহরণস্বরূপ, জোড়া এ-তে দাতা রোগীকে জোড়া বি-তে দান করেন, জোড়া বি-তে দাতা রোগীকে জোড়া সি-তে দান করেন এবং জোড়া সি-তে দাতা রোগীকে জোড়া এ-তে দান করেন। ও. কে. ই সমস্যার উদ্দেশ্য হল এই ধরনের বিনিময়ের একটি সর্বোত্তম ব্যবস্থা খুঁজে বের করা। "সর্বোত্তম" বলতে সাধারণত বোঝায় যে প্রতিস্থাপনের সংখ্যা যতটা সম্ভব বেশি, তবে অন্যান্য উদ্দেশ্যও থাকতে পারে। এই অপ্টিমাইজেশান সমস্যার একটি গুরুত্বপূর্ণ বাধা হ 'ল একজন দাতা কেবল তখনই একটি কিডনি দেন যখন তার রোগী একটি সামঞ্জস্যপূর্ণ কিডনি পান, যাতে কোনও জুটি অংশগ্রহণের ফলে একটি কিডনি হারাতে না পারে। এই প্রয়োজনীয়তাকে কখনও কখনও ব্যক্তিগত যৌক্তিকতা বলা হয়। ও. কে. ই সমস্যার অনেকগুলি রূপ রয়েছে, যা প্রতিটি বিনিময়ের অনুমোদিত আকার, উদ্দেশ্যমূলক কার্যকারিতা এবং অন্যান্য কারণগুলির মধ্যে পৃথক হয়। সংজ্ঞা ইনপুট ও. কে. ই-এর একটি উদাহরণ সাধারণত একটি নির্দেশিত গ্রাফ হিসাবে বর্ণনা করা হয়। প্রতিটি নোড একটি রোগী-দাতা জুটির প্রতিনিধিত্ব করে। জোড়া এ থেকে জোড়া বি-তে একটি নির্দেশিত চাপের অর্থ হল জোড়া এ-তে দাতা জোড়া বি-তে রোগীর সাথে চিকিৎসাগতভাবে সামঞ্জস্যপূর্ণ (সঙ্গতি দাতা এবং রোগীর রক্তের ধরণের উপর ভিত্তি করে নির্ধারিত হয়, পাশাপাশি অন্যান্য কারণ যেমন তাদের রক্তে নির্দিষ্ট অ্যান্টিজেন)। সামঞ্জস্য গ্রাফের একটি নির্দেশিত চক্র একটি সম্ভাব্য বিনিময়ের প্রতিনিধিত্ব করে। আকার 2-এর একটি নির্দেশিত চক্র (যেমন। এ-> বি-> এ) একটি সম্ভাব্য জোড়ার বিনিময়কে উপস্থাপন করে-এক জোড়া জোড়ার মধ্যে একটি বিনিময়। ও. কে. ই-এর আরও সাধারণ রূপটি দ্বিতীয় ধরনের নোডগুলিকেও বিবেচনা করে, যা পরোপকারী দাতাদের প্রতিনিধিত্ব করে-দাতারা যারা কোনও রোগীর সাথে যুক্ত নয় এবং যে কোনও সামঞ্জস্যপূর্ণ রোগীকে একটি কিডনি দান করতে ইচ্ছুক। আলট্রুইস্টিক ডোনার নোডগুলিতে কেবল বহির্গামী চাপ থাকে। পরোপকারী দাতাদের সাথে, কেবল চক্রের সাথেই নয়, শৃঙ্খলের সাথেও বিনিময়ের ব্যবস্থা করা সম্ভব, একজন পরোপকারী দাতা থেকে শুরু করে। গ্রাফের খিলানগুলির ওজন থাকতে পারে, যেমন। জড়িত প্রতিস্থাপনের সাফল্যের সম্ভাবনা। তাদের অগ্রাধিকারও থাকতে পারে, যেমন নির্ধারিত। চিকিৎসা সংক্রান্ত জরুরি অবস্থা বা রোগী প্রতিস্থাপনের সারিতে অপেক্ষা করার সময়। আউটপুট একটি ও. কে. ই-এর আউটপুট হল জোড়া-বিচ্ছিন্ন নির্দেশিত চক্রের একটি সেট (এবং সম্ভবত নির্দেশিত চেইন, যদি পরোপকারী দাতারা উপলব্ধ থাকে)। ও. কে. ই-এর সবচেয়ে সহজ উদ্দেশ্য হল কিডনি গ্রহণকারী রোগীদের সংখ্যা সর্বাধিক করা। অন্যান্য সাধারণ উদ্দেশ্যগুলি হলঃ কিডনি বিনিময়ের ওজনযুক্ত যোগফলকে সর্বাধিক করাঃ গ্রাফের প্রতিটি প্রান্তের একটি ওজন থাকে এবং লক্ষ্য হল এমন একটি বিনিময় খুঁজে বের করা যা বিনিময়ে ব্যবহৃত সমস্ত প্রান্তে ওজনের যোগফলকে সর্বাধিক করে। ট্রান্সপ্লান্ট প্রার্থীদের আয়ু বা তাদের গুণমান-সামঞ্জস্যপূর্ণ আয়ু সর্বাধিক করা। অনিয়ন্ত্রিত চক্রের দৈর্ঘ্য প্রাথমিকভাবে, বিনিময় চক্রের দৈর্ঘ্যের উপর কোনও সীমা ছাড়াই সমস্যাটি অধ্যয়ন করা হয়েছিল। রথ, সোনমেজ এবং আনভার পেরেটো-সর্বোত্তম এবং প্রণোদনা-সামঞ্জস্যপূর্ণ উপায়ে বিনিময় চক্র খুঁজে বের করার জন্য শীর্ষ বাণিজ্য চক্র ব্যবস্থার সম্প্রসারণের উপর ভিত্তি করে একটি প্রক্রিয়া উপস্থাপন করেছিলেন। আব্রাহাম, ব্লাম এবং স্যান্ডহোম দেখান যে, সীমাহীন চক্রের দৈর্ঘ্য সহ, সর্বাধিক-কার্ডিনালিটি এবং সর্বাধিক-ওজন বিনিময় বহুপদী সময়ে পাওয়া যেতে পারে। উদাহরণস্বরূপ, একটি ম্যাক্সিয়াম-কার্ডিনালিটি বিনিময় খুঁজে বের করার জন্য, মূল নির্দেশিত গ্রাফ জি দেওয়া, একটি অনির্দিষ্ট দ্বিদলীয় গ্রাফ এইচ (এক্স + ওয়াই, ই) তৈরি করুন যেখানেঃ জি-তে প্রতিটি জোড়া জে-এর দুটি নোড রয়েছেঃ এক্সজে (দাতার প্রতিনিধিত্বকারী) এবং ওয়াইজে (রোগীর প্রতিনিধিত্বকারী)। এগুলি ওজন 1-এর একটি প্রান্ত দ্বারা সংযুক্ত। জি-তে প্রতিটি প্রান্তের জন্য, এইচ-এ একটি প্রান্ত xi-- 1 + 1/এন ওজনের yj যোগ করুন। এইচ-এ সর্বাধিক ওজনের মিল খুঁজে বের করুন। জি-তে প্রতিটি সর্বাধিক-কার্ডিনালিটি বিনিময় এইচ-এ সর্বাধিক ওজনের মিলনের সাথে মিলে যায়। মনে রাখবেন যে ওজনগুলি গ্যারান্টি দেয় যে এইচ-এ প্রতিটি সর্বাধিক ওজনের মিল নিখুঁত, যাতে প্রতিটি রোগী কোনও সামঞ্জস্যপূর্ণ দাতার সাথে বা তার নিজের দাতার সাথে মিলে যায়। সুতরাং কোনও দাতা একটি কিডনি দেয় না যদি না তার রোগী একটি কিডনি পায়, যা ব্যক্তিগত যৌক্তিকতার প্রয়োজনীয়তা পূরণ করে। এই অ্যালগরিদমটি সর্বাধিক ওজনের বিনিময়ে প্রসারিত করা এবং পরার্থপর দাতাদের অন্তর্ভুক্ত করা সহজ। 2004 সালে নিউ ইংল্যান্ডে একটি কিডনি বিনিময় কর্মসূচি বাস্তবায়নের লক্ষ্যে আলোচনায় দেখা যায় যে, যৌক্তিকভাবে, শুধুমাত্র জোড়া বিনিময় সম্ভব। এর কারণ হল, বিনিময়ের সমস্ত কাজ একযোগে করতে হয়। এই প্রয়োজনীয়তার লক্ষ্য হল ব্যক্তিগত যৌক্তিকতার সীমাবদ্ধতা নিশ্চিত করা-একজন দাতা তার রোগীর কিডনি পাওয়ার পরে দান করতে অস্বীকার করার ঝুঁকি এড়াতে। k আকারের একটি বিনিময় চক্রের জন্য 2k যুগপৎ ক্রিয়াকলাপ প্রয়োজন। সেই সময়ে, একযোগে 4টির বেশি ক্রিয়াকলাপের ব্যবস্থা করা ব্যবহারিক ছিল না, তাই চক্রের আকার 2-এর মধ্যে সীমাবদ্ধ ছিল। এই সেটিংসে, নির্দেশিত সামঞ্জস্যতা গ্রাফকে একটি অনির্দিষ্ট গ্রাফে হ্রাস করা সম্ভব, যেখানে জোড়া এ এবং বি সংযুক্ত থাকে যদি এবং শুধুমাত্র যদি এ-> বি এবং বি-> এ হয়। সর্বাধিক-কার্ডিনালিটি পেয়ারওয়াইজ এক্সচেঞ্জ খুঁজে পাওয়া সেই অনির্দিষ্ট গ্রাফে সর্বাধিক কার্ডিনালিটি ম্যাচিং খুঁজে পাওয়ার সমতুল্য। উপরন্তু, যখন শুধুমাত্র জোড়া বিনিময় অনুমোদিত হয়, একটি ম্যাচিং পারেটো-দক্ষ হয় যদি এবং শুধুমাত্র যদি এটির সর্বাধিক কার্ডিনালিটি থাকে। অতএব, এই ধরনের বিনিময় বহুপদী সময়ে পাওয়া যেতে পারে। রথ, সোনমেজ এবং আনভার সাধারণ সর্বাধিক-কার্ডিনালিটি বিনিময়ের দুটি সম্প্রসারণ অধ্যয়ন করেছেনঃ রোগী বা প্রতিস্থাপনের উপর একটি অগ্রাধিকার র্যাঙ্কিং দেওয়া, বহুপদী সময়ে একটি অগ্রাধিকার মিল খুঁজে পাওয়া সম্ভব-একটি মিল যা সমস্ত সর্বাধিক-কার্ডিনালিটি মিলনের মধ্যে, উচ্চতর-অগ্রাধিকার রোগীদের সংখ্যা সর্বাধিক করে। উপরন্তু, এই অ্যালগরিদমগুলি এই অর্থে প্রণোদনা-সামঞ্জস্যপূর্ণ করা যেতে পারে যে প্রতিটি রোগী সিস্টেমে যতটা সম্ভব দাতাদের নিয়ে এসে এবং যতটা সম্ভব কিডনি গ্রহণ করতে সম্মত হয়ে তার মিলিত হওয়ার সম্ভাবনাকে সর্বাধিক করে তোলে। প্রমাণগুলি গ্রাফ তত্ত্ব থেকে ধারণাগুলি ব্যবহার করে, যেমন গ্যালাই-এডমন্ডস পচন। একটি স্টোকাস্টিক এক্সচেঞ্জ খুঁজে পাওয়া সম্ভব, যেখানে সমস্ত সর্বাধিক-কার্ডিনালিটি ম্যাচিং থেকে এলোমেলোভাবে একটি ম্যাচিং নির্বাচন করা হয়। সমতার প্রক্রিয়াটির লক্ষ্য হল একজন রোগীর কিডনি পাওয়ার ক্ষুদ্রতম সম্ভাবনাকে সর্বাধিক করা। সমতাবাদী প্রক্রিয়াটি অগ্রাধিকার ব্যবস্থার মতো একই অর্থে প্রণোদনা-সামঞ্জস্যপূর্ণ। k দৈর্ঘ্যের চক্র পরবর্তী বছরগুলিতে, লজিস্টিক উন্নতিগুলি একযোগে আরও বেশি সংখ্যক ক্রিয়াকলাপ সম্পাদনের অনুমতি দেয়। তদনুসারে, তিন বা ততোধিক জোড়া জড়িত বিনিময় চক্র সম্ভব হয়েছিল। সর্বাধিক-কার্ডিনালিটি বিনিময় খুঁজে বের করাকে বলা হয়, গ্রাফ তাত্ত্বিক পরিভাষায়, সর্বাধিক চক্র প্যাকিং। সর্বাধিক k দৈর্ঘ্যের চক্র সহ সর্বাধিক চক্র প্যাকিং, যে কোনও নির্দিষ্ট k ≤ 3-এর জন্য, একটি এনপি-হার্ড গণনামূলক সমস্যা (এটি একটি হাইপারগ্রাফে ত্রিমাত্রিক মিলনের সমস্যা থেকে হ্রাস করে প্রমাণিত করা যেতে পারে)। আব্রাহাম, ব্লাম এবং স্যান্ডহোম সর্বাধিক সাইকেল প্যাকিংয়ের জন্য দুটি কৌশল উপস্থাপন করেছেনঃ কলাম জেনারেশন এবং কনস্ট্র্যান্ট জেনারেশন। তারা রিপোর্ট করে যে কলাম প্রজন্মের স্কেল অনেক ভাল। তাদের অ্যালগরিদম অ্যালায়েন্স ফর পেয়ার্ড কিডনি ডোনেশনে প্রয়োগ করা হয়েছে। বিরো, ম্যানলভ এবং রিজ্জি এই সমস্যা সমাধানের জন্য দুটি পদ্ধতির পরামর্শ দেন এমনকি যখন প্রান্তগুলির ওজন থাকে (এই ক্ষেত্রে এটিকে সর্বাধিক ওজনের চক্র প্যাকিং বলা হয়): সর্বাধিক ওজনের স্বাধীন সেটের জন্য পরিচিত আনুমানিক অ্যালগরিদমের উপর ভিত্তি করে একটি আনুমানিক অ্যালগরিদম; একটি সঠিক অ্যালগরিদম, চক্রের হাইপারগ্রাফকে একটি গ্রাফে রূপান্তর করার সমস্ত উপায় পদ্ধতিগতভাবে পরীক্ষা করে। অ্যালগরিদমটি সময়মতো চলে, যেখানে s হল প্রতিটি 3-চক্র থেকে একটি করে চাপ সম্বলিত একটি সেটের আকার। কে দৈর্ঘ্যের চক্র এবং সীমাহীন দৈর্ঘ্যের চেইন আলট্রুইস্টিক দাতাদের বিনিময়ের একটি চেইন শুরু করতে ব্যবহার করা যেতে পারে, যা কোনও চক্র নয়। এই ধরনের শৃঙ্খলে, অপারেশনগুলি একযোগে করার প্রয়োজন নেইঃ প্রতিটি রোগীকে গ্যারান্টি দেওয়া সম্ভব যে তার দাতা একটি কিডনি দেওয়ার আগে সে একটি কিডনি পায়। যদি কোনও দাতার ত্রুটি থাকে, তবে এটি চেইনটি ভেঙে দেয়, তবে এটি এমন রোগীদের ক্ষতি করে না যাদের দাতা ইতিমধ্যে একটি কিডনি দিয়েছেন, তাই এটি ব্যক্তিগত যৌক্তিকতা ভেঙে দেয় না। অ্যান্ডারসন, আশলাগি, গামার্নিক এবং রথ সর্বাধিক কে দৈর্ঘ্যের চক্র এবং সীমাহীন দৈর্ঘ্যের চেইনে সর্বাধিক-কার্ডিনালিটি প্যাকিং খুঁজে বের করার জন্য দুটি অ্যালগরিদম উপস্থাপন করেছেনঃ একটি পূর্ণসংখ্যা রৈখিক প্রোগ্রামিং এবং সীমাবদ্ধতা প্রজন্মের উপর ভিত্তি করে; অন্যটি ভ্রমণকারী বিক্রেতার সমস্যার সমাধানের উপর ভিত্তি করে। অনিশ্চিত প্রতিস্থাপন ও. কে. ই-তে প্রাথমিক তাত্ত্বিক কাজগুলি ধরে নিয়েছিল যে, একবার বিনিময়ের একটি সেট নির্ধারণ করা হলে, সেগুলি সবই কার্যকর করা হবে। বাস্তবে, তবে, প্রতিস্থাপন বাতিল করা যেতে পারে। উদাহরণস্বরূপ, প্রতিস্থাপনের ঠিক আগে করা চিকিৎসা পরীক্ষাটি প্রকাশ করতে পারে যে দাতা রোগীর সাথে অসঙ্গতিপূর্ণ, যদিও ডাটাবেসে তারা সামঞ্জস্যপূর্ণ হিসাবে নিবন্ধিত। অতএব, নতুন কাজের লক্ষ্য হল প্রতিস্থাপনের প্রত্যাশিত সংখ্যা সর্বাধিক করা। উদাহরণস্বরূপ, আলভেলোস, ক্লিমেনটোভা এবং ভিয়ানা এই সমস্যার জন্য একটি শাখা-এবং-মূল্য অ্যালগরিদম উপস্থাপন করে। কিডনি বিনিময়ের জন্য পূর্ণসংখ্যা-প্রোগ্রামিং মডেলগুলির আরও উল্লেখ রয়েছে। রেফারেন্স অপ্টিমাইজেশন অ্যালগরিদম এবং পদ্ধতি অঙ্গ দান