LP-type problem
অ্যালগরিদম অধ্যয়নে, একটি এল. পি-টাইপ সমস্যা (যাকে সাধারণীকৃত রৈখিক প্রোগ্রামও বলা হয়) হল একটি অপ্টিমাইজেশন সমস্যা যা নিম্ন-মাত্রিক রৈখিক প্রোগ্রামগুলির সাথে নির্দিষ্ট বৈশিষ্ট্যগুলি ভাগ করে নেয় এবং যা অনুরূপ অ্যালগরিদম দ্বারা সমাধান করা যেতে পারে। এলপি-ধরনের সমস্যাগুলির মধ্যে রয়েছে অনেক গুরুত্বপূর্ণ অপ্টিমাইজেশান সমস্যা যা নিজে রৈখিক প্রোগ্রাম নয়, যেমন প্ল্যানার পয়েন্টগুলির একটি প্রদত্ত সেট ধারণকারী ক্ষুদ্রতম বৃত্তটি খুঁজে বের করার সমস্যা। এগুলি র্যান্ডমাইজড অ্যালগরিদমগুলির সংমিশ্রণ দ্বারা এমন একটি সময়ের মধ্যে সমাধান করা যেতে পারে যা সমস্যাটিকে সংজ্ঞায়িত করে এমন উপাদানগুলির সংখ্যায় রৈখিক এবং সমস্যার মাত্রায় সাবএক্সপোনেনশিয়াল। সংজ্ঞায়িত এলপি-ধরনের সমস্যাগুলি এমন সমস্যা হিসাবে সংজ্ঞায়িত করা হয়েছিল যেখানে একটিকে ইনপুট হিসাবে উপাদানগুলির একটি সীমাবদ্ধ সেট দেওয়া হয় এবং এমন একটি ফাংশন যা সম্পূর্ণরূপে সাজানো সেট থেকে মানগুলির উপসেটগুলিকে ম্যাপ করে। দুটি মূল বৈশিষ্ট্য পূরণ করার জন্য ফাংশনটির প্রয়োজন হয়ঃ একতানতাঃ প্রতি দুটি সেটের জন্য, f (A) ≤ f (B) ≤ f (S)। স্থানীয়তাঃ প্রতি দুটি সেট এবং প্রতিটি উপাদানের জন্য, যদি, তাহলে। একটি এল. পি-টাইপ সমস্যার একটি ভিত্তি হল এমন একটি সেট যার বৈশিষ্ট্য হল প্রতিটি সঠিক উপসেটের নিজের চেয়ে কম মান থাকে এবং একটি এল. পি-টাইপ সমস্যার মাত্রা (বা সমন্বিত মাত্রা) একটি ভিত্তির সর্বাধিক প্রধানতা হিসাবে সংজ্ঞায়িত করা হয়। এটি ধরে নেওয়া হয় যে একটি অপ্টিমাইজেশন অ্যালগরিদম শুধুমাত্র সেই সেটগুলিতে ফাংশনটির মূল্যায়ন করতে পারে যা নিজেরাই ভিত্তি বা একটি ভিত্তিতে একটি একক উপাদান যোগ করে গঠিত হয়। বিকল্পভাবে, অ্যালগরিদমটি দুটি আদিম ক্রিয়াকলাপের মধ্যে সীমাবদ্ধ থাকতে পারেঃ একটি লঙ্ঘন পরীক্ষা যা নির্ধারণ করে, একটি ভিত্তি এবং একটি উপাদানের জন্য, এবং একটি ভিত্তি গণনা যা (একই ইনপুট সহ) এর একটি ভিত্তি খুঁজে পায়। অ্যালগরিদমের কাজ হল শুধুমাত্র এই সীমাবদ্ধ মূল্যায়ন বা আদিম ব্যবহার করে মূল্যায়ন করা। উদাহরণ এবং প্রয়োগ একটি রৈখিক প্রোগ্রাম অ-নেতিবাচক বাস্তব চলকগুলির একটি সিস্টেম দ্বারা সংজ্ঞায়িত করা যেতে পারে, যা রৈখিক বৈষম্যের সীমাবদ্ধতার সাপেক্ষে, একটি অ-নেতিবাচক রৈখিক উদ্দেশ্যমূলক ফাংশন সহ ন্যূনতম করা যেতে পারে। সীমাবদ্ধতার সেট হিসাবে রেখে এবং (সীমাবদ্ধতার একটি উপসেটের জন্য) দ্বারা সংজ্ঞায়িত ছোট রৈখিক প্রোগ্রামের ন্যূনতম উদ্দেশ্যমূলক ফাংশন মান হিসাবে সংজ্ঞায়িত করে এটি এলপি-টাইপ সমস্যার কাঠামোর মধ্যে স্থাপন করা যেতে পারে। উপযুক্ত সাধারণ অবস্থান অনুমানের সাথে (একই সর্বোত্তম উদ্দেশ্যমূলক ফাংশন মান সহ একাধিক সমাধান পয়েন্ট প্রতিরোধ করার জন্য), এটি একটি এল. পি-টাইপ সমস্যার একঘেয়েমি এবং স্থানীয়তার প্রয়োজনীয়তা সন্তুষ্ট করে এবং ভেরিয়েবলের সংখ্যার সমান সমন্বিত মাত্রা রয়েছে। একইভাবে, একটি পূর্ণসংখ্যা প্রোগ্রাম (একটি রৈখিক প্রোগ্রামের মতো রৈখিক সীমাবদ্ধতার সংগ্রহ এবং একটি রৈখিক উদ্দেশ্যমূলক ফাংশন নিয়ে গঠিত, তবে অতিরিক্ত বিধিনিষেধের সাথে যে ভেরিয়েবলগুলিকে কেবলমাত্র পূর্ণসংখ্যার মানগুলি গ্রহণ করতে হবে) একটি এলপি-টাইপ সমস্যার একঘেয়েমি এবং স্থানীয় বৈশিষ্ট্য উভয়কেই সন্তুষ্ট করে, রৈখিক প্রোগ্রামগুলির মতো একই সাধারণ অবস্থান অনুমান সহ। এর উপপাদ্য এবং দেখায় যে, ভেরিয়েবল সহ একটি পূর্ণসংখ্যা প্রোগ্রামের জন্য, সমন্বয়মূলক মাত্রা সর্বাধিক। গণনামূলক জ্যামিতিতে অনেক প্রাকৃতিক অপ্টিমাইজেশান সমস্যা হল এল. পি-টাইপঃ ক্ষুদ্রতম বৃত্ত সমস্যা হল সমতলে প্রদত্ত বিন্দুর একটি সেট ধারণকারী একটি বৃত্তের ন্যূনতম ব্যাসার্ধ খুঁজে বের করার সমস্যা। এটি একঘেয়েমিকে সন্তুষ্ট করে (আরও পয়েন্ট যোগ করলে কেবল বৃত্তটি বড় হতে পারে) এবং স্থানীয়তা (যদি সেটের জন্য ক্ষুদ্রতম বৃত্তটি থাকে এবং, তবে একই বৃত্তটিও থাকে)। যেহেতু ক্ষুদ্রতম বৃত্তটি সর্বদা প্রায় তিনটি বিন্দু দ্বারা নির্ধারিত হয়, তাই ক্ষুদ্রতম বৃত্ত সমস্যার সংমিশ্রণমূলক মাত্রা তিন থাকে, যদিও এটি দ্বিমাত্রিক ইউক্লিডীয় জ্যামিতি ব্যবহার করে সংজ্ঞায়িত করা হয়। আরও সাধারণভাবে, মাত্রায় পয়েন্টের ক্ষুদ্রতম পরিবেষ্টিত বলটি সংমিশ্রণ মাত্রার একটি এল. পি-ধরনের সমস্যা তৈরি করে। সবচেয়ে ছোট বৃত্ত সমস্যাটিকে সাধারণীকরণ করা যেতে পারে বলের একটি সেটকে ঘিরে থাকা সবচেয়ে ছোট বল, বলের প্রতিটি সেটকে স্পর্শ বা ঘিরে থাকা সবচেয়ে ছোট বল, ওজনযুক্ত 1-কেন্দ্রের সমস্যা, বা অ-ইউক্লিডীয় জায়গাগুলিতে অনুরূপ ছোট আবদ্ধ বল সমস্যা যেমন ব্রেগম্যান বিচ্যুতি দ্বারা সংজ্ঞায়িত দূরত্ব সহ স্থান। ক্ষুদ্রতম আবদ্ধ উপবৃত্তাকার খুঁজে বের করার সম্পর্কিত সমস্যাটিও একটি এল. পি-টাইপ সমস্যা, তবে একটি বৃহত্তর সংমিশ্রণ মাত্রা সহ। ধরা যাক-মাত্রিক ইউক্লিডীয় স্থানে উত্তল সেটগুলির একটি ক্রম, এবং ধরুন আমরা এই ক্রমের দীর্ঘতম উপসর্গটি খুঁজে পেতে চাই যার একটি সাধারণ ছেদ বিন্দু রয়েছে। এটি একটি এল. পি-টাইপ সমস্যা হিসাবে প্রকাশ করা যেতে পারে যেখানে কি হল এ-এর প্রথম সদস্য যা এ-এর ছেদকারী উপসর্গের অন্তর্গত নয় এবং যেখানে যদি এমন কোনও সদস্য না থাকে। এই ব্যবস্থার সমন্বিত মাত্রা হল। ধরুন আমাদের ত্রিমাত্রিক স্থানে অক্ষ-সারিবদ্ধ আয়তক্ষেত্রাকার বাক্সগুলির একটি সংগ্রহ দেওয়া হয়েছে এবং স্থানের ধনাত্মক অষ্টকের মধ্যে নির্দেশিত একটি রেখা খুঁজে পেতে চাই যা সমস্ত বাক্স কেটে দেয়। এটি সংমিশ্রণ মাত্রা 4 সহ একটি এল. পি-টাইপ সমস্যা হিসাবে প্রকাশ করা যেতে পারে। দুটি উত্তল পলিটোপগুলির মধ্যে নিকটতম দূরত্ব খুঁজে বের করার সমস্যা, তাদের শীর্ষগুলির সেট দ্বারা নির্দিষ্ট, একটি এল. পি-টাইপ সমস্যা হিসাবে উপস্থাপিত হতে পারে। এই গঠনে, সেটটি উভয় পলিটপের সমস্ত শীর্ষের সেট, এবং ফাংশন মান হল দুটি পলিটপের শীর্ষের দুটি উপসেটগুলির উত্তল হুলের মধ্যে ক্ষুদ্রতম দূরত্বের নেতিবাচকতা। সমস্যাটির সমন্বিত মাত্রা হল যদি দুটি পলিটোপ বিচ্ছিন্ন হয়, অথবা যদি তাদের একটি অ-খালি ছেদ থাকে। ধরা যাক} কোয়াসিকোভেক্স ফাংশনের একটি সেট। তারপর পয়েন্টওয়াইজ ম্যাক্সিমম নিজেই কোয়াসিকোভেক্স, এবং এর ন্যূনতম মান খুঁজে বের করার সমস্যা হল একটি এল. পি-টাইপ সমস্যা। এটির সর্বাধিক সমন্বিত মাত্রা রয়েছে, যেখানে ফাংশনের ক্ষেত্রের মাত্রা কোথায়, তবে পর্যাপ্ত মসৃণ ফাংশনের জন্য সমন্বয়মূলক মাত্রা সর্বাধিক ছোট। অন্যান্য অনেক এল. পি-ধরনের সমস্যা এইভাবে কোয়াসিকোভেক্স ফাংশন ব্যবহার করে প্রকাশ করা যেতে পারে; উদাহরণস্বরূপ, ক্ষুদ্রতম পরিবেষ্টিত বৃত্ত সমস্যা হল যেখানে প্রতিটি ফাংশন প্রদত্ত বিন্দুগুলির মধ্যে একটি থেকে ইউক্লিডীয় দূরত্ব পরিমাপ করে তা হ্রাস করার সমস্যা। এল. পি-টাইপ সমস্যাগুলি অ্যালগরিদমিক গেম তত্ত্বে নির্দিষ্ট গেমগুলির সর্বোত্তম ফলাফল নির্ধারণ করতে, সীমাবদ্ধ উপাদান পদ্ধতি জালগুলিতে ভার্টেক্স বসানোর উন্নতি করতে, সুবিধার অবস্থানের সমস্যাগুলি সমাধান করতে, নির্দিষ্ট সূচকীয়-সময়ের অনুসন্ধান অ্যালগরিদমগুলির সময় জটিলতা বিশ্লেষণ করতে এবং তাদের দ্বি-মাত্রিক চিত্র থেকে বস্তুর ত্রিমাত্রিক অবস্থানগুলি পুনর্গঠন করতেও ব্যবহার করা হয়েছে। অ্যালগরিদম সিডেল নিম্ন-মাত্রিক রৈখিক প্রোগ্রামিংয়ের জন্য একটি অ্যালগরিদম দিয়েছে যা এলপি-টাইপ সমস্যা কাঠামোর সাথে খাপ খাইয়ে নেওয়া যেতে পারে। সিডেলের অ্যালগরিদম ইনপুট হিসাবে সেট এবং সর্বোত্তম ভিত্তির অন্তর্গত হিসাবে পরিচিত উপাদানগুলির একটি পৃথক সেট (প্রাথমিকভাবে খালি) গ্রহণ করে। এরপরে এটি অবশিষ্ট উপাদানগুলিকে একটি এলোমেলো ক্রমে বিবেচনা করে, প্রত্যেকটির জন্য লঙ্ঘন পরীক্ষা করে এবং ফলাফলের উপর নির্ভর করে, পরিচিত ভিত্তি উপাদানগুলির একটি বৃহত্তর সেট সহ একই অ্যালগরিদমে একটি পুনরাবৃত্তিমূলক কল সম্পাদন করে। এটি নিম্নলিখিত সিউডোকোড দিয়ে প্রকাশ করা যেতে পারেঃ ফাংশন সিডেল (এস, এফ, এক্স) হ 'ল আরঃ = খালি সেট বিঃ = এস-এর এলোমেলো বিন্যাসে এক্স-এর জন্য এক্সঃ যদি এফ (বি) § এফ (বি ≤ {এক্স}): বিঃ = সিডেল (আর, এফ, এক্স ≤ {এক্স}) আরঃ = আর ≤ {এক্স} রিটার্ন বি সংযুক্ত মাত্রার একটি সমস্যায়, অ্যালগরিদমের তম পুনরাবৃত্তির লঙ্ঘন পরীক্ষা কেবল তখনই ব্যর্থ হয় যখন অবশিষ্ট ভিত্তি উপাদানগুলির মধ্যে একটি হয়, যা সর্বাধিক সম্ভাবনার সাথে ঘটে। এই গণনার উপর ভিত্তি করে, এটি দেখানো যেতে পারে যে সামগ্রিকভাবে অ্যালগরিদম দ্বারা সঞ্চালিত লঙ্ঘন পরীক্ষার প্রত্যাশিত সংখ্যা রৈখিক তবে সূচকীয়ের চেয়ে খারাপ। ক্লার্কসন র্যান্ডম স্যাম্পলিং কৌশলের উপর ভিত্তি করে রৈখিক প্রোগ্রামিংয়ের জন্য দুটি অ্যালগরিদম, একটি পুনরাবৃত্তিমূলক অ্যালগরিদম এবং একটি পুনরাবৃত্তিমূলক অ্যালগরিদম সংজ্ঞায়িত করেন এবং উভয়ের সংমিশ্রণের পরামর্শ দেন যা পুনরাবৃত্তিমূলক অ্যালগরিদম থেকে পুনরাবৃত্তিমূলক অ্যালগরিদমকে ডাকে। পুনরাবৃত্তিমূলক অ্যালগরিদম বারবার এলোমেলো নমুনাগুলি বেছে নেয় যার আকার ইনপুট আকারের প্রায় বর্গমূল, নমুনা সমস্যাটি পুনরাবৃত্তিমূলকভাবে সমাধান করে এবং তারপরে অবশিষ্ট উপাদানগুলির একটি উপসেট খুঁজে বের করার জন্য লঙ্ঘন পরীক্ষা ব্যবহার করে যাতে কমপক্ষে একটি ভিত্তি উপাদান অন্তর্ভুক্ত থাকতে হবেঃ ফাংশন পুনরাবৃত্তিমূলক (এস, এফ) এক্সঃ = খালি সেট পুনরাবৃত্তি আরঃ = আকারের সাথে এস-এর একটি এলোমেলো উপসেট ডি আর এন বিঃ = আর এক্স-এর জন্য ভিত্তি, পুনরাবৃত্তভাবে গণনা করা ভিঃ = {x। এফ (বি) § এফ (বি এক্স এক্স এক্স এক্স) এক্সঃ = এক্স এক্স ভি যতক্ষণ না ভি খালি রিটার্ন বি হয় প্রতিটি পুনরাবৃত্তিতে, এর প্রত্যাশিত আকার, এবং যখনই খালি হয় তখন এতে কমপক্ষে একটি অন্তর্ভুক্ত থাকে। অতএব, অ্যালগরিদম সর্বাধিক পুনরাবৃত্তিতে কাজ করে, যার প্রতিটি লঙ্ঘন পরীক্ষা করে এবং আকারের একটি উপ-সমস্যার জন্য একটি একক পুনরাবৃত্তিমূলক কল করে। ক্লার্কসনের পুনরাবৃত্তিমূলক অ্যালগরিদম প্রতিটি উপাদানকে ওজন বরাদ্দ করে, প্রাথমিকভাবে তাদের সবগুলিই সমান। এরপরে এটি এলোমেলোভাবে উপাদানগুলির একটি সেট বেছে নেয় এবং পূর্ববর্তী অ্যালগরিদমের মতো সেটগুলি গণনা করে। যদি এর মোট ওজন সর্বাধিক গুণ মোট ওজন হয় (ধ্রুবক সম্ভাবনার সাথে ঘটে) তবে অ্যালগরিদম এর প্রতিটি উপাদানের ওজন দ্বিগুণ করে এবং আগের মতো এই প্রক্রিয়াটি খালি না হওয়া পর্যন্ত পুনরাবৃত্তি করে। প্রতিটি পুনরাবৃত্তিতে, সর্বোত্তম ভিত্তির ওজন মোট ওজনের চেয়ে বেশি হারে বৃদ্ধি হতে দেখা যায়, যেখান থেকে এটি অনুসরণ করে যে অ্যালগরিদমকে অবশ্যই পুনরাবৃত্তির মধ্যে শেষ করতে হবে। একটি প্রদত্ত সমস্যা সমাধানের জন্য পুনরাবৃত্তিমূলক অ্যালগরিদম ব্যবহার করে, তার পুনরাবৃত্তিমূলক কলগুলির জন্য পুনরাবৃত্তিমূলক অ্যালগরিদমটিতে স্যুইচ করে এবং তারপরে পুনরাবৃত্তিমূলক অ্যালগরিদম দ্বারা করা কলগুলির জন্য সিডেলের অ্যালগরিদমটিতে আবার স্যুইচ করে, লঙ্ঘন পরীক্ষা ব্যবহার করে প্রদত্ত এলপি-টাইপ সমস্যা সমাধান করা সম্ভব। যখন একটি রৈখিক প্রোগ্রামে প্রয়োগ করা হয়, তখন এই অ্যালগরিদমটিকে একটি দ্বৈত সিম্প্লেক্স পদ্ধতি হিসাবে ব্যাখ্যা করা যেতে পারে। লঙ্ঘন পরীক্ষা এবং ভিত্তি গণনার আদিমগুলির বাইরে কিছু অতিরিক্ত গণনামূলক আদিমগুলির সাথে, এই পদ্ধতিটিকে নির্ধারক করা যেতে পারে। ম্যাটুসেক, শারির এবং ওয়েলজল এমন একটি অ্যালগরিদম বর্ণনা করেছেন যা রৈখিক প্রোগ্রামগুলির একটি অতিরিক্ত বৈশিষ্ট্য ব্যবহার করে যা সর্বদা অন্যান্য এলপি-টাইপ সমস্যাগুলির দ্বারা ধারণ করা হয় না, যে সমস্ত ঘাঁটির একে অপরের একই কার্ডিনালিটি রয়েছে। যদি কোনও এল. পি-টাইপ সমস্যার এই বৈশিষ্ট্য না থাকে, তবে নতুন ডামি উপাদান যোগ করে এবং ফাংশনটি সংশোধন করে তার পুরানো মান এবং সংখ্যার অর্ডার করা জোড়াটি অভিধানগতভাবে ফেরত দেওয়ার জন্য এটি তৈরি করা যেতে পারে। একবারে এস ওয়ান-এর উপাদানগুলি যোগ করার পরিবর্তে, বা উপাদানগুলির নমুনা খুঁজে বের করার পরিবর্তে, একটি অ্যালগরিদম বর্ণনা করুন যা একবারে উপাদানগুলিকে সরিয়ে দেয়। প্রতিটি ধাপে এটি একটি ভিত্তি বজায় রাখে যা প্রাথমিকভাবে ডামি উপাদানগুলির সেট হতে পারে। এটি নিম্নলিখিত সিউডোকোড দিয়ে বর্ণনা করা যেতে পারেঃ ফাংশন এম. এস. ডব্লিউ (এস, এফ, সি) হল যদি এস = সি হয় তবে রিটার্ন সি একটি এলোমেলো উপাদান x বেছে নেয় এস\সি বি = এম. এস. ডব্লিউ (এস\এক্স, এফ, সি) যদি এফ (বি) ≤ এফ (বি ≤ {এক্স}) হয় তবে বিঃ = বেসিস (বি ≤ {এক্স}) বিঃ = এম. এস. ডব্লিউ (এস, এফ, বি) রিটার্ন বি অ্যালগরিদমের বেশিরভাগ পুনরাবৃত্তিমূলক কলগুলিতে, লঙ্ঘন পরীক্ষা সফল হয় এবং যদি বিবৃতিটি বাদ দেওয়া হয়। যাইহোক, একটি ছোট সম্ভাবনার সঙ্গে লঙ্ঘন পরীক্ষা ব্যর্থ হয় এবং অ্যালগরিদম একটি অতিরিক্ত ভিত্তি গণনা এবং তারপর একটি অতিরিক্ত পুনরাবৃত্তিমূলক কল করে। লেখকরা যেমন দেখিয়েছেন, অ্যালগরিদমের জন্য প্রত্যাশিত সময় n-এ রৈখিক এবং এর বর্গমূলের সূচকীয়। এই পদ্ধতিটিকে ক্লার্কসনের পুনরাবৃত্তিমূলক এবং পুনরাবৃত্তিমূলক পদ্ধতির সাথে একত্রিত করে, সময় নির্ভরতার এই দুটি রূপকে একে অপরের থেকে পৃথক করা যেতে পারে, যার ফলে একটি অ্যালগরিদম যা বাইরের পুনরাবৃত্তিমূলক অ্যালগরিদমের ও (ডিএন) লঙ্ঘন পরীক্ষা করে এবং একটি সংখ্যা যা সূচক হয় অ্যালগরিদমের নিম্ন স্তরের বর্গমূল। বৈচিত্র্য আউটলায়ারগুলির সাথে অপ্টিমাইজেশান এলপি-টাইপ অপ্টিমাইজেশান সমস্যার একটি বৈচিত্র্য বিবেচনা করে যেখানে সেট এবং উদ্দেশ্যমূলক ফাংশন সহ একটি সংখ্যা দেওয়া হয়; কাজটি হল অবশিষ্ট সেটের উদ্দেশ্যমূলক ফাংশনটিকে যতটা সম্ভব ছোট করার জন্য উপাদানগুলি সরিয়ে ফেলা। উদাহরণস্বরূপ, যখন ক্ষুদ্রতম বৃত্তের সমস্যায় প্রয়োগ করা হয়, তখন এটি ক্ষুদ্রতম বৃত্তটি দেবে যা সমতলীয় বিন্দুর একটি নির্দিষ্ট সেট ছাড়া সমস্ত কিছু ধারণ করে। তিনি দেখান যে, সমস্ত নন-ডিজেনারেট এল. পি-টাইপ সমস্যার জন্য (অর্থাৎ, যে সমস্যাগুলিতে সমস্ত ভিত্তির স্বতন্ত্র মান রয়েছে) এই সমস্যাটি সময়মতো সমাধান করা যেতে পারে, এর উপসেট দ্বারা সংজ্ঞায়িত এল. পি-টাইপ সমস্যার একটি সেট সমাধান করে। অন্তর্নিহিত সমস্যা কিছু জ্যামিতিক অপ্টিমাইজেশান সমস্যা এল. পি-টাইপ সমস্যা হিসাবে প্রকাশ করা যেতে পারে যেখানে এল. পি-টাইপ গঠনে উপাদানগুলির সংখ্যা অপ্টিমাইজেশান সমস্যার জন্য ইনপুট ডেটা মানের সংখ্যার তুলনায় উল্লেখযোগ্যভাবে বেশি। উদাহরণস্বরূপ, সমতলে পয়েন্টগুলির একটি সংগ্রহ বিবেচনা করুন, প্রতিটি স্থির বেগ নিয়ে চলছে। যে কোনও সময়ে, এই ব্যবস্থার ব্যাস হল এর দুটি বিন্দুর মধ্যে সর্বোচ্চ দূরত্ব। এমন একটি সময় খুঁজে বের করার সমস্যা যেখানে ব্যাসকে ন্যূনতম করা হয়, প্রতিটি জোড়া বিন্দুর জন্য একটি করে, সময়ের একটি ফাংশন হিসাবে জুটির মধ্যে ইউক্লিডীয় দূরত্ব পরিমাপ করে, কোয়াসিকোভেক্স ফাংশনের পয়েন্টওয়াইজ সর্বাধিককে ন্যূনতম হিসাবে প্রণয়ন করা যেতে পারে। সুতরাং, এটি উপাদানগুলির একটি সেটের উপর দুটি সমন্বিত মাত্রার একটি এল. পি-টাইপ সমস্যা হিসাবে সমাধান করা যেতে পারে, তবে এই সেটটি ইনপুট পয়েন্টের সংখ্যার তুলনায় উল্লেখযোগ্যভাবে বড়। অন্তর্নিহিতভাবে সংজ্ঞায়িত এল. পি-টাইপ সমস্যা সমাধানের জন্য একটি অ্যালগরিদম বর্ণনা করে যেমন এইটিতে প্রতিটি এল. পি-টাইপ উপাদান কিছু ধ্রুবকের জন্য ইনপুট মানের একটি-টুপল দ্বারা নির্ধারিত হয়। তার পদ্ধতি প্রয়োগ করার জন্য, একটি সিদ্ধান্ত অ্যালগরিদম থাকতে হবে যা নির্ধারণ করতে পারে, একটি প্রদত্ত এলপি-টাইপ ভিত্তি এবং ইনপুট মানগুলির সেটের জন্য, দ্বারা নির্ধারিত এলপি-টাইপ সমস্যার জন্য একটি ভিত্তি কিনা। চ্যানের অ্যালগরিদম নিম্নলিখিত পদক্ষেপগুলি সম্পাদন করেঃ যদি ইনপুট মানগুলির সংখ্যা কিছু প্রান্তিক মানের নিচে থাকে, তবে এলপি-টাইপ উপাদানগুলির সেটটি খুঁজে বের করুন যা এটি নির্ধারণ করে এবং ফলস্বরূপ স্পষ্ট এলপি-টাইপ সমস্যার সমাধান করে। অন্যথায়, ইনপুট মানগুলিকে সমান আকারের উপসেটগুলির চেয়ে বড় একটি উপযুক্ত সংখ্যায় ভাগ করুন। যদি অন্তর্নিহিতভাবে সংজ্ঞায়িত এলপি-টাইপ সমস্যার সমাধান করার জন্য উদ্দেশ্যমূলক ফাংশন হয়, তবে এমন একটি ফাংশন সংজ্ঞায়িত করুন যা সংগ্রহের মিলনের মানের সাথে উপসেটগুলির সংগ্রহকে ম্যাপ করে। তারপরে উপসেটগুলির সংগ্রহ এবং উদ্দেশ্যমূলক ফাংশন নিজেই একটি এল. পি-টাইপ সমস্যাকে সংজ্ঞায়িত করে, যা সমাধান করা অন্তর্নিহিত সমস্যার মতো একই মাত্রার। ক্লার্কসনের অ্যালগরিদম ব্যবহার করে সংজ্ঞায়িত (স্পষ্ট) এল. পি-টাইপ সমস্যাটি সমাধান করুন, যা একটি রৈখিক সংখ্যক লঙ্ঘন পরীক্ষা এবং একটি পলিলোগারিদমিক সংখ্যার ভিত্তি মূল্যায়ন সম্পাদন করে। চ্যানের অ্যালগরিদমে পুনরাবৃত্তিমূলক কলের মাধ্যমে ভিত্তি মূল্যায়ন করা যেতে পারে এবং লঙ্ঘন পরীক্ষাগুলি সিদ্ধান্ত অ্যালগরিদমে কলের মাধ্যমে করা যেতে পারে। এই অনুমানের সাথে যে সিদ্ধান্ত অ্যালগরিদমটি এমন পরিমাণ সময় নেয় যা ইনপুট আকারের একটি ফাংশন হিসাবে কমপক্ষে বহুপদীভাবে বৃদ্ধি পায়, চ্যান দেখায় যে একটি স্পষ্ট এলপি গঠনে স্যুইচ করার জন্য প্রান্তিক এবং পার্টিশনে উপসেটগুলির সংখ্যা এমনভাবে বেছে নেওয়া যেতে পারে যাতে অন্তর্নিহিত এলপি-টাইপ অপ্টিমাইজেশন অ্যালগরিদমও সময়মতো চলে। উদাহরণস্বরূপ, চলমান বিন্দুর ন্যূনতম ব্যাসের জন্য, সিদ্ধান্ত অ্যালগরিদমের শুধুমাত্র একটি নির্দিষ্ট সময়ে বিন্দুর একটি সেটের ব্যাস গণনা করা প্রয়োজন, একটি সমস্যা যা ঘূর্ণায়মান ক্যালিপার কৌশল ব্যবহার করে সময়মতো সমাধান করা যেতে পারে। অতএব, ব্যাসটি যে সময়ে ন্যূনতম করা হয় তা খুঁজে বের করার জন্য চ্যানের অ্যালগরিদমটিও সময় নেয়। চ্যান এই পদ্ধতিটি ব্যবহার করে-মাত্রিক ইউক্লিডীয় স্থানের বিন্দুগুলির একটি প্রদত্ত সংগ্রহের মধ্যে সর্বাধিক টুকি গভীরতার একটি বিন্দু খুঁজে বের করার জন্য। একটি উত্তল বহুভুজের উপর অভিন্ন বন্টনের জন্য সর্বাধিক টুকি গভীরতার একটি বিন্দু খুঁজে বের করার জন্য একটি অনুরূপ কৌশল ব্যবহার করা হয়েছিল। ইতিহাস এবং সম্পর্কিত সমস্যা রৈখিক প্রোগ্রামিংয়ের জন্য রৈখিক সময় অ্যালগরিদমের আবিষ্কার এবং পর্যবেক্ষণ যে একই অ্যালগরিদমগুলি অনেক ক্ষেত্রে জ্যামিতিক অপ্টিমাইজেশান সমস্যা সমাধানের জন্য ব্যবহার করা যেতে পারে যা রৈখিক প্রোগ্রাম ছিল না, অন্ততপক্ষে ফিরে যায়, যিনি তিন-পরিবর্তনশীল রৈখিক প্রোগ্রাম এবং ক্ষুদ্রতম বৃত্ত সমস্যা উভয়ের জন্য একটি রৈখিক প্রত্যাশিত সময় অ্যালগরিদম দিয়েছিলেন। যাইহোক, মেগিডো সেটের সিস্টেমে একটি বিমূর্ত সমস্যা হিসাবে নয়, বরং একটি উত্তল অপ্টিমাইজেশান সমস্যা হিসাবে জ্যামিতিকভাবে রৈখিক প্রোগ্রামিংয়ের সাধারণীকরণ প্রণয়ন করেছিলেন। একইভাবে, এবং ক্লার্কসন (1988 সালের সম্মেলনের সংস্করণে) পর্যবেক্ষণ করেছেন যে তাদের পদ্ধতিগুলি উত্তল প্রোগ্রামের পাশাপাশি রৈখিক প্রোগ্রামগুলিতে প্রয়োগ করা যেতে পারে। দেখিয়েছেন যে ন্যূনতম আবদ্ধ উপবৃত্তাকার সমস্যাটিকে অল্প সংখ্যক অ-রৈখিক সীমাবদ্ধতা যোগ করে উত্তল অপ্টিমাইজেশন সমস্যা হিসাবেও প্রণয়ন করা যেতে পারে। নিম্ন মাত্রিক রৈখিক প্রোগ্রামিং এবং সম্পর্কিত সমস্যাগুলির জন্য সময়সীমার উন্নতির জন্য র্যান্ডমাইজেশনের ব্যবহার ক্লার্কসন এবং দ্বারা প্রবর্তিত হয়েছিল। স্থানীয়তা এবং একঘেয়েমির স্বতঃসিদ্ধগুলিকে সন্তুষ্ট করে এমন ফাংশনের পরিপ্রেক্ষিতে এল. পি-টাইপ সমস্যার সংজ্ঞাটি থেকে, তবে একই সময়সীমার অন্যান্য লেখকরা রৈখিক প্রোগ্রামগুলির বিকল্প সমন্বয়মূলক সাধারণীকরণ প্রণয়ন করেছেন। উদাহরণস্বরূপ, দ্বারা বিকশিত একটি কাঠামোতে, ফাংশনটি এর উপসেটগুলিতে মোট ক্রম দ্বারা প্রতিস্থাপিত হয়। একটি মোট ক্রম তৈরি করার জন্য একটি এল. পি-টাইপ সমস্যায় বন্ধনগুলি ভেঙে ফেলা সম্ভব, তবে শুধুমাত্র সমন্বিত মাত্রার বৃদ্ধির ব্যয়ে। উপরন্তু, এল. পি-টাইপ সমস্যার মতো, গার্টনার উপাদানগুলির উপসেটগুলিতে গণনা সম্পাদনের জন্য নির্দিষ্ট আদিম সংজ্ঞায়িত করেন; তবে, তাঁর আনুষ্ঠানিককরণে সমন্বিত মাত্রার অনুরূপ নেই। রৈখিক প্রোগ্রাম এবং রৈখিক পরিপূরক সমস্যা উভয়েরই আরেকটি বিমূর্ত সাধারণীকরণ, যা অন্যান্য লেখকদের দ্বারা প্রণয়ন করা হয়েছে এবং পরে অধ্যয়ন করা হয়েছে, একটি হাইপারকিউবের প্রান্তগুলির অভিমুখকে এই বৈশিষ্ট্যের সাথে সম্পর্কিত করে যে হাইপারকিউবের প্রতিটি মুখের (মুখ হিসাবে পুরো হাইপারকিউব সহ) একটি অনন্য সিঙ্ক রয়েছে, একটি শীর্ষ যার কোনও বহির্গামী প্রান্ত নেই। এই ধরনের অভিযোজন একটি এল. পি-টাইপ সমস্যা থেকে গঠিত হতে পারে একটি হাইপারকিউবের শীর্ষগুলির সাথে এস-এর উপসেটগুলিকে এমনভাবে অনুরূপ করে যাতে দুটি উপসেট একটি একক উপাদান দ্বারা পৃথক হয় যদি এবং শুধুমাত্র যদি সংশ্লিষ্ট শীর্ষগুলি সংলগ্ন থাকে, এবং পার্শ্ববর্তী সেটগুলির মধ্যে প্রান্তটি যদি এবং অন্য দিকে অভিমুখী করে। ফলস্বরূপ অভিযোজনের অতিরিক্ত বৈশিষ্ট্য রয়েছে যে এটি একটি নির্দেশিত অ্যাসাইক্লিক গ্রাফ গঠন করে, যা থেকে এটি দেখানো যেতে পারে যে একটি র্যান্ডমাইজড অ্যালগরিদম পুরো হাইপারকিউবের অনন্য সিঙ্ক (এলপি-টাইপ সমস্যার সর্বোত্তম ভিত্তি) এর বর্গমূলের সূচকীয় বেশ কয়েকটি ধাপে খুঁজে পেতে পারে। লঙ্ঘনকারী স্থানগুলির আরও সম্প্রতি উন্নত কাঠামোটি এল. পি-টাইপ সমস্যাগুলিকে সাধারণীকরণ করে, এই অর্থে যে প্রতিটি এল. পি-টাইপ সমস্যা লঙ্ঘনকারী স্থান দ্বারা মডেল করা যেতে পারে তবে অগত্যা তদ্বিপরীত নয়। লঙ্ঘনকারী স্থানগুলি এল. পি-টাইপ সমস্যার মতো একইভাবে সংজ্ঞায়িত করা হয়, এমন একটি ফাংশন দ্বারা যা উদ্দেশ্যমূলক ফাংশন মানগুলিতে সেট করে, তবে এর মানগুলি অর্ডার করা হয় না। অর্ডারের অভাব সত্ত্বেও, প্রতিটি সেটের একটি সুনির্দিষ্ট বেস রয়েছে (পুরো সেটের মতো একই মান সহ ন্যূনতম সেট) যা এলপি-টাইপ সমস্যার জন্য ক্লার্কসনের অ্যালগরিদমের বৈচিত্র্য দ্বারা পাওয়া যায়। প্রকৃতপক্ষে, লঙ্ঘনকারী স্থানগুলি ক্লার্কসনের অ্যালগরিদম দ্বারা সমাধান করা যেতে পারে এমন সিস্টেমগুলিকে সঠিকভাবে চিহ্নিত করতে দেখানো হয়েছে। উল্লেখগুলি উল্লেখ করুন। । । । । । । । । । । । । । । । । । । । । । । । । । । । । । । । । । । গণনামূলক জ্যামিতি রৈখিক প্রোগ্রামিং