উন্নত এলপি সমাধান

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

এই নির্দেশিকাটি ধারণাগুলির সাথে পরিচয় করিয়ে দেয় এবং আপনাকে LP সমাধানকারীদের থেকে সর্বাধিক কার্যক্ষমতা এবং নির্ভরযোগ্যতা পেতে সহায়তা করার জন্য উদাহরণ প্রদান করে।

ধারণা

এই বিভাগটি এলপি সলভারগুলির উন্নত ব্যবহারের জন্য মূল ধারণাগুলি উপস্থাপন করে। আমরা অনুমান করি যে পাঠকরা এলপি-তে দ্বৈততার ধারণার সাথে পরিচিত।

এলপি অ্যালগরিদমের পরিবার

LP-এর জন্য নিম্নোক্ত শ্রেণীর অ্যালগরিদমগুলি OR-Tools-এর মাধ্যমে অ্যাক্সেসযোগ্য।

  1. সিমপ্লেক্স অ্যালগরিদম ছিল প্রথম ব্যবহারিক এলপি অ্যালগরিদম এবং এটি এখনও সবচেয়ে জনপ্রিয়। অ্যালগরিদম সম্ভাব্য অঞ্চলের শীর্ষবিন্দু (কোণার বিন্দু) বরাবর চলে, একটি সর্বোত্তম সমাধানে না পৌঁছানো পর্যন্ত উদ্দেশ্যমূলক ফাংশনের মানকে পুনরাবৃত্তি করে। দুটি ধরনের সিমপ্লেক্স অ্যালগরিদম রয়েছে:

    1. প্রাইমাল সিমপ্লেক্স প্রাথমিক সম্ভাব্য অঞ্চলের শীর্ষবিন্দু বরাবর পদক্ষেপ নেয়। এই বৈকল্পিকটি বিভিন্ন উদ্দেশ্যমূলক ফাংশন সহ LP সমস্যাগুলির একটি ক্রম সমাধানে বিশেষভাবে কার্যকর, অর্থাৎ যেখানে প্রাথমিক সম্ভাব্য অঞ্চল স্থির করা হয়েছে।
    2. ডুয়াল সিমপ্লেক্স দ্বৈত সম্ভাব্য অঞ্চলের শীর্ষবিন্দু বরাবর পদক্ষেপ নেয়। এই বৈকল্পিকটি এলপি সমস্যার একটি ক্রম সমাধানে বিশেষভাবে কার্যকর যেখানে দ্বৈত সম্ভাব্য অঞ্চল স্থির করা হয়, উদাহরণস্বরূপ, যখন শুধুমাত্র ভেরিয়েবলের সীমা পরিবর্তিত হয়। এই কারণে, ডুয়াল সিমপ্লেক্স এমআইপি সমাধানকারীদের মধ্যে ব্যাপকভাবে ব্যবহৃত হয়।

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

  3. প্রথম-ক্রম পদ্ধতিগুলি হল অ্যালগরিদমগুলির একটি পরিবার যা পুনরাবৃত্তগুলিকে গাইড করার জন্য একচেটিয়াভাবে গ্রেডিয়েন্ট তথ্য (অর্থাৎ প্রথম-ক্রম ডেরিভেটিভ) ব্যবহার করে। গ্রেডিয়েন্ট ডিসেন্ট একটি সুপরিচিত উদাহরণ। এই পদ্ধতিগুলি ননলাইনার অপ্টিমাইজেশান এবং মেশিন লার্নিং-এ জনপ্রিয়। LP-এর জন্য, প্রথম-ক্রম পদ্ধতিগুলি সিমপ্লেক্স এবং বাধার চেয়ে বড় সমস্যাগুলিকে স্কেল করতে পারে এবং এছাড়াও অনেক ছোট মেমরির প্রয়োজনীয়তা থাকতে পারে। অন্যদিকে, তারা সংখ্যাগত সমস্যাগুলির প্রতি আরও সংবেদনশীল এবং অত্যন্ত সঠিক সমাধান পেতে সংগ্রাম করতে পারে।

নীচের সারণীটি OR-Tools-এ উপলব্ধ LP সলভারগুলিকে তালিকাভুক্ত করে এবং নির্দেশ করে যে অ্যালগরিদমের তিনটি পরিবারের মধ্যে কোনটি প্রতিটি সলভারে প্রয়োগ করা হয়েছে৷

সমাধানকারী সিমপ্লেক্স বাধা প্রথম আদেশ
Clp এক্স এক্স
CPLEX এল এক্স এক্স
গ্লপ জি এক্স
জিএলপিকে এক্স এক্স
গুরোবি এল এক্স এক্স
পিডিএলপি জি এক্স
এক্সপ্রেস এল এক্স এক্স

G নির্দেশ করে যে সলভারটি গুগল ডেভেলপ করেছে। L নির্দেশ করে যে সমাধানকারীর জন্য সংশ্লিষ্ট তৃতীয় পক্ষের বিকাশকারী দ্বারা জারি করা লাইসেন্সের প্রয়োজন।

কোন সমাধানকারী এবং অ্যালগরিদমগুলি ব্যবহার করতে হবে তার পরামর্শগুলির জন্য সুপারিশগুলি দেখুন৷

সমাধান আসলে কি মানে?

LP সমাধানকারীদের থেকে সর্বাধিক সুবিধা পাওয়ার জন্য, যখন একজন সমাধানকারী একটি LP সমস্যার সমাধান খুঁজে পেয়েছে বলে দাবি করে তখন কী বোঝানো হয় তা বোঝা গুরুত্বপূর্ণ৷ এই বিভাগটি এই প্রশ্নের উত্তর দেওয়ার জন্য প্রয়োজনীয় মৌলিক বিষয়গুলি কভার করে, বিশেষ করে দেওয়া সংখ্যাগত অপূর্ণতা এবং সমাধানগুলির অ-স্বতন্ত্রতা।

সহনশীলতা

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

লিনিয়ার প্রোগ্রামিং সমস্যা বিবেচনা করুন

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

এবং এর সংশ্লিষ্ট দ্বৈত সমস্যা

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

এই জোড়া সমস্যার একটি অনন্য সর্বোত্তম প্রাথমিক সমাধান $x_1 = 1, x_2 = 0 $ এবং দ্বৈত সমাধান $y = -2 $। কোন সমাধান একটি সমাধানকারী দ্বারা সর্বোত্তম হিসাবে গ্রহণ করা যেতে পারে? এর উত্তর দেওয়ার জন্য, আমরা নিম্নলিখিত পরিমাণগুলি সংজ্ঞায়িত করি:

  • দ্বৈত ব্যবধান হল প্রাথমিক উদ্দেশ্য মান এবং দ্বৈত উদ্দেশ্য মানের মধ্যে পার্থক্য, এই ক্ষেত্রে, $ |(-2x_1 - x_2) - y| $
  • প্রাথমিক অসম্ভাব্যতা হল প্রাথমিক সীমাবদ্ধতার লঙ্ঘন, এই ক্ষেত্রে, $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2 , 0\}) $।
  • দ্বৈত অসম্ভাব্যতা হল দ্বৈত সীমাবদ্ধতার লঙ্ঘন, এই ক্ষেত্রে, $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \} ) $.

একটি সমাধানকারী একটি সমাধানকে সর্বোত্তম হিসাবে ঘোষণা করে যদি দ্বৈত ব্যবধান, প্রাথমিক অসম্ভাব্যতা এবং দ্বৈত অসম্ভাব্যতা প্রদত্ত সহনশীলতার চেয়ে ছোট হয়। 1

উল্লেখযোগ্যভাবে, সহনশীলতার প্রয়োগ সলভার এবং অ্যালগরিদম জুড়ে প্রাকৃতিক এবং বৈচিত্র্যময় উভয় কারণেই পরিবর্তিত হয়। উদাহরণ স্বরূপ, সিমপ্লেক্স অ্যালগরিদমে দ্বৈততার ব্যবধান শুধুমাত্র সংখ্যাগত অপূর্ণতা দ্বারা চালিত হয়, যখন প্রাথমিক এবং দ্বৈত অসম্ভাব্যতা এমনকি সঠিক পাটিগণিতেও উপস্থিত থাকে। কিছু পদ্ধতি সরাসরি $x_1 \ge 0, x_2 \ge 0, $ এবং $y \le 0 $ প্রয়োগ করে, যখন অন্যরা $x_1 + x_2 \le 1$ এর মতো রৈখিক সীমাবদ্ধতার লঙ্ঘন থেকে আবদ্ধ সীমাবদ্ধতার লঙ্ঘনকে ভিন্নভাবে বিবেচনা করে। কিছু সমাধানকারীদের জন্য, সহনশীলতা পরম ; অর্থাৎ, একটি পরামিতি $ \epsilon $ আছে, এবং সমাধানগুলিকে সর্বোত্তম হিসাবে বিবেচনা করা হয় যদি দ্বৈততার ব্যবধান এবং সমস্ত প্রাথমিক এবং দ্বৈত অসম্ভাব্যতা $ \epsilon $ এর থেকে কম বা সমান হয়। অন্যান্য সমাধানকারীদের জন্য, সহনশীলতাগুলি আপেক্ষিক , যার অর্থ তারা সমস্যার সহগগুলির আকারের সাথে স্কেল করে।

সহনশীলতার প্রভাবের উদাহরণের জন্য, উপরের আদি-দ্বৈত জোড়ায় প্রয়োগ করা $ \epsilon = \frac{1}{2} $ এর পরম সহনশীলতা বিবেচনা করুন। সমাধান $x_1 = 1.5, x_2 = 0, y = -3 $ এর শূন্য দ্বৈত ব্যবধান এবং অসম্ভাব্যতা সবগুলি $ \epsilon $ এর চেয়ে কম বা সমান, তাই একজন সমাধানকারী এই সমাধানটিকে "অনুকূল" ঘোষণা করতে পারে। তবুও, এর বস্তুনিষ্ঠ মান (-3) -2 এর প্রকৃত সর্বোত্তম উদ্দেশ্য মান থেকে 1 দ্বারা পৃথক। $ \epsilon $ এর সাধারণ ডিফল্ট মান $10^{-6}$ এবং $10^{-8}$ এর মধ্যে, যা এই ধরনের চরম উদাহরণকে বিরল করে তোলে কিন্তু অসম্ভব নয়।

সমাধানের প্রকারভেদ

LP সমস্যার একাধিক সর্বোত্তম সমাধান থাকতে পারে, এমনকি সহনশীলতার জন্য হিসাব করার সময়ও। আমরা উপরে উপস্থাপিত এলপি অ্যালগরিদমের তিনটি ভিন্ন পরিবার দ্বারা প্রত্যাবর্তিত সমাধানগুলির বৈশিষ্ট্যগুলি সংক্ষেপে আলোচনা করি।

সিমপ্লেক্স অ্যালগরিদমগুলি সর্বদা সম্ভাব্য অঞ্চলের শীর্ষবিন্দু বা কোণ বিন্দু প্রদান করে। এই সমাধানগুলি কিছু পরিস্থিতিতে পছন্দ করা হয় কারণ সেগুলি বিচ্ছিন্ন হতে থাকে।

বাধা এবং প্রথম-ক্রম পদ্ধতি সাধারণত শীর্ষবিন্দু ফেরত দেয় না। (তত্ত্ব অতিরিক্ত বৈশিষ্ট্য প্রদান করে যা এই গাইডের সুযোগের বাইরে।)

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

সুপারিশ

এলপি সলভারগুলির উন্নত ব্যবহারের জন্য আমরা নিম্নলিখিত সুপারিশগুলি করি৷

সমস্যা ডেটা স্কেলিং

সাংখ্যিক সমস্যার কারণে সমাধানকারীরা মডেলে ধীর অভিসার বা ব্যর্থতা অনুভব করতে পারে। এই ধরনের সমস্যা অনেক কারণে দেখা দিতে পারে; এখানে আমরা একটি উদাহরণ দিই।

LP মডেলগুলিতে খুব ছোট বা বড় সাংখ্যিক ধ্রুবকগুলি উপস্থিত হওয়া সাধারণ। উপরে থেকে উদাহরণটি প্রসারিত করে, যদি \(x_1\) এবং \(x_2\) "প্রোভাইডার 1" বা "প্রোভাইডার 2" কে নির্ধারিত গ্রাহকদের ভগ্নাংশের প্রতিনিধিত্ব করে এবং যদি আমরা এই গ্রাহকদের পরিবেশন করার মাধ্যমে সর্বাধিক সুবিধা পেতে চাই, তাহলে আমরা নিম্নলিখিত উদ্দেশ্যমূলক ফাংশন লিখতে পারি ,

$$ \min -c_1x_1 - c_2x_2 $$

কোথায়:

  • $c_1 $ হল প্রদানকারী 1 কে গ্রাহকদের বরাদ্দ করার সুবিধা
  • $c_2 $ হল প্রদানকারী 2 কে গ্রাহকদের বরাদ্দ করার সুবিধা

নিম্নলিখিত সীমাবদ্ধতাগুলিকে সন্তুষ্ট করে এমন দ্বৈতগুলি পরম সহনশীলতা $ \epsilon $ সহ সম্ভাব্য বলে বিবেচিত হবে:

  • $y \le -c_1 + \epsilon $,
  • $y \le -c_2 + \epsilon $।

যদি $c_1 $ এবং $c_2 $ এর সুবিধার ইউনিটগুলি ছোট ভগ্নাংশের মান হয় যেগুলি $ \epsilon $ এর মতো একই স্কেলে হয়, তাহলে দ্বৈত সম্ভাব্যতা শর্তগুলি বরং দুর্বল হয়ে পড়ে, তাই একটি খুব সাবঅপ্টিমাল প্রাইমালকে সর্বোত্তম ঘোষণা করা যেতে পারে।

অন্য দিকে, যদি সুবিধার ইউনিটগুলি হয় "মাইক্রোডলার" (1 000 000 মাইক্রোডলার = 1 ডলার), ফলে খুব বড় পরম মানগুলি সমাধানে খুব উচ্চ নির্ভুলতা চায়, সম্ভবত ভাসমান বিন্দু সংখ্যার সীমার কারণে অযৌক্তিকভাবে বেশি। সমাধানকারীরা একত্রিত হতে ব্যর্থ হতে পারে যদি সমস্যাটি এইভাবে তৈরি করা হয়। একটি ভাল-পোজড সমস্যা প্রণয়নের অংশ হিসাবে, উন্নত মডেলারদের বিবেচনা করা উচিত যদি সমস্যার ডেটা এমনভাবে মাপানো হয় যা তাদের সমাধানকারীর সহনশীলতার সাথে সামঞ্জস্যপূর্ণ।

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

Glop-এর সহনশীলতার জন্য, GlopParameters এ primal_feasibility_tolerance , dual_feasibility_tolerance , এবং solution_feasibility_tolerance দেখুন। লক্ষ্য করুন যে primal_feasibility_tolerance এবং dual_feasibility_tolerance অ্যালগরিদমের মধ্যে ব্যবহার করা হয়, যখন solution_feasibility_tolerance সংখ্যাসূচক সমস্যাগুলি চিহ্নিত করার জন্য সমাধানের পরে পরীক্ষা করা হয়। PDLP-এর জন্য, eps_optimal_absolute এবং eps_optimal_relative দেখুন।

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

সমাধানকারী এবং অ্যালগরিদমের পছন্দ

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

অনুশীলনে পরিবর্তনশীলতা

আমরা LP অ্যালগরিদম এবং সলভার জুড়ে কর্মক্ষমতার পরিবর্তনশীলতা চিত্রিত করি যেগুলি LP সলভার বেঞ্চমার্ক করার জন্য হ্যান্স মিটেলম্যান ব্যবহার করেছেন এমন উদাহরণগুলির একটি নির্বাচনের উপর সমাধানের সময়ের তুলনা করে। দৃষ্টান্তগুলি স্পষ্টভাবে আপেক্ষিক কর্মক্ষমতার চরমতা দেখানোর জন্য বেছে নেওয়া হয়েছে এবং অগত্যা সাধারণ আচরণের প্রতিনিধি নয় ।

Glop-এর প্রাথমিক এবং দ্বৈত সিমপ্লেক্স পদ্ধতি গুরোবির বাধা পদ্ধতির সাথে তুলনা করা হয় (ক্রসওভার সহ এবং ছাড়া, যা একটি শীর্ষবিন্দু সমাধান খুঁজে পায়) এবং PDLP, একটি প্রথম-ক্রম পদ্ধতি, উচ্চ এবং নিম্ন নির্ভুলতায়। নীচের সারণীটি 20 মিনিট (1200 সেকেন্ড) এর সীমা সহ সেকেন্ডে সময়গুলি সমাধান করে।

দৃষ্টান্ত গ্লপ
প্রাইমাল সিমপ্লেক্স		 গ্লপ
ডুয়াল সিমপ্লেক্স		 গুরোবি বাধা
ক্রসওভার সঙ্গে		 গুরোবি বাধা
ক্রসওভার ছাড়া		 পিডিএলপি
উচ্চ নির্ভুলতা		 পিডিএলপি
নিম্ন নির্ভুলতা
ex10 >1200 >1200 79.7 63.5 8.2 2.7
nug08-3য় >1200 252.8 144.6 3.2 1.1 0.9
savsched1 >1200 >1200 156.0 22.6 46.4 32.4
প্রশস্ত15 >1200 20.8 >1200 >1200 916.4 56.3
বিল্ডিং এনার্জি 178.4 267.5 12.8 12.3 >1200 157.2
s250r10 12.1 520.6 15.2 16.4 >1200 >1200
সমাধানকারী সংস্করণ OR- টুলস 9.3 OR- টুলস 9.3 গুরোবি 9.0 গুরোবি 9.0 OR- টুলস 9.3 OR- টুলস 9.3
solver_specific_parameters (পূর্ব নির্ধারিত) use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

এই ফলাফল থেকে আমরা নিম্নলিখিত উপসংহারে.

  • অ্যালগরিদম এবং সমাধানকারীদের আপেক্ষিক কর্মক্ষমতা একটি একক দৃষ্টান্তে মাত্রার আদেশ অনুসারে পরিবর্তিত হতে পারে।
  • কোনো একক অ্যালগরিদম এবং সমাধানকারী অন্যদের চেয়ে সমানভাবে ভালো নয়।
  • ক্রসওভার (ডিফল্টরূপে সক্রিয়) সমাধানের সময় বাড়ায়, কখনও কখনও যথেষ্ট পরিমাণে।
  • PDLP উচ্চ নির্ভুলতার চেয়ে কখনও কখনও 10 গুণ দ্রুত কম নির্ভুলতায় সমাধান করতে পারে।

LP সমাধানকারী নির্বাচন করার জন্য একটি সংক্ষিপ্ত নির্দেশিকা

প্রদত্ত যে কোনও একক LP অ্যালগরিদম বা সমাধানকারী সর্বোত্তম নয়, আপনার ব্যবহারের ক্ষেত্রে কোনটি সেরা তা আবিষ্কার করার জন্য আমরা নিম্নলিখিত পদক্ষেপগুলি সুপারিশ করি৷ প্রথম ধাপ দিয়ে শুরু করুন এবং পারফরম্যান্স যথেষ্ট না হলে পরবর্তীতে যান।

  1. Glop চেষ্টা করুন. কেন : Glop হল Google এর প্রাথমিক এবং দ্বৈত সিমপ্লেক্স পদ্ধতির ইন-হাউস বাস্তবায়ন। Glop হল ওপেন সোর্স এবং Google-এর প্রোডাকশন ওয়ার্কলোডের জন্য বিশ্বস্ত৷
    • যদি ডিফল্ট কনফিগারেশন (প্রাইমাল সিমপ্লেক্স) ভালভাবে কাজ না করে, তাহলে use_dual_simplex: true ব্যবহার করে ডুয়াল সিম্পলক্সে স্যুইচ করার চেষ্টা করুন।
  2. যদি একটি লাইসেন্স পাওয়া যায়, একটি বাণিজ্যিক সমাধানের চেষ্টা করুন (CPLEX, Gurobi, বা Xpress)। সিমপ্লেক্স এবং বাধা পদ্ধতি নিয়ে পরীক্ষা করুন। কেন: এই সমাধানকারীগুলি শিল্পের মান এবং অত্যন্ত অপ্টিমাইজড। এছাড়াও, বাধা পদ্ধতিগুলি Glop দ্বারা প্রস্তাবিত সিমপ্লেক্স অ্যালগরিদমগুলির পরিপূরক।
    • বাধা ব্যবহার করলে, "ক্রসওভার" অক্ষম করুন যদি আপনার একটি শীর্ষবিন্দু সমাধানের প্রয়োজন না হয়।
  3. PDLP চেষ্টা করুন। আপনার আবেদনের সাথে কনভারজেন্স টলারেন্স টিউন করুন। কেন: PDLP সবচেয়ে বড় সমস্যাগুলির জন্য ডিজাইন করা হয়েছে, যেখানে সিমপ্লেক্স এবং বাধা পদ্ধতিগুলি মেমরির সীমাকে আঘাত করে বা খুব ধীর। PDLP সর্বোত্তম কার্য সম্পাদন করে যখন একটি আনুমানিক কিন্তু দ্রুত সমাধানকে একটি সঠিক কিন্তু ধীর সমাধানের চেয়ে পছন্দ করা হয়।
  4. আপনি যদি এটি এতদূর তৈরি করে থাকেন তবে আপনি এখন একজন উন্নত এলপি ব্যবহারকারী! আরও সাহায্যের জন্য অনুগ্রহ করে OR-Tools সমর্থন বিকল্পগুলি দেখুন৷

  1. এটি প্রায়শই এর চেয়ে জটিল। সমাধানকারীরা সাধারণত সমস্যাটির রূপান্তরিত/সরলীকৃত সংস্করণে এই শর্তগুলি পরীক্ষা করে, যাকে সমাধান করা সমস্যা বলা হয়। কিছু ক্ষেত্রে, সমাধান করা সমস্যার সমাধান ইনপুট সমস্যার সমাধান থেকে অনেক দূরে হতে পারে। এই পরিস্থিতি CPLEX এর OptimalInfeas বা Glop এর IMPRECISE মত অস্বাভাবিক অবস্থার দিকে নিয়ে যেতে পারে। ↩