مسأله الگوریتم تقریبی سال قبل

من داشتم حل تمرین‌های سال قبل را می‌نوشتم ولی انگار ذخیره نشده بود. سوال این بود که یک ماتریس ۰ و ۱ داریم می‌خواهیم ببینیم حالتی هست که ستون‌ها را جا به جا کنیم و همه‌ی ۱ ها کنار هم قرار بگیرند. (با integer programming حل کنید.)

حل من این بود که هر درایه ماتریس را یک متغیر می‌گیریم و مقادیر اولیه را به صورت قیود تساوی می‌گذاریم.

یک سری متغیر دیگر هم تعریف می‌کنیم که معادل جا به جا کردن هر دو ستون باشند.

برای اینکه یک‌ها کنار هم باشند هم باید متغیرهایی که تعریف کرده‌ایم به ازای یکی از حالت‌های تقسیم هر سطر به دو قسمت یک بخش ۱ داشته باشند. برای اینکه یکی از این شرط ها برقرار باشد می‌توانیم به ازای آنهایی که ۱ هستند یکی کم کنیم در این صورت حالت درست معادل ۰ می‌شود و اگر همه را در هم ضرب کنیم و صفر شود جواب دارد در غیر این صورت جواب ندارد.