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