Configuration linear program
কনফিগারেশন লিনিয়ার প্রোগ্রাম (কনফিগারেশন-এল. পি) একটি লিনিয়ার প্রোগ্রামিং কৌশল যা কম্বিনেটোরিয়াল অপ্টিমাইজেশান সমস্যা সমাধানের জন্য ব্যবহৃত হয়। কাটিং স্টক সমস্যার প্রেক্ষাপটে এটি চালু করা হয়েছিল। পরে, এটি বিন প্যাকিং এবং কাজের সময়সূচী সংক্রান্ত সমস্যার ক্ষেত্রে প্রয়োগ করা হয়েছে। কনফিগারেশন-এলপিতে, প্রতিটি সম্ভাব্য কনফিগারেশনের জন্য একটি পরিবর্তনশীল রয়েছে-প্রতিটি সম্ভাব্য মাল্টিসেট আইটেম যা একটি একক বিন-এ ফিট করতে পারে (এই কনফিগারেশনগুলি প্যাটার্ন হিসাবেও পরিচিত)। সাধারণত, সমস্যার আকারে বিন্যাসের সংখ্যা সূচকীয় হয়, তবে কিছু ক্ষেত্রে শুধুমাত্র একটি বহুপদী সংখ্যা ব্যবহার করে আনুমানিক সমাধান অর্জন করা সম্ভব। বিন প্যাকিং-এ ইন্টিগ্রাল এল. পি. বিন প্যাকিং সমস্যায়, বিভিন্ন আকারের এন আইটেম রয়েছে। লক্ষ্য হল জিনিসগুলিকে ন্যূনতম সংখ্যক বিনে প্যাক করা, যেখানে প্রতিটি বি-তে সর্বাধিক বি থাকতে পারে। একটি সম্ভাব্য বিন্যাস হল মাপের একটি সেট যার যোগফল সর্বাধিক বি। উদাহরণস্বরূপঃ ধরুন আইটেমের মাপ 3,3,3,3,3,4,4,4,4,4, এবং B = 12। তারপর সম্ভাব্য বিন্যাসগুলি হলঃ 3333; 333; 33,334; 3,34,344; 4,44,444। যদি আমাদের কাছে 3 আকারের মাত্র তিনটি আইটেম থাকত, তাহলে আমরা 3333 কনফিগারেশনটি ব্যবহার করতে পারতাম না। বিভিন্ন মাপের সেট (এবং তাদের সংখ্যা) এস দ্বারা চিহ্নিত করুন। বিভিন্ন বিন্যাসের সেটকে (এবং তাদের সংখ্যা) সি দ্বারা চিহ্নিত করুন। প্রতিটি আকারের জন্য এস-এ এস এবং সি-তে সি কনফিগারেশনের জন্য, নির্দেশ করুনঃ এনএস-আকারের আইটেমগুলির সংখ্যা এস হিসাবে, সি-কনফিগারেশনে এস আকারের ঘটনার সংখ্যা সি এক্সসি-কনফিগারেশন সি সহ বিনগুলির সংখ্যা নির্দেশ করে একটি পরিবর্তনশীল। তারপর, বিন-প্যাকিংয়ের কনফিগারেশন এলপি হ 'লঃ এস-এ সমস্ত এস-এর জন্য (-আকারের সমস্ত এনএস আইটেমগুলি প্যাক করা হয়)। সি-তে সমস্ত সি-এর জন্য (-সামগ্রিকভাবে সর্বাধিক এন বিন রয়েছে, তাই প্রতিটি পৃথক কনফিগারেশনের সর্বাধিক এন)। কনফিগারেশন এল. পি একটি পূর্ণসংখ্যা রৈখিক প্রোগ্রাম, তাই সাধারণভাবে এটি এন. পি-হার্ড। উপরন্তু, এমনকি সমস্যাটি নিজেই সাধারণত খুব বড়ঃ এতে সি ভেরিয়েবল এবং এস সীমাবদ্ধতা রয়েছে। যদি ক্ষুদ্রতম আইটেমের আকার eB হয় (কিছু ভগ্নাংশ e-এর জন্য (0,1)), তাহলে প্রতিটি বিন-এ 1/e পর্যন্ত আইটেম থাকতে পারে, তাই কনফিগারেশনের সংখ্যা C ~ S1/e, যা খুব বড় হতে পারে যদি e ছোট হয় (যদি e-কে ধ্রুবক হিসাবে বিবেচনা করা হয়, তবে পূর্ণসংখ্যা LP সম্পূর্ণ অনুসন্ধানের মাধ্যমে সমাধান করা যেতে পারেঃ সর্বাধিক S1/E কনফিগারেশন রয়েছে এবং প্রতিটি কনফিগারেশনের জন্য সর্বাধিক n সম্ভাব্য মান রয়েছে, তাই পরীক্ষা করার জন্য সর্বাধিক সংমিশ্রণ রয়েছে। প্রতিটি সংমিশ্রণের জন্য, আমাদের S সীমাবদ্ধতাগুলি পরীক্ষা করতে হবে, তাই রান-টাইম হল, যা n-এ বহুপদী যখন S, e ধ্রুবক হয়)। তবে, এই আইএলপি বেশ কয়েকটি আনুমানিক অ্যালগরিদমের ভিত্তি হিসাবে কাজ করে। এই অ্যালগরিদমগুলির মূল ধারণা হল মূল দৃষ্টান্তটিকে একটি নতুন উদাহরণে হ্রাস করা যেখানে এস ছোট এবং ই বড়, তাই সি তুলনামূলকভাবে ছোট। তারপর, আইএলপি সম্পূর্ণ অনুসন্ধানের মাধ্যমে সমাধান করা যেতে পারে (যদি এস, সি যথেষ্ট ছোট হয়), অথবা একটি ভগ্নাংশ এলপিতে শিথিল করে। ভগ্নাংশ এলপি বিন-প্যাকিংয়ের ভগ্নাংশ কনফিগারেশন এলপি এটি উপরের আইএলপি-র রৈখিক প্রোগ্রামিং শিথিলকরণ। এটি শেষ সীমাবদ্ধতাকে সীমাবদ্ধতার সাথে প্রতিস্থাপন করে। অন্য কথায়, প্রতিটি বিন্যাস ভগ্নাংশ সংখ্যক বার ব্যবহার করা যেতে পারে। শিথিলকরণ প্রথম গিলমোর এবং গোমোরি দ্বারা উপস্থাপিত হয়েছিল এবং এটিকে প্রায়শই গিলমোর-গোমোরি রৈখিক প্রোগ্রাম বলা হয়। উদাহরণস্বরূপঃ ধরুন 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 বিন রয়েছে। মনে রাখবেন যে শুধুমাত্র দুটি ভিন্ন বিন্যাসের প্রয়োজন। সংক্ষেপে, ভগ্নাংশ এলপি নিম্নরূপ লেখা যেতে পারেঃ যেখানে 1 হল সি আকারের ভেক্টর (1,, 1), এ হল একটি এস-বাই-সি ম্যাট্রিক্স যেখানে প্রতিটি কলাম একটি একক বিন্যাসের প্রতিনিধিত্ব করে এবং এন হল ভেক্টর (এন1,, এনএস)। ভগ্নাংশ এল. পি. সমাধান করা কোনও অবিচ্ছেদ্য সীমাবদ্ধতা ছাড়াই একটি রৈখিক প্রোগ্রামকে পরিবর্তনশীল এবং সীমাবদ্ধতার সংখ্যার সময় বহুপদীতে সমাধান করা যেতে পারে। সমস্যাটি হল যে ভগ্নাংশ বিন্যাস এল. পি-তে চলকের সংখ্যা সম্ভাব্য বিন্যাসের সংখ্যার সমান, যা বিশাল হতে পারে। কর্মকার এবং কার্প একটি অ্যালগরিদম উপস্থাপন করেছেন যা এই সমস্যাটি অতিক্রম করে। প্রথমত, তারা ভগ্নাংশ এলপি-র দ্বৈত রৈখিক প্রোগ্রাম তৈরি করেঃ। এর এস ভেরিয়েবল y1,., yS, এবং C সীমাবদ্ধতা রয়েছেঃ প্রতিটি কনফিগারেশন c-এর জন্য, একটি সীমাবদ্ধতা রয়েছে, যেখানে এ-এর কলামটি কনফিগারেশন c-এর প্রতিনিধিত্ব করে। 3 এর নিম্নলিখিত অর্থনৈতিক ব্যাখ্যা রয়েছে। প্রতিটি আকারের জন্য, আমাদের একটি অ-ঋণাত্মক মূল্য নির্ধারণ করা উচিত। আমাদের মুনাফা হল সমস্ত জিনিসের মোট মূল্য। প্রতিটি বিন্যাসে পণ্যের মোট মূল্য সর্বাধিক 1 টাকা হওয়া সীমাবদ্ধতার সাপেক্ষে আমরা মুনাফা সর্বাধিক করতে চাই। দ্বিতীয়ত, তারা উপবৃত্তাকার পদ্ধতির একটি বৈকল্পিক প্রয়োগ করে, যার জন্য সমস্ত সীমাবদ্ধতার তালিকা করার প্রয়োজন হয় না-এটির জন্য কেবল একটি পৃথকীকরণ ওরাকল প্রয়োজন। একটি পৃথকীকরণ ওরাকল হল একটি অ্যালগরিদম যা একটি ভেক্টর y দেওয়া হলে, হয় এটি সম্ভব বলে দাবি করে, অথবা এটি লঙ্ঘন করে এমন একটি সীমাবদ্ধতা খুঁজে পায়। দ্বৈত এলপির জন্য পৃথকীকরণ ওরাকলটি মাপ s এবং মান y দিয়ে ন্যাপস্যাক সমস্যা সমাধানের মাধ্যমে প্রয়োগ করা যেতে পারেঃ যদি ন্যাপস্যাক সমস্যার সর্বোত্তম সমাধানের মোট মান সর্বাধিক 1 হয়, তবে y সম্ভব; যদি এটি 1 এর চেয়ে বড় হয়, y এর চেয়ে বেশি সম্ভব নয়, এবং ন্যাপস্যাক সমস্যার সর্বোত্তম সমাধান এমন একটি কনফিগারেশন চিহ্নিত করে যার জন্য সীমাবদ্ধতা লঙ্ঘন করা হয়েছে। তৃতীয়ত, তারা দেখায় যে, ন্যাপস্যাক সমস্যার আনুমানিক সমাধানের মাধ্যমে, কেউ দ্বৈত এলপি-র আনুমানিক সমাধান পেতে পারে এবং এটি থেকে, প্রাথমিক এলপি-র আনুমানিক সমাধান; কর্মকার-কার্প বিন প্যাকিং অ্যালগরিদম দেখুন। সব মিলিয়ে, যে কোনও সহনশীলতা ফ্যাক্টর এইচ-এর জন্য, সর্বাধিক এলওপিটি (আই) + এইচ-এ ব্যয়ের একটি মৌলিক সম্ভাব্য সমাধান খুঁজে পায় এবং সময়মতো চলেঃ, যেখানে এস হল বিভিন্ন আকারের সংখ্যা, এন হল বিভিন্ন আইটেমের সংখ্যা, এবং ক্ষুদ্রতম আইটেমের আকার হল ইবি। বিশেষত, যদি e ±1/n এবং h = 1 হয়, তবে অ্যালগরিদমটি সর্বাধিক LOPT + 1 বিন সহ একটি সমাধান খুঁজে পাবেঃ এই অ্যালগরিদমের একটি এলোমেলো রূপ প্রত্যাশিত সময়ে চলেঃ ভগ্নাংশ এল. পি.-কে বৃত্তাকার করে কর্মকার এবং কার্প ভগ্নাংশ এল. পি-কে অবিচ্ছেদ্য এল. পি-র আনুমানিক সমাধানে বৃত্তাকার করার একটি উপায় তৈরি করেছেন; কর্মকার-কার্প বিন প্যাকিং অ্যালগরিদম দেখুন। তাদের প্রমাণ দেখায় যে এই এল. পি-র যোগাত্মক অখণ্ডতার ব্যবধান ও (লগ 2 (এন))-তে রয়েছে। পরে, হোবারগ এবং রথভোস তাদের ফলাফলের উন্নতি করেন এবং প্রমাণ করেন যে অখণ্ডতার ব্যবধানটি ও (লগ (এন))-তে রয়েছে। অবিচ্ছেদ্য ব্যবধানের সবচেয়ে পরিচিত নিম্ন সীমা হল একটি ধ্রুবক ω (1)। সঠিক অখণ্ডতার ব্যবধান খুঁজে বের করা একটি উন্মুক্ত সমস্যা। বিন আচ্ছাদনে বিন আচ্ছাদন সমস্যায়, বিভিন্ন আকারের এন আইটেম রয়েছে। লক্ষ্য হল জিনিসগুলিকে সর্বাধিক সংখ্যক বিন-এ প্যাক করা, যেখানে প্রতিটি বিন-এ কমপক্ষে বি থাকা উচিত। এই সমস্যার জন্য একটি স্বাভাবিক কনফিগারেশন এল. পি হতে পারেঃ যেখানে এ কমপক্ষে বি যোগফল সহ আইটেমগুলির সমস্ত কনফিগারেশনকে উপস্থাপন করে (কেউ শুধুমাত্র অন্তর্ভুক্তি-ন্যূনতম কনফিগারেশন নিতে পারে)। এই এল. পি-র সমস্যা হল, বিন-আচ্ছাদন সমস্যায়, ছোট জিনিসগুলি পরিচালনা করা সমস্যাযুক্ত, কারণ সর্বোত্তম সমাধানের জন্য ছোট জিনিসগুলি অপরিহার্য হতে পারে। ছোট জিনিসপত্রের অনুমতি থাকলে, এমনকি কর্মকার এবং কার্পের কৌশলের জন্যও বিন্যাসের সংখ্যা খুব বেশি হতে পারে। সিরিক, জনসন এবং কেনিয়ন একটি বিকল্প এলপি উপস্থাপন করেন। প্রথমত, তারা একগুচ্ছ বস্তুর সংজ্ঞা দেয় যাকে ছোট বলা হয়। ধরা যাক টি সমস্ত ছোট আইটেমের মোট আকার। তারপর, তারা যোগফল <2 সহ সমস্ত বিন্যাসের প্রতিনিধিত্বকারী একটি ম্যাট্রিক্স এ তৈরি করে। তারপরে, তারা উপরের এল. পি-কে একটি অতিরিক্ত সীমাবদ্ধতা সহ বিবেচনা করেঃ অতিরিক্ত সীমাবদ্ধতা নিশ্চিত করে যে ছোট জিনিসগুলি দ্বারা ডাবের "খালি জায়গা" পূরণ করা যেতে পারে। এই এলপির দ্বৈত আরও জটিল এবং একটি সাধারণ ন্যাপস্যাক-সমস্যা পৃথকীকরণ ওরাকল দ্বারা সমাধান করা যায় না। সিরিক, জনসন এবং কেনিয়ন প্রায় 1/এপসিলোনে সময় সূচকীয়ভাবে এটি সমাধান করার জন্য একটি ভিন্ন পদ্ধতি উপস্থাপন করেছেন। জ্যানসেন এবং সোলিস-ওবা 1/এপসিলোনে আনুমানিক সময়ের সূচকীয়তায় এটি সমাধান করার জন্য একটি উন্নত পদ্ধতি উপস্থাপন করেছেন। মেশিনের সময়সূচীতে সম্পর্কহীন-মেশিনের সময়সূচীর সমস্যায়, কিছু ভিন্ন মেশিন রয়েছে যা কিছু ভিন্ন কাজ প্রক্রিয়া করা উচিত। যখন মেশিন আই কাজ জে প্রক্রিয়া করে, তখন পাই, জে সময় নেয়। লক্ষ্য হল যন্ত্রগুলির মধ্যে কাজগুলি এমনভাবে ভাগ করা যাতে একটি যন্ত্রের সর্বাধিক সমাপ্তির সময় যতটা সম্ভব কম হয়। এই সমস্যার সিদ্ধান্ত সংস্করণটি হ 'লঃ সময় টি দেওয়া, এমন কোনও পার্টিশন আছে যেখানে সমস্ত মেশিনের সমাপ্তির সময় সর্বাধিক টি হয়? প্রতিটি মেশিন i-এর জন্য, কাজের অনেকগুলি উপসেট রয়েছে যা মেশিন i দ্বারা সর্বাধিক T সময়ে প্রক্রিয়া করা যেতে পারে। এই ধরনের প্রতিটি উপসেটকে মেশিনের জন্য একটি কনফিগারেশন বলা হয় i। Ci (T) দ্বারা চিহ্নিত করুন মেশিন i-এর জন্য সমস্ত কনফিগারেশনের সেট, প্রদত্ত সময় T। প্রতিটি মেশিন i এবং কনফিগারেশন c-এর জন্য Ci (T)-এ, একটি পরিবর্তনশীল সংজ্ঞায়িত করুন যা 1-এর সমান হয় যদি মেশিনে ব্যবহৃত প্রকৃত কনফিগারেশন i হল c, এবং অন্যথায় 0। তারপর, এল. পি-র সীমাবদ্ধতাগুলি হলঃ প্রতিটি মেশিনের জন্য i ইন 1,., m; প্রতিটি কাজের জন্য j ইন 1,., n; প্রতিটি i, j-এর জন্য। বৈশিষ্ট্য অসংলগ্ন-যন্ত্রের সময়সূচীর জন্য কনফিগারেশন-এলপির অবিচ্ছেদ্য ব্যবধান হল 2। আরও দেখুন হাই-মাল্টিপ্লিসিটি বিন প্যাকিং রেফারেন্স বিন প্যাকিং নম্বর পার্টিশনিং জব সিডিউলিং লিনিয়ার প্রোগ্রামিং