গবেষকরা সেমিনাল সমস্যার জন্য নতুন গতি সীমার দিকে যাচ্ছেন | কোয়ান্টা ম্যাগাজিন

ভ্রমণ বিক্রয়কর্মী সমস্যাটি প্রাচীনতম পরিচিত গণনামূলক প্রশ্নগুলির মধ্যে একটি। এটি মাইলেজ কমিয়ে শহরের একটি নির্দিষ্ট তালিকার মাধ্যমে আদর্শ পথের জন্য জিজ্ঞাসা করে। আপাতদৃষ্টিতে সহজ মনে হলেও, সমস্যাটি কুখ্যাতভাবে কঠিন। আপনি সংক্ষিপ্ততম পথ খুঁজে না পাওয়া পর্যন্ত সমস্ত সম্ভাব্য রুটগুলি পরীক্ষা করার জন্য নৃশংস শক্তি ব্যবহার করতে পারেন, এই ধরনের একটি কৌশল শুধুমাত্র মুষ্টিমেয় শহরগুলির পরে অক্ষম হয়ে যায়। পরিবর্তে, আপনি লিনিয়ার প্রোগ্রামিং নামে একটি কঠোর গাণিতিক মডেল প্রয়োগ করতে পারেন, যা মোটামুটি সমীকরণের সেট হিসাবে সমস্যাটিকে আনুমানিক করে এবং সর্বোত্তম সমাধান খুঁজে পেতে সম্ভাব্য সমন্বয়গুলিকে পদ্ধতিগতভাবে পরীক্ষা করে।

কিন্তু কখনও কখনও, পূর্ণ-সংখ্যার পরিমাণ জড়িত সমস্যাগুলির জন্য আপনাকে অপ্টিমাইজ করতে হবে। 500.7 পালঙ্ক তৈরি করে এমন একটি ফ্যাক্টরি অপ্টিমাইজেশন প্ল্যান কী ভালো? এই জন্য, গবেষকরা প্রায়ই লিনিয়ার প্রোগ্রামিং নামক একটি বৈকল্পিক চালু পূর্ণসংখ্যা লিনিয়ার প্রোগ্রামিং (ILP)। উৎপাদন পরিকল্পনা, এয়ারলাইন ক্রু শিডিউলিং এবং যানবাহন রাউটিং সহ বিচ্ছিন্ন সিদ্ধান্ত জড়িত অ্যাপ্লিকেশনগুলিতে এটি জনপ্রিয়। "মূলত, আইএলপি তত্ত্ব এবং অনুশীলন উভয় ক্ষেত্রেই অপারেশন গবেষণার রুটি এবং মাখন," বলেন সন্তোষ ভেম্পালা, জর্জিয়া ইনস্টিটিউট অফ টেকনোলজির একজন কম্পিউটার বিজ্ঞানী।

যেহেতু তারা প্রথম আইএলপি তৈরি করেছিল 60 বছর আগে, গবেষকরা বিভিন্ন অ্যালগরিদম আবিষ্কার করেছেন যেগুলি ILP সমস্যার সমাধান করে, কিন্তু সেগুলি প্রয়োজনীয় পদক্ষেপের সংখ্যার দিক থেকে তুলনামূলকভাবে ধীরগতির হয়েছে৷ তারা যে সর্বোত্তম সংস্করণটি নিয়ে আসতে পারে — এক ধরণের গতি সীমা — তুচ্ছ ঘটনা থেকে আসে যেখানে সমস্যার ভেরিয়েবল (যেমন একজন বিক্রয়কর্মী একটি শহরে যান কি না) শুধুমাত্র বাইনারি মান (শূন্য বা 1) ধরে নিতে পারে। এই ক্ষেত্রে, ILP-এর একটি রানটাইম রয়েছে যা ভেরিয়েবলের সংখ্যার সাথে তাত্পর্যপূর্ণভাবে স্কেল করে, যাকে মাত্রাও বলা হয়। (যদি শুধুমাত্র একটি ভেরিয়েবল থাকে, তবে প্রতিটি সম্ভাব্য সংমিশ্রণ পরীক্ষা করতে এবং সমস্যাটি সমাধান করার জন্য এটি মাত্র দুটি পদক্ষেপ নেয়; দুটি ভেরিয়েবল মানে চারটি ধাপ, তিনটি মানে আটটি ধাপ ইত্যাদি।)

দুর্ভাগ্যবশত, একবার ভেরিয়েবলগুলি শূন্য এবং 1 এর বাইরে একটি মান গ্রহণ করলে, অ্যালগরিদমের রানটাইম অনেক বেশি বৃদ্ধি পায়। গবেষকরা দীর্ঘদিন ধরে ভাবছেন যে তারা তুচ্ছ আদর্শের কাছাকাছি যেতে পারে কিনা। অগ্রগতি ধীর হয়েছে, সঙ্গে নথি 1980-এর দশকে সেট করা হয়েছে এবং শুধুমাত্র ক্রমবর্ধমান উন্নতি থেকে তৈরি

কিন্তু সাম্প্রতিক কাজ by ভিক্টর রেইস, বর্তমানে ইনস্টিটিউট ফর অ্যাডভান্সড স্টাডিতে, এবং টমাস রথভোস, ওয়াশিংটন বিশ্ববিদ্যালয়ে, কয়েক দশকের মধ্যে সবচেয়ে বড় রানটাইম লিপ করেছে৷ সম্ভাব্য সমাধানগুলিকে সীমিত করার জন্য জ্যামিতিক সরঞ্জামগুলিকে একত্রিত করে, তারা তুচ্ছ বাইনারি ক্ষেত্রে প্রায় একই সময়ে ILP সমাধানের জন্য একটি নতুন, দ্রুত অ্যালগরিদম তৈরি করেছে। ফলাফল 2023 এ একটি সেরা-পেপার পুরস্কার পেয়েছে কম্পিউটার বিজ্ঞানের ভিত্তি সম্মেলনে।

"এই নতুন অ্যালগরিদম অত্যন্ত উত্তেজনাপূর্ণ," বলেছেন নোয়া স্টিফেনস-ডেভিডোভিটজ, কর্নেল বিশ্ববিদ্যালয়ের একজন গণিতবিদ এবং কম্পিউটার বিজ্ঞানী। "এটি প্রায় 40 বছরে ILP সমাধানকারীদের প্রথম [প্রধান] উন্নতির প্রতিনিধিত্ব করে।"

ILP একটি প্রদত্ত সমস্যাকে রৈখিক সমীকরণের একটি সেটে রূপান্তর করে কাজ করে যা অবশ্যই কিছু অসমতা পূরণ করতে হবে। নির্দিষ্ট সমীকরণগুলি মূল সমস্যার বিবরণের উপর ভিত্তি করে। কিন্তু যদিও এই বিবরণগুলি ভিন্ন হতে পারে, আইএলপি সমস্যার মৌলিক মেকআপ একই থাকে, যা গবেষকদের অনেক সমস্যা আক্রমণ করার একক উপায় দেয়।

এটা বলার অপেক্ষা রাখে না যে এটি সহজ কাজ। এটা 1983 সাল পর্যন্ত ছিল না যে গণিতবিদ হেনড্রিক লেনস্ট্রা প্রতিপন্ন যে সাধারণ সমস্যাটি এমনকি সমাধানযোগ্য ছিল, এটি করতে পারে এমন প্রথম অ্যালগরিদম প্রদান করে। লেনস্ট্রা জ্যামিতিকভাবে ILP সম্পর্কে চিন্তা করেছিলেন। প্রথমত, তিনি ILP-এর কেন্দ্রস্থলে অসমতাকে একটি উত্তল আকৃতিতে পরিণত করেছেন, যেমন যেকোন নিয়মিত বহুভুজ। এই আকৃতিটি আপনি যে স্বতন্ত্র সমস্যাটি সমাধান করছেন তার সীমাবদ্ধতাগুলিকে প্রতিনিধিত্ব করে, এটি পালঙ্ক উত্পাদন বা বিমানের সময়সূচী হোক না কেন, তাই আকৃতির অভ্যন্তরীণ সমস্ত সম্ভাব্য মানগুলির সাথে সামঞ্জস্যপূর্ণ যা অসমতাগুলি সমাধান করতে পারে এবং এইভাবে সমস্যাটি। লেন্সট্রা এই আকৃতিকে উত্তল দেহ বলে। সমস্যার মাত্রা এই আকৃতির মাত্রাকে প্রভাবিত করে: দুটি ভেরিয়েবল সহ এটি একটি সমতল বহুভুজের রূপ নেয়; তিন মাত্রায় এটি একটি প্লাটোনিক শক্ত, এবং তাই।

লেন্সট্রা পরবর্তীতে সমস্ত পূর্ণসংখ্যাকে গ্রিড পয়েন্টের একটি অসীম সেট হিসাবে কল্পনা করেছিলেন, যা গণিতে জালি হিসাবে পরিচিত। একটি দ্বি-মাত্রিক সংস্করণ বিন্দুর সমুদ্রের মতো দেখায় এবং তিন মাত্রায় এটি বিল্ডিংয়ের ইস্পাত রশ্মি সংযোগকারী বিন্দুগুলির মতো দেখায়। জালির মাত্রা প্রদত্ত সমস্যার মাত্রার উপরও নির্ভর করে।

একটি প্রদত্ত ILP সমস্যা সমাধানের জন্য, Lenstra দেখিয়েছেন যে আপনি সম্ভাব্য সমাধানগুলি কোথায় পূর্ণসংখ্যার সেটের সাথে মিলিত হয় তা দেখুন: উত্তল বডি এবং জালির সংযোগস্থলে। এবং তিনি একটি অ্যালগরিদম নিয়ে এসেছিলেন যা এই স্থানটি সম্পূর্ণভাবে অনুসন্ধান করতে পারে — কিন্তু কার্যকরী হতে, এটিকে কখনও কখনও সমস্যাটিকে ছোট মাত্রার টুকরো টুকরো করতে হয়, রানটাইমে অনেকগুলি ধাপ যুক্ত করে।

পরবর্তী বছরগুলিতে, বেশ কয়েকজন গবেষক এই অ্যালগরিদমটিকে কীভাবে দ্রুত চালানো যায় তা অনুসন্ধান করেছেন। 1988 সালে, রবি কান্নান এবং লাসজলো লোভাস কভারিং ব্যাসার্ধ নামে একটি ধারণা চালু করেছিলেন, ধার করা এর গবেষণা থেকে ত্রুটি-সংশোধনকারী কোড, উত্তল বডি এবং জালিকে আরও দক্ষতার সাথে ছেদ করতে সাহায্য করতে। মোটামুটিভাবে, কভারিং ব্যাসার্ধ নিশ্চিত করে যে উত্তল বডিতে সর্বদা অন্তত একটি পূর্ণসংখ্যা বিন্দু থাকে, আপনি এটিকে জালির উপর যেখানেই রাখুন না কেন। ফলস্বরূপ, কভারিং ব্যাসার্ধের আকারও নির্ধারণ করে আপনি কতটা দক্ষতার সাথে ILP সমস্যা সমাধান করতে পারেন।

সুতরাং এটি সবই আদর্শ কভারিং ব্যাসার্ধের আকার নির্ধারণে নেমে এসেছে। দুর্ভাগ্যবশত, এটি নিজেই একটি কঠিন সমস্যা হিসাবে প্রমাণিত হয়েছে, এবং কান্নান এবং লোভাস যা করতে পারে তা হল উপরের এবং নীচের সীমানা অনুসন্ধান করে একটি সম্ভাব্য মানকে সংকুচিত করা। তারা দেখিয়েছে যে উপরের বাউন্ড - কভারিং ব্যাসার্ধের সর্বাধিক আকার - মাত্রার সাথে রৈখিকভাবে স্কেল করা হয়েছে. এটি বেশ দ্রুত ছিল, কিন্তু উল্লেখযোগ্যভাবে ILP রানটাইম গতি বাড়ানোর জন্য যথেষ্ট নয়। পরবর্তী 30 বছরে, অন্যান্য গবেষকরা শুধুমাত্র সামান্য ভাল করতে পারে।

রেইস এবং রথভোসকে শেষ পর্যন্ত যা সাহায্য করেছিল তা হল একটি সম্পর্কহীন গাণিতিক ফলাফল যা সম্পূর্ণরূপে জালির উপর দৃষ্টি নিবদ্ধ করেছিল। 2016 সালে, Oded Regev এবং Stephens-Davidowitz দেখিয়েছেন, কার্যত, একটি নির্দিষ্ট আকৃতির মধ্যে কতগুলি জালি বিন্দু ফিট হতে পারে। রেইস এবং রথভোস এটিকে অন্যান্য আকারে প্রয়োগ করেছে, যা তাদের আইএলপি কভারিং ব্যাসার্ধে থাকা জালি বিন্দুর সংখ্যা আরও ভালভাবে অনুমান করতে দেয়, উপরের সীমাকে কমিয়ে দেয়। "সর্বশেষ অগ্রগতি এই উপলব্ধির সাথে এসেছে যে আপনি আসলে অন্য ধরণের আকারগুলি করতে পারেন," রেগেভ বলেছিলেন।

এই নতুন আঁটসাঁট করা উপরের বাউন্ডটি ছিল একটি বিশাল উন্নতি, যার ফলে Reis এবং Rothvoss সামগ্রিক ILP অ্যালগরিদমের একটি নাটকীয় গতি অর্জন করতে পারে। তাদের কাজ রানটাইমকে (লগ n)^O(n), কোথায় n ভেরিয়েবলের সংখ্যা এবং উপর)মানে এটি রৈখিকভাবে স্কেল করে n. (এই অভিব্যক্তিটিকে "প্রায়" বাইনারি সমস্যার রান টাইম হিসাবে বিবেচনা করা হয়।)

"এটি গণিত, কম্পিউটার বিজ্ঞান এবং জ্যামিতির সংযোগস্থলে একটি বিজয়," বলেন ড্যানিয়েল দাদুশ নেদারল্যান্ডসের জাতীয় গবেষণা ইনস্টিটিউট সিডব্লিউআই-এর, যিনি আইএলপি রানটাইম পরিমাপ করতে ব্যবহৃত অ্যালগরিদম রেইস এবং রথভোসকে অগ্রগামী করতে সহায়তা করেছিলেন।

আপাতত, নতুন অ্যালগরিদমটি আসলে কোনো লজিস্টিক সমস্যা সমাধানের জন্য ব্যবহার করা হয়নি, যেহেতু এটি ব্যবহার করতে আজকের প্রোগ্রামগুলি আপডেট করতে খুব বেশি কাজ করতে হবে। কিন্তু রথভোসের জন্য, এটি বিন্দুর পাশে। "এটি একটি সমস্যার তাত্ত্বিক বোঝার বিষয়ে যার মৌলিক প্রয়োগ রয়েছে," তিনি বলেছিলেন।

ILP-এর কম্পিউটেশনাল দক্ষতা আরও উন্নত করা যেতে পারে কিনা, গবেষকরা এখনও আশাবাদী যে তারা আদর্শ রানটাইমের কাছে যেতে থাকবে - কিন্তু শীঘ্রই নয়। "এর জন্য একটি মৌলিকভাবে নতুন ধারণার প্রয়োজন হবে," ভেম্পলা বলেছিলেন।