Karmarkar–Karp bin packing algorithms
কারমারকার-কার্প (কেকে) বিন প্যাকিং অ্যালগরিদমগুলি বিন প্যাকিং সমস্যার জন্য বেশ কয়েকটি সম্পর্কিত আনুমানিক অ্যালগরিদম। বিন প্যাকিং সমস্যা হল বিভিন্ন আকারের জিনিসগুলিকে একই ক্ষমতার বিনগুলিতে প্যাক করার সমস্যা, যাতে মোট বিনগুলির সংখ্যা যতটা সম্ভব কম হয়। সর্বোত্তম সমাধান খুঁজে পাওয়া গণনামূলকভাবে কঠিন। কর্মকার এবং কার্প একটি অ্যালগরিদম তৈরি করেছিলেন যা বহুপদী সময়ে চলে এবং সর্বাধিক বিন দিয়ে একটি সমাধান খুঁজে পায়, যেখানে ওপিটি হল সর্বোত্তম সমাধানে বিনগুলির সংখ্যা। তারা সামান্য ভিন্ন আনুমানিক গ্যারান্টি এবং রান-টাইম সীমা সহ আরও বেশ কয়েকটি অ্যালগরিদম তৈরি করেছিল। কে কে অ্যালগরিদমগুলি বিন প্যাকিং অধ্যয়নে একটি যুগান্তকারী হিসাবে বিবেচিত হয়েছিলঃ পূর্বে পরিচিত অ্যালগরিদমগুলি গুণিতক আনুমানিক খুঁজে পেয়েছিল, যেখানে কিছু ধ্রুবকের জন্য বা সর্বাধিক পরিমাণে বিনগুলির সংখ্যা ছিল। কেকে অ্যালগরিদমগুলি প্রথম একটি যোগাত্মক আনুমানিক অর্জন করেছিল। বিন-প্যাকিং সমস্যার ইনপুট হল বিভিন্ন মাপের আইটেমের একটি সেট, a1,. an। নিম্নলিখিত স্বরলিপিটি ব্যবহার করা হয়ঃ n-বস্তুর সংখ্যা। এম-বিভিন্ন আকারের আইটেমের সংখ্যা। প্রতিটি i এর জন্য 1,., m: si হল i-তম আকার; ni হল আকারের আইটেমের সংখ্যা। বি-বিন আকার। একটি উদাহরণ I দেওয়া হলে, আমরা বোঝাইঃ উদাহরণ I-এর সর্বোত্তম সমাধান হল ওপিটি (আই) =। এফওপিটি (আই) = (এ1 +. + এ)/বি = তাত্ত্বিকভাবে সর্বোত্তম সংখ্যক বিন, যখন সমস্ত বিন সম্পূর্ণরূপে আইটেম বা আইটেম ভগ্নাংশ দিয়ে ভরা হয়। স্পষ্টতই, এফওপিটি (আই) ≤ ওপিটি (আই)। উচ্চ-স্তরের স্কিম কেকে অ্যালগরিদমগুলি মূলত কনফিগারেশন রৈখিক প্রোগ্রামটি সমাধান করেঃ এখানে, এ হল এম সারি সহ একটি ম্যাট্রিক্স। এ-এর প্রতিটি কলাম একটি সম্ভাব্য বিন্যাসের প্রতিনিধিত্ব করে-আইটেম-আকারের একটি মাল্টিসেট, যাতে এই সমস্ত আকারের যোগফল সর্বাধিক বি হয়। কনফিগারেশনের সেট হল সি. এক্স হল সি আকারের একটি ভেক্টর। এক্স-এর প্রতিটি উপাদান xc কনফিগারেশন সি-এর কতবার ব্যবহার করা হয় তা উপস্থাপন করে। উদাহরণস্বরূপঃ ধরুন আইটেমের মাপ 3,3,3,3,3,4,4,4,4,4, এবং B = 12। তারপর সি = 10টি সম্ভাব্য বিন্যাস রয়েছেঃ 3333; 333; 33,334; 3,44,444। ম্যাট্রিক্স এ-এর দুটি সারি রয়েছেঃ s = 3-এর জন্য [4,3,2,2,1,1,1,0,0,0] এবং s = 4-এর জন্য [0,0,0,1,0,1,2,1,2,3]। ভেক্টর এন হল [5,5] কারণ প্রতিটি আকারের 5টি করে বস্তু রয়েছে। একটি সম্ভাব্য সর্বোত্তম সমাধান হল x = [1,0,0,0,0,0,1,0,0,1], যা 3333,344,444 কনফিগারেশন সহ তিনটি বিন ব্যবহার করার সাথে সামঞ্জস্যপূর্ণ। এই সমস্যা সমাধানে দুটি প্রধান সমস্যা রয়েছে। প্রথমত, এটি একটি পূর্ণসংখ্যা রৈখিক প্রোগ্রাম, যা সমাধান করা গণনামূলকভাবে কঠিন। দ্বিতীয়ত, ভেরিয়েবলের সংখ্যা হল সি-কনফিগারেশনের সংখ্যা, যা বিশাল হতে পারে। কে কে অ্যালগরিদমগুলি বিভিন্ন কৌশল ব্যবহার করে এই সমস্যাগুলি মোকাবেলা করে, যার মধ্যে কয়েকটি ইতিমধ্যে ডি-লা-ভেগা এবং লুয়েকার দ্বারা চালু করা হয়েছিল। এখানে অ্যালগরিদমের একটি উচ্চ-স্তরের বিবরণ রয়েছে (যেখানে মূল উদাহরণটি রয়েছে): 1-এ। ছোট জিনিসগুলি সরিয়ে তৈরি করা একটি উদাহরণ ধরা যাক। 2-এ। আসুন একটি উদাহরণ তৈরি করা যাক যা আইটেমগুলিকে গোষ্ঠীভুক্ত করে এবং প্রতিটি গ্রুপের আইটেমগুলির আকারকে গ্রুপের সর্বোচ্চ আইটেমের সাথে বৃত্তাকার করে। 3-এ। অবিচ্ছেদ্যতার সীমাবদ্ধতা ছাড়াই কনফিগারেশন রৈখিক প্রোগ্রামটি তৈরি করুন। 4. শিথিল রৈখিক প্রোগ্রামের জন্য a (ভগ্নাংশ) সমাধান x গণনা করুন। 3-বি। জন্য একটি অবিচ্ছেদ্য সমাধানের জন্য x বৃত্তাকার করুন। 2-বি। সমাধান পেতে আইটেমগুলিকে "আন-গ্রুপ" করুন। 1-বি। একটি সমাধান পেতে ছোট জিনিসগুলি যোগ করুন। নীচে, আমরা পর্যায়ক্রমে এই পদক্ষেপগুলির প্রতিটি বর্ণনা করি। ধাপ 1। ছোট আইটেমগুলি অপসারণ এবং যুক্ত করা ছোট আইটেমগুলি অপসারণের প্রেরণা হল, যখন সমস্ত আইটেম বড় হয়, তখন প্রতিটি বিন-এ আইটেমের সংখ্যা অবশ্যই কম হতে হবে, তাই সম্ভাব্য কনফিগারেশনের সংখ্যা (তুলনামূলকভাবে) কম। আমরা কিছু ধ্রুবক বেছে নিই এবং মূল দৃষ্টান্ত থেকে তার চেয়ে ছোট সমস্ত আইটেম সরিয়ে ফেলি। ফলস্বরূপ উদাহরণটি ধরা যাক। মনে রাখবেন যে, প্রতিটি বিন-এ বেশিরভাগ জিনিস থাকতে পারে। আমরা প্যাক করি এবং কিছু বিন সহ একটি প্যাকিং পাই। এখন, যতক্ষণ জায়গা থাকে, ততক্ষণ আমরা ছোট জিনিসগুলি একটি নির্বিচারে ক্রমে বিদ্যমান বিনগুলিতে যুক্ত করি। যখন বিদ্যমান বিনগুলিতে আর জায়গা থাকে না, তখন আমরা একটি নতুন বিন খুলি (পরবর্তী মাপের বিন প্যাকিংয়ের মতো)। ধরা যাক চূড়ান্ত প্যাকিং-এ বিন-এর সংখ্যা কত। তারপরঃ প্রমাণ। যদি কোনও নতুন ডাস্টবিন না খোলা হয়, তাহলে ডাস্টবিনের সংখ্যা থেকে যায়। যদি একটি নতুন বিন খোলা হয়, তবে সম্ভবত শেষটি ব্যতীত সমস্ত বিন কমপক্ষে মোট আকার ধারণ করে, তাই মোট উদাহরণের আকার কমপক্ষে। অতএব, সর্বোত্তম সমাধানের জন্য কমপক্ষে বিন প্রয়োজন। তাই। বিশেষ করে, g = 1/n নিয়ে আমরা পাইঃ, যেহেতু। অতএব, এটি ধরে নেওয়া সাধারণ যে সমস্ত আইটেম 1/এন এর চেয়ে বড়। ধাপ 2। গ্রুপিং এবং আন-গ্রুপিং আইটেমগুলি গ্রুপিংয়ের অনুপ্রেরণা হল বিভিন্ন আইটেমের আকারের সংখ্যা হ্রাস করা, কনফিগারেশন এলপিতে সীমাবদ্ধতার সংখ্যা হ্রাস করা। সাধারণ গোষ্ঠীকরণ প্রক্রিয়াটি হ 'লঃ অবরোহী আকার অনুসারে আইটেমগুলি অর্ডার করুন। জিনিসগুলিকে দলে ভাগ করুন। প্রতিটি গ্রুপের জন্য, গ্রুপের সমস্ত আইটেমের আকারকে গ্রুপের বৃহত্তম আকারে পরিবর্তন করুন। গোষ্ঠীবদ্ধকরণের বিভিন্ন পদ্ধতি রয়েছে। লিনিয়ার গ্রুপিং একটি পূর্ণসংখ্যা পরামিতি হতে হবে। গ্রুপ 1-এ সবচেয়ে বড় আইটেমগুলি রাখুন; গ্রুপ 2-এ পরবর্তী বৃহত্তম আইটেমগুলি; এবং আরও অনেক কিছু (শেষ গ্রুপে আইটেমগুলির চেয়ে কম থাকতে পারে)। মূল উদাহরণটি ধরা যাক। ধরা যাক প্রথম গ্রুপ (বৃহত্তম আইটেমগুলির গ্রুপ), এবং প্রথম গ্রুপ ছাড়া গোষ্ঠীভুক্ত উদাহরণ। তারপরঃ সমস্ত জিনিসের আকার একই। বিভিন্ন আকারের সংখ্যায়। - যেহেতু গ্রুপ 1-এ গ্রুপ 2-এ আধিপত্য বিস্তার করে (গ্রুপ 1-এর সমস্ত কে আইটেম গ্রুপ 2-এর কে আইটেমগুলির চেয়ে বড়); একইভাবে, গ্রুপ 2-এ গ্রুপ 3-এ আধিপত্য বিস্তার করে ইত্যাদি। - যেহেতু প্রতিটি জিনিস একটি একক বিনে প্যাক করা সম্ভব। অতএব, প্রকৃতপক্ষে, বিন দিয়ে একটি সমাধান দেওয়া হলে, আমরা বেশিরভাগ বিন দিয়ে একটি সমাধান পেতে পারি। জ্যামিতিক গোষ্ঠীকরণ ধরা যাক একটি পূর্ণসংখ্যা পরামিতি। জ্যামিতিক গোষ্ঠীকরণ দুটি ধাপে এগিয়ে যায়ঃ দৃষ্টান্তটিকে বেশ কয়েকটি ক্ষেত্রে এমনভাবে ভাগ করুন যাতে প্রতিটি ক্ষেত্রে, সমস্ত আকার ব্যবধানের মধ্যে থাকে। মনে রাখবেন যে, যদি সমস্ত আইটেমের কমপক্ষে আকার থাকে, তবে দৃষ্টান্তের সংখ্যা সর্বাধিক। প্রতিটি ক্ষেত্রে, পরামিতি সহ রৈখিক বৃত্তাকার সঞ্চালন করুন। ফলস্বরূপ দৃষ্টান্তগুলি ধরা যাক। যাক এবং। তারপর, বিভিন্ন আকারের সংখ্যা নিম্নরূপ সীমাবদ্ধঃ সমস্ত r এর জন্য, এবং। যেহেতু সমস্ত আইটেমগুলি এর চেয়ে বড়, তাই আমাদের আছে। সমস্ত r-এর উপর সংক্ষিপ্তসার করলে পাওয়া যায়। বিনগুলির সংখ্যা নিম্নরূপ সীমাবদ্ধঃ সমস্ত আর-এর জন্য,-যেহেতু আইটেম রয়েছে এবং সেগুলির সবগুলিই এর চেয়ে ছোট, তাই এগুলি সর্বাধিক বিনগুলিতে প্যাক করা যেতে পারে। অতএব, অতএব, বিকল্প জ্যামিতিক গোষ্ঠীকরণ ধরা যাক একটি পূর্ণসংখ্যা পরামিতি। অবরোহী আকার অনুযায়ী জিনিসগুলি অর্ডার করুন। তাদের এমনভাবে গোষ্ঠীতে ভাগ করুন যাতে প্রতিটি গোষ্ঠীর মোট আকার কমপক্ষে হয়। যেহেতু প্রতিটি আইটেমের আকার বি-এর চেয়ে কম, তাই প্রতিটি গ্রুপের আইটেমের সংখ্যা কমপক্ষে। প্রতিটি গ্রুপের পণ্যের সংখ্যা দুর্বলভাবে বৃদ্ধি পাচ্ছে। যদি সমস্ত আইটেম এর চেয়ে বড় হয়, তবে প্রতিটি গ্রুপের আইটেমের সংখ্যা সর্বাধিক। প্রতিটি গ্রুপে, শুধুমাত্র বড় আইটেমগুলি একত্রিত করা হয়। এটি এমনভাবে করা যেতে পারে যেঃ । ধাপ 3। এলপি তৈরি করা এবং সমাধানটি বৃত্তাকার করা আমরা অখণ্ডতার সীমাবদ্ধতা ছাড়াই কনফিগারেশন রৈখিক প্রোগ্রামটি বিবেচনা করিঃ এখানে, আমাদের প্রতিটি কনফিগারেশনের একটি ভগ্নাংশ সংখ্যা ব্যবহার করার অনুমতি দেওয়া হয়। উদাহরণস্বরূপঃ ধরুন 3 আকারের 31টি আইটেম এবং 4 আকারের 7টি আইটেম রয়েছে এবং বিন-আকার 10টি। বিন্যাসগুলি হলঃ 4,44,34,334,3,33,333। সীমাবদ্ধতাগুলি হল [0,0,1,2,1,2,3] * x = 31 এবং [1,2,1,1,0,0,0] * x = 7। ভগ্নাংশ LP-এর একটি সর্বোত্তম সমাধান হল [0,0,0,7,0,0,17/3] অর্থাৎঃ 334 বিন্যাসের 7টি বিন এবং 333 বিন্যাসের 17/3 বিন রয়েছে। মনে রাখবেন যে শুধুমাত্র দুটি ভিন্ন বিন্যাসের প্রয়োজন। এলওপিটি দ্বারা রৈখিক প্রোগ্রামের সর্বোত্তম সমাধান নির্দেশ করুন। নিম্নলিখিত সম্পর্কগুলি সুস্পষ্টঃ এফ. ও. পি. টি (আই) ≤ এল. ও. পি. টি (আই), যেহেতু এফ. ও. পি. টি (আই) হল বিনগুলির (সম্ভবত ভগ্নাংশ) সংখ্যা যখন সমস্ত বিন সম্পূর্ণরূপে আইটেম বা আইটেমের ভগ্নাংশ দিয়ে ভরা হয়। স্পষ্টতই, কোনও সমাধানই এর চেয়ে বেশি কার্যকর হতে পারে না। এল. ও. পি. টি (আই) ≤ ও. পি. টি (আই), যেহেতু এল. ও. পি. টি (আই) কম সীমাবদ্ধতার সাথে একটি ন্যূনতম সমস্যার সমাধান। ওপিটি (আই) <2 * এফওপিটি (আই), যেহেতু কমপক্ষে 2 * এফওপিটি (আই) বিন সহ যে কোনও প্যাকিংয়ে, দুটি ন্যূনতম পূর্ণ বিনগুলির যোগফল সর্বাধিক বি হয়, তাই সেগুলি একটি একক বিন-এ একত্রিত করা যেতে পারে। ভগ্নাংশ এলপি-র একটি সমাধান নিম্নরূপ একটি অবিচ্ছেদ্য সমাধানে বৃত্তাকার করা যেতে পারে। ধরুন আমাদের ভগ্নাংশ এলপি-র একটি সমাধান x আছে। আমরা নিম্নরূপ ইন্টিগ্রাল আইএলপি-র জন্য একটি সমাধানে x কে বৃত্তাকার করি। ধরা যাক x ভগ্নাংশ LP-এর একটি সর্বোত্তম মৌলিক সম্ভাব্য সমাধান। মনে করুন এটি বিন হিসাবে (নোট যে একটি ভগ্নাংশ সংখ্যা হতে পারে)। যেহেতু ভগ্নাংশ LP-র m সীমাবদ্ধতা রয়েছে (প্রতিটি স্বতন্ত্র আকারের জন্য একটি), x-এর সর্বাধিক m অ-শূন্য চলক রয়েছে, অর্থাৎ সর্বাধিক m বিভিন্ন কনফিগারেশন ব্যবহার করা হয়। আমরা x থেকে একটি অবিচ্ছেদ্য প্যাকিং তৈরি করি যা একটি প্রধান অংশ এবং একটি অবশিষ্ট অংশ নিয়ে গঠিত। প্রধান অংশে প্রতিটি কনফিগারেশন সি-এর মেঝে (এক্সসি) বিন রয়েছে যার জন্য এক্সসি> 0। অবশিষ্ট অংশের জন্য (আর দ্বারা চিহ্নিত), আমরা দুটি প্রার্থী প্যাকিং তৈরি করিঃ প্রতিটি কনফিগারেশন সি-এর একটি একক বিন যার জন্য xc> 0; সমস্ত এম বিনের প্রয়োজন হয়। একটি লোভী প্যাকিং, 2 * এফওপিটি (আর)-এর কম বিন সহ (যেহেতু কমপক্ষে 2 * এফওপিটি (আর) বিন থাকলে, দুটি ক্ষুদ্রতম একত্রিত করা যেতে পারে)। এই প্যাকিংগুলির মধ্যে সবচেয়ে ছোটটির জন্য ন্যূনতম (এম, 2 * এফওপিটি (আর)) ≤ গড় (এম, 2 * এফওপিটি (আর)) = এফওপিটি (আর) + এম/2 প্রয়োজন। এর সাথে মূল অংশের বৃত্তাকার-ডাউন বিনগুলি বেশিরভাগ বিনগুলিতে ফলন দেয়। এই রূপান্তর অ্যালগরিদমের কার্যকর সময় হল ও (এন লগ এন)। এটাও বোঝায়। ধাপ 4। ভগ্নাংশ এল. পি সমাধান করা ভগ্নাংশ এল. পি সমাধানের প্রধান চ্যালেঞ্জ হল যে এতে প্রচুর সংখ্যক পরিবর্তনশীল থাকতে পারে-প্রতিটি সম্ভাব্য বিন্যাসের জন্য একটি পরিবর্তনশীল। দ্বৈত এল. পি ভগ্নাংশ এল. পি-র দ্বৈত রৈখিক প্রোগ্রামটি হ 'লঃ এটির এম ভেরিয়েবল এবং সি সীমাবদ্ধতা রয়েছে-প্রতিটি কনফিগারেশনের জন্য একটি সীমাবদ্ধতা। এর নিম্নলিখিত অর্থনৈতিক ব্যাখ্যা রয়েছে। প্রতিটি আকারের জন্য, আমাদের একটি অ-ঋণাত্মক মূল্য নির্ধারণ করা উচিত। আমাদের মুনাফা হল সমস্ত জিনিসের মোট মূল্য। প্রতিটি বিন্যাসে পণ্যের মোট মূল্য সর্বাধিক 1 টাকা হওয়া সীমাবদ্ধতার সাপেক্ষে আমরা মুনাফা সর্বাধিক করতে চাই। এই এলপিতে এখন কেবল এম ভেরিয়েবল রয়েছে, তবে বিপুল সংখ্যক সীমাবদ্ধতা রয়েছে। এমনকি সমস্ত সীমাবদ্ধতার তালিকাও অসম্ভব। সৌভাগ্যবশত, উপবৃত্তাকার পদ্ধতির একটি বৈকল্পিক ব্যবহার করে সমস্ত সীমাবদ্ধতার তালিকা না করে যে কোনও নির্দিষ্ট নির্ভুলতা পর্যন্ত সমস্যাটি সমাধান করা সম্ভব। এই ভ্যারিয়েন্টটি ইনপুট হিসাবে পাওয়া যায়, একটি পৃথকীকরণ ওরাকলঃ একটি ফাংশন যা একটি ভেক্টর y ≤ 0 দেওয়া হয়, নিম্নলিখিত দুটি বিকল্পের মধ্যে একটি প্রদান করেঃ জোর দিয়ে বলুন যে y সম্ভবপর, অর্থাৎ, বা-জোর দিয়ে বলুন যে y অসম্ভব, এবং একটি নির্দিষ্ট সীমাবদ্ধতা প্রদান করে যা লঙ্ঘন করা হয়েছে, অর্থাৎ, একটি ভেক্টর a যেমন। উপবৃত্তাকার পদ্ধতিটি একটি বড় উপবৃত্তাকার দিয়ে শুরু হয়, যার মধ্যে সম্পূর্ণ সম্ভাব্য ক্ষেত্র রয়েছে। প্রতিটি ধাপ টি-তে, এটি বর্তমান উপবৃত্তাকারের কেন্দ্রটি নেয় এবং এটিকে পৃথকীকরণ ওরাকলে পাঠায়ঃ যদি ওরাকল বলে যে এটি সম্ভব, তবে আমরা একটি "অনুকূলতা কাট" করিঃ আমরা উপবৃত্তাকার থেকে সমস্ত পয়েন্ট y কেটে ফেলি যার জন্য। এই পয়েন্টগুলি অবশ্যই সর্বোত্তম নয়। যদি ওরাকল বলে যে এটি অসম্ভব এবং সীমাবদ্ধতা a লঙ্ঘন করে, তবে আমরা একটি "সম্ভাব্যতা কাট" করিঃ আমরা উপবৃত্তাকার থেকে সমস্ত পয়েন্ট y কেটে ফেলি যার জন্য। এই পয়েন্টগুলি অবশ্যই সম্ভব নয়। একটি কাটা করার পরে, আমরা একটি নতুন, ছোট উপবৃত্তাকার তৈরি করি। এটি দেখানো যেতে পারে যে এই প্রক্রিয়াটি একটি আনুমানিক সমাধানে একত্রিত হয়, সময় পলিনোমিয়ালে প্রয়োজনীয় নির্ভুলতায়। দ্বৈত এল. পি-র জন্য একটি পৃথকীকরণ ওরাকল আমাদের কিছু অ-ঋণাত্মক সংখ্যা দেওয়া হয়েছে। আমাদের নিম্নলিখিত দুটি বিকল্পের মধ্যে সিদ্ধান্ত নিতে হবেঃ প্রতিটি সম্ভাব্য বিন্যাসের জন্য, এই বিন্যাসের সাথে সম্পর্কিত যোগফল সর্বাধিক 1; এর অর্থ হল যে y সম্ভবপর। একটি সম্ভাব্য বিন্যাস রয়েছে যার জন্য যোগফল 1-এর চেয়ে বড়; এর অর্থ হল যে y অসম্ভব। এই ক্ষেত্রে, আমাদের কনফিগারেশনটিও ফেরত দিতে হবে। এই সমস্যাটি একটি ন্যাপস্যাক সমস্যা সমাধানের মাধ্যমে সমাধান করা যেতে পারে, যেখানে আইটেমের মান, আইটেমের ওজন এবং ওজনের ক্ষমতা বি (বিন আকার)। যদি সর্বোত্তম ন্যাপস্যাক সমাধানের মোট মান সর্বাধিক 1 হয়, তবে আমরা বলি যে y সম্ভবপর। যদি সর্বোত্তম ন্যাপস্যাক সমাধানের মোট মান 1 এর চেয়ে বড় হয়, তবে আমরা বলি যে y অসম্ভব, এবং সর্বোত্তম ন্যাপস্যাক সমাধানের আইটেমগুলি এমন একটি কনফিগারেশনের সাথে মিলে যায় যা একটি সীমাবদ্ধতা লঙ্ঘন করে (যেহেতু ভেক্টরের জন্য a যা এই কনফিগারেশনের সাথে মিলে যায়)। ন্যাপস্যাক সমস্যাটি ছদ্ম-বহুপদী সময়ে গতিশীল প্রোগ্রামিং দ্বারা সমাধান করা যেতে পারেঃ, যেখানে m হল ইনপুটের সংখ্যা এবং V হল বিভিন্ন সম্ভাব্য মানের সংখ্যা। একটি পলিনোমিয়াল-টাইম অ্যালগরিদম পেতে, আমরা ইনপুট রাউন্ডিং ব্যবহার করে প্রায় ন্যাপস্যাক সমস্যাটি সমাধান করতে পারি। ধরুন, আমরা সহনশীলতার সঙ্গে একটি সমাধান চাই। আমরা প্রত্যেকটিকে/n এর নিকটতম গুণিতক পর্যন্ত বৃত্তাকার করতে পারি। তারপর, 0 এবং 1 এর মধ্যে সম্ভাব্য মানগুলির সংখ্যা হল n/, এবং রান-টাইম হল। সমাধানটি অন্তত সর্বোত্তম সমাধান বিয়োগ/এন। একটি আনুমানিক পৃথকীকরণ ওরাকল সহ উপবৃত্তাকার পদ্ধতি উপবৃত্তাকার পদ্ধতিটি একটি আনুমানিক পৃথকীকরণ ওরাকল ব্যবহার করার জন্য অভিযোজিত করা উচিত। বর্তমান উপবৃত্তাকার কেন্দ্রের পরিপ্রেক্ষিতেঃ যদি আনুমানিক ওরাকল 1-এর চেয়ে বড় মান সহ একটি সমাধান প্রদান করে, তবে তা অবশ্যই অসম্ভব, এবং সমাধানটি এমন একটি বিন্যাসের সাথে সামঞ্জস্যপূর্ণ যা একটি সীমাবদ্ধতা a লঙ্ঘন করে। আমরা একটি "সম্ভাব্যতা কাট" করি, যার জন্য উপবৃত্তাকার সমস্ত পয়েন্ট y কাটা হয়। যদি আনুমানিক ওরাকল সর্বাধিক 1 মান সহ একটি সমাধান প্রদান করে, তবে এটি সম্ভব বা নাও হতে পারে, তবে বৃত্তাকার করা (দ্বারা বোঝানো) সম্ভব। বৃত্তাকারের সংজ্ঞা অনুসারে, আমরা তা জানি। আমরা এখনও একটি "অপ্টিমালিটি কাট" করিঃ আমরা উপবৃত্তাকার থেকে সমস্ত পয়েন্ট y কেটে ফেলি যার জন্য। মনে রাখবেন যে এটি অসম্ভব হতে পারে, তাই এর মান ওপিটি-র চেয়ে বেশি হতে পারে। অতএব, আমরা এমন কিছু পয়েন্ট সরিয়ে ফেলতে পারি যার উদ্দেশ্য সর্বোত্তম। যাইহোক, সরানো পয়েন্টগুলি সন্তুষ্ট করে; কোনও পয়েন্ট সরানো হয় না যদি এর মান এর চেয়ে বেশি হয়। আনুমানিক পৃথকীকরণ ওরাকল ব্যবহার করে দ্বৈত এলপি-র একটি সম্ভাব্য সমাধান y * পাওয়া যায়, যেখানে, সর্বাধিক পুনরাবৃত্তির পরে, যেখানে। আনুমানিক পৃথকীকরণ ওরাকল সহ উপবৃত্তাকার পদ্ধতির মোট রান-টাইম হল। সীমাবদ্ধতাগুলি দূর করা উপবৃত্তাকার পদ্ধতির সময়, আমরা ফর্মের সর্বাধিক Q সীমাবদ্ধতাগুলি ব্যবহার করি। অন্যান্য সমস্ত সীমাবদ্ধতা দূর করা যেতে পারে, কারণ উপবৃত্তাকার পদ্ধতির ফলাফল y *-এর উপর তাদের কোনও প্রভাব নেই। আমরা আরও বেশি সীমাবদ্ধতা দূর করতে পারি। এটি জানা যায় যে, m ভেরিয়েবল সহ যে কোনও LP-তে, m সীমাবদ্ধতার একটি সেট রয়েছে যা সর্বোত্তম সমাধান নির্ধারণের জন্য যথেষ্ট (অর্থাৎ, সর্বোত্তম মান একই, এমনকি যদি শুধুমাত্র এই m সীমাবদ্ধতাগুলি ব্যবহার করা হয়)। আমরা বারবার উপরের মতো উপবৃত্তাকার পদ্ধতি চালাতে পারি, প্রতিবার সীমাবদ্ধতার একটি নির্দিষ্ট সেট অপসারণের চেষ্টা করি। যদি ফলস্বরূপ ত্রুটি সর্বাধিক হয়, তবে আমরা এই সীমাবদ্ধতাগুলি স্থায়ীভাবে সরিয়ে ফেলি। এটি দেখানো যেতে পারে যে আমাদের সর্বাধিক অপসারণের প্রয়োজন, তাই সঞ্চয়ের ত্রুটি সর্বাধিক। যদি আমরা নির্ধারিতভাবে সীমাবদ্ধতার সেটগুলি চেষ্টা করি, তবে সবচেয়ে খারাপ ক্ষেত্রে, এম ট্রায়ালগুলির মধ্যে একটি সফল হয়, তাই আমাদের বেশিরভাগ সময় উপবৃত্তাকার পদ্ধতিটি চালাতে হবে। যদি আমরা এলোমেলোভাবে অপসারণের জন্য সীমাবদ্ধতাগুলি বেছে নিই, তবে প্রত্যাশিত পুনরাবৃত্তির সংখ্যা হল। পরিশেষে, আমাদের একটি হ্রাসকৃত দ্বৈত এল. পি রয়েছে, যার মধ্যে কেবল এম ভেরিয়েবল এবং এম সীমাবদ্ধতা রয়েছে। হ্রাসকৃত এলপির সর্বোত্তম মান অন্তত কোথায়। প্রাথমিক এল. পি সমাধান করা এল. পি দ্বৈততা উপপাদ্য দ্বারা, প্রাথমিক এল. পি-র ন্যূনতম মান দ্বৈত এল. পি-র সর্বোচ্চ মানের সমান, যা আমরা এল. ও. পি. টি দ্বারা চিহ্নিত করি। একবার আমাদের একটি হ্রাসকৃত দ্বৈত এলপি হয়ে গেলে, আমরা তার দ্বৈতটি গ্রহণ করি এবং একটি হ্রাসকৃত প্রাথমিক এলপি গ্রহণ করি। এই এলপিতে শুধুমাত্র এম ভেরিয়েবল রয়েছে-সি কনফিগারেশনের মধ্যে শুধুমাত্র এম এর সাথে সামঞ্জস্যপূর্ণ। হ্রাসকৃত দ্বৈত এলপি-র সর্বোচ্চ মান কমপক্ষে। এটি দেখানো যেতে পারে যে হ্রাসকৃত প্রাথমিক এলপি-র সর্বোত্তম সমাধান হল সর্বাধিক। সমাধানটি সর্বাধিক মিটার কনফিগারেশন ব্যবহার করে একটি প্রায়-সর্বোত্তম বিন প্যাকিং দেয়। নির্ধারণমূলক অ্যালগরিদমের মোট রান-টাইম, যখন সমস্ত আইটেমগুলি এর চেয়ে বড় হয়, তা হলঃ, র্যান্ডমাইজড অ্যালগরিদমের প্রত্যাশিত মোট রান-টাইম হলঃ এন্ড-টু-এন্ড অ্যালগরিদম কর্মকার এবং কার্প তিনটি অ্যালগরিদম উপস্থাপন করেছেন, যা বিভিন্ন পরামিতি সহ উপরের কৌশলগুলি ব্যবহার করে। এই সমস্ত অ্যালগরিদমের রান-টাইম একটি ফাংশনের উপর নির্ভর করে, যা একটি বহুপদী ফাংশন যা সহনশীলতা এইচ = 1 সহ ভগ্নাংশ এলপি সমাধান করতে যে সময় নেয় তা বর্ণনা করে, যা নির্ধারণমূলক সংস্করণের জন্য। অ্যালগরিদম 1 একটি ধ্রুবক হতে দিন যা কাঙ্ক্ষিত আনুমানিক নির্ভুলতার প্রতিনিধিত্ব করে। 1-এ। সেট করুন। ধরা যাক জি. 2-এ-এর চেয়ে ছোট সমস্ত আইটেম সরিয়ে একটি উদাহরণ তৈরি করা হয়েছে। সেট করুন। ধরা যাক k প্যারামিটারের সাথে রৈখিক গ্রুপিং দ্বারা নির্মিত একটি উদাহরণ, এবং অবশিষ্ট উদাহরণ (k বৃহত্তম আইটেমের গ্রুপ) হতে দিন। এটা মনে রাখবেন। 3-এ। অবিচ্ছেদ্যতার সীমাবদ্ধতা ছাড়াই কনফিগারেশন রৈখিক প্রোগ্রামটি তৈরি করুন। 4. x-এর জন্য একটি সমাধান গণনা করুন, যার জন্য সহনশীলতা h = 1। ফলস্বরূপ একটি ভগ্নাংশ বিন বিন দিয়ে প্যাক করা হয়। রান-টাইম হল। 3-বি। জন্য একটি অবিচ্ছেদ্য সমাধানের জন্য x বৃত্তাকার করুন। ভগ্নাংশ অংশের জন্য বেশিরভাগ বিন যোগ করুন। মোট বিনের সংখ্যা হল। 2-বি। সর্বাধিক কে বিনে ব্যবহার করে জিনিসগুলি প্যাক করুন; একটি প্যাকিং নিন। বিনের সংখ্যা হল। 1-বি। সমাধান পেতে জি-এর চেয়ে ছোট জিনিসগুলি যোগ করুন। বাক্সের সংখ্যা হলঃ সব মিলিয়ে, বিনগুলির সংখ্যা রয়েছে এবং রান-টাইম রয়েছে। বেছে নেওয়ার মাধ্যমে আমরা পাই। অ্যালগরিদম 2 ধরা যাক একটি বাস্তব পরামিতি এবং একটি পূর্ণসংখ্যা পরামিতি যা পরে নির্ধারণ করা হবে। 1-এ। ধরা যাক একটি উদাহরণ যা জি. 2-এর চেয়ে ছোট সমস্ত আইটেম অপসারণ করে তৈরি করা হয়েছে। যখন করবেনঃ 2-এ। k প্যারামিটার সহ বিকল্প জ্যামিতিক গ্রুপিং করুন। ফলাফলের উদাহরণ হতে দিন, এবং অবশিষ্ট উদাহরণ হতে দিন। আমাদের আছে। 3-এ। অবিচ্ছেদ্যতার সীমাবদ্ধতা ছাড়াই কনফিগারেশন রৈখিক প্রোগ্রামটি তৈরি করুন। 4. x-এর জন্য একটি সমাধান গণনা করুন, যার জন্য সহনশীলতা h = 1। ফলস্বরূপ একটি ভগ্নাংশ বিন বিন দিয়ে প্যাক করা হয়। রান-টাইম হল। 3-বি। জন্য একটি অবিচ্ছেদ্য সমাধানের জন্য x বৃত্তাকার করুন। ভগ্নাংশ অংশের জন্য বিন যোগ করবেন না। পরিবর্তে, প্যাকেটজাত জিনিসগুলি সরিয়ে ফেলুন। 2-বি। বেশিরভাগ পাত্রে জিনিসপত্র গুছিয়ে রাখুন। 2. একবার, অবশিষ্ট জিনিসগুলি বেশিরভাগ পাত্রে লোভের সাথে প্যাক করুন। ধাপ 2-এ লুপের প্রতিটি পুনরাবৃত্তিতে, x-এর ভগ্নাংশ অংশে সর্বাধিক m (K) প্যাটার্ন থাকে। প্রতিটি পুনরাবৃত্তিতে এফওপিটি কে-এর একটি গুণক দ্বারা হ্রাস পায়, তাই পুনরাবৃত্তির সংখ্যা সর্বাধিক। অতএব, এর জন্য ব্যবহৃত মোট বাক্সের সংখ্যা হলঃ 1-বি। সমাধান পেতে জি-এর চেয়ে ছোট জিনিসগুলি যোগ করুন। বাক্সের সংখ্যা হলঃ রান-টাইম চলে এসেছে। এখন, যদি আমরা k = 2 এবং g = 1/FOPT (I) বেছে নিই, আমরা পাইঃ, এবং তাইঃ, তাই মোট বিন সংখ্যা রয়েছে। রান-টাইম হল। সঠিকতার সাথে রান-টাইম বিনিময় করতে একই অ্যালগরিদম বিভিন্ন পরামিতিগুলির সাথে ব্যবহার করা যেতে পারে। কিছু প্যারামিটারের জন্য, এবং নির্বাচন করুন। তারপর, প্যাকিংয়ের জন্য বেশিরভাগ ডাস্টবিনে প্রয়োজন হয় এবং রান-টাইম শেষ হয়ে যায়। অ্যালগরিদম 3 তৃতীয় অ্যালগরিদমটি কার্যকর হয় যখন মাপের সংখ্যা m ছোট হয় (উচ্চ-গুণমান বিন প্যাকিংও দেখুন)। 1-এ। সেট করুন। ধরা যাক জি-এর চেয়ে ছোট সমস্ত আইটেম সরিয়ে একটি উদাহরণ তৈরি করা হয়েছে। যদি তা হয়ঃ 3-এ। অবিচ্ছেদ্যতার সীমাবদ্ধতা ছাড়াই কনফিগারেশন রৈখিক প্রোগ্রামটি তৈরি করুন। 4. x-এর জন্য একটি সমাধান গণনা করুন, যার জন্য সহনশীলতা h = 1। ফলস্বরূপ একটি ভগ্নাংশ বিন বিন দিয়ে প্যাক করা হয়। রান-টাইম হল। 3-বি। জন্য একটি অবিচ্ছেদ্য সমাধানের জন্য x বৃত্তাকার করুন। ভগ্নাংশ অংশের জন্য বিন যোগ করবেন না। পরিবর্তে, প্যাকেটজাত জিনিসগুলি সরিয়ে ফেলুন। অবশিষ্ট অংশে অ্যালগরিদম 2-এর 2য় ধাপটি চালান। 1-বি। সমাধান পেতে জি-এর চেয়ে ছোট জিনিসগুলি যোগ করুন। বাক্সের সংখ্যা হলঃ এটি বেশিরভাগ বিনে ব্যবহার করে এবং রান-টাইম থাকে। উন্নতি কেকে কৌশলগুলি পরে আরও উন্নত করা হয়েছিল, যাতে আরও ভাল অনুমান প্রদান করা যায়। রথভোস অ্যালগরিদম 2-এর মতো একই স্কিম ব্যবহার করে, তবে দ্বিতীয় ধাপে একটি ভিন্ন বৃত্তাকার পদ্ধতি ব্যবহার করে। তিনি একটি "আঠালো" পদক্ষেপ চালু করেছিলেন, যেখানে ছোট জিনিসগুলি একসঙ্গে আঠালো করা হয় যাতে একটি বড় জিনিস পাওয়া যায়। এই আঠালো ব্যবহার করে ক্ষুদ্রতম আইটেমের আকার প্রায় বৃদ্ধি করা যেতে পারে। যখন সমস্ত আকার কমপক্ষে হয়, তখন আমরা অ্যালগরিদম 2-এর গ্যারান্টিতে প্রতিস্থাপন করতে পারি এবং পেতে পারিঃ, যা একটি বিন উৎপন্ন করে। হোবারগ এবং রথভোস একটি অনুরূপ পদ্ধতি ব্যবহার করেন যেখানে জিনিসগুলি প্রথমে "পাত্রে" প্যাক করা হয় এবং তারপরে পাত্রে প্যাক করা হয়। তাদের অ্যালগরিদমের বেশিরভাগ বিন প্রয়োজন। রেফারেন্স বিন প্যাকিং