پژوهش: مدل‌های زبانی در تشخیص قیدهای مکمل، به نام‌ها و استدلال وابسته‌اند

در بازصورت‌بندی Dantzig–Wolfe، انتخاب خانواده‌های قید برای محدب‌سازی می‌تواند کران ریلکسیشن خطی یک مسئلهٔ بهینه‌سازی آمیخته‌صحیح را تقویت کند. اما هر انتخاب به اجرای column generation نیاز دارد و بعضی خانواده‌های قید فقط به‌صورت گروهی اثر می‌گذارند؛ در این حالت، جست‌وجویی که هر بار یک خانواده را می‌افزاید ممکن است بهبود را نبیند و متوقف شود.

پژوهشگران در مقالهٔ پیش‌چاپی در arXiv ثابت می‌کنند اگر هر ارزیابی حداکثر s خانواده از میان k خانواده را محدب کند، روشی که فقط کران‌ها را مشاهده می‌کند برای یافتن یک گروه پنهان شامل w خانواده به تعداد ارزیابی‌هایی در مرتبهٔ k^w نیاز دارد. این نتیجه، به‌گفتهٔ مقاله، دربارهٔ ریلکسیشن‌های واقعی Dantzig–Wolfe نیز برقرار است. اگر پیش‌بینی اولیه e عضو گروه را جا بیندازد، یک جست‌وجوی مرحله‌ای می‌تواند هزینه را به مرتبهٔ Θ(k^e) کاهش دهد، بی‌آنکه لازم باشد مقدار e از پیش معلوم باشد.

مقاله دو منبع پیش‌بینی را بررسی می‌کند: نگاه یک‌مرحله‌ای به دوگان بهینهٔ مسئلهٔ خطی و مدل زبانی‌ای که نام‌ها و متن مدل را می‌خواند. روش پیشنهادی JointDW پیش‌بینی مدل زبانی را با جست‌وجوی مرحله‌ای می‌آزماید و آن را با نگاه دوگانی ترکیب می‌کند؛ نویسندگان می‌گویند این ترکیب افت عملکرد را محدود می‌کند. نگاه دوگانی در یک‌مرحله‌ای برای گروه‌هایی نابینا است که خانواده‌هایشان هیچ متغیری را مشترک ندارند.

در مدل‌های MIPLIB-NL که کرانشان قابل بهبود بود، گروه‌های مؤثر فقط در کنار هم در یک‌چهارم مدل‌ها دیده شدند. قوی‌ترین مدل‌های زبانی در شناسایی این گروه‌ها تقریباً به‌اندازهٔ روش دوگانی موفق بودند؛ برای مدل‌های درسی، پیش‌بینی‌شان بر نام‌ها تکیه داشت و افزودن استدلال دقت همان مدل را دو برابر کرد. در مدل‌های بزرگ‌تر و دارای خانواده‌های قید گمراه‌کننده، روش دوگانی گروه را با یک ارزیابی از سه خانواده پیدا کرد. مدل‌های زبانی که فقط متن را دریافت کردند به‌ندرت آن را نام بردند، اما یک مدل استدلالی که همهٔ ضرایب را در اختیار داشت، جز در یک پاسخ همیشه گروه را شناسایی کرد و برای جفت‌خانواده‌ها به ارزیابی‌های کمتری از روش دوگانی نیاز داشت.