پاسخی که @mdardah داده‌اند دقیقا پاسخی است که مدنظر سازندهٔ پرسش بوده‌است. ولی در کل برای افرادی که علاقه به روش‌های گوناگون دارند، یک روش ممکن بازنویسیِ پرسش به شکل یک برنامه‌نویسی صحیح خطی (linear integer programming) که در واقع بهتر است بگوئیم بهینه‌سازی صحیح خطی است. سپس از الگوریتم‌های ارائه شده برای حل چنین مدل‌هایی می‌توانید استفاده کنید. در اینجا تنها یکی از حالت‌های ممکن برای این بازنویسی را اشاره می‌کنیم. و تأکید می‌کنیم که این روش بهترین روش نیست!
دو عدد مورد نظر را می‌توانیم به شکل روبرو بنویسیم.
\begin{align}
y_1 &= 1000x_4+100x_3+10x_2+x_1\\
y_2 &= 1000x_8+100x_7+10x_6+x_5
\end{align}
که $x_i$ها رقم‌های این عددها هستند. پس پرسش بهینه‌سازی‌مان به شکل زیر در می‌آید، توجه کنید که می‌خواهیم $y_1+y_2$ کمینه شود که تابع هدف می‌شود.
$$
\begin{array}{l}
\min\qquad 1000x_8+1000x_4+100x_7+100x_3+10x_6+10x_2+x_5+x_1\\
\text{s.t. }\qquad\begin{cases}
x_1,\cdots,x_8\in\lbrace 1,2,\cdots,8\rbrace\\
x_i\neq x_j\;:\;\forall 1\leq i\lneqq j\leq 8
\end{cases}
\end{array}
$$
توجه کنید که تابع هدف خطی است. میماند اینکه شرایط نامساوی را به شکل بزرگتریامساوی یا کوچکتریامساوی بازنویسی کنیم. توجه کنید که شرطِ $u\neq v$ را میتوان به شکلِ «وَ»یِ دو شرط زیر نوشت.
\begin{array}{l}
u-v\leq -\varepsilon+Ma\\
u-v\geq\varepsilon-(1-a)M
\end{array}
که $\varepsilon$ را باید عدد مثبت خیلی کوچکی انتخاب کنید که در اینجا که اختلاف دو عدد ممکن (دو رقم) از یک واحد کمتر نمی‌شود مثلا نیم مقدار مناسبی است و $M$ نیز باید عدد بزرگی باشد که در اینجا که رقم‌ها حداکثر ۸ هستند عدد ۱۰ بد نیست. پس $\varepsilon$ و $M$ را خودمان انتخاب می‌کنیم و ثابت هستند ولی $a$ یک متغیر بولی جدید است که به پرسش افزوده‌ایم به این نوع متغیرها «متغیرهای کمکی» می‌گوئيم. اضافه شدنشان می‌تواند جستجو برای پاسخ را پرهزینه‌تر کند (از نظر زمان و پیچیدگی و غیره) ولی هزینه‌ای است که برای تبدیل شرط‌های بهینه‌سازی در حال پرداخت هستیم. پس اکنون شکل زیر یک هم‌ارز از بین هم‌ارزهای ممکن برای پرسش اصلی این پست ولی در چهارچوب بهینه‌سازی صحیح خطی است.
$$
\begin{array}{l}
\min\qquad 1000x_8+1000x_4+100x_7+100x_3+10x_6+10x_2+x_5+x_1\\
\text{s.t. }\qquad\begin{cases}
x_i-x_j+0.5-10a_{i,j}\leq 0\;:\;1\leq i\leq 7,\;i+1\leq j\leq 8\\
x_i-x_j-0.5+10-10a_{i,j}\leq 0\;:\;1\leq i\leq 7,\;i+1\leq j\leq 8\\
x_i-1\geq 0\;:\;1\leq i\leq 8\\
x_i-8\leq 0\;:\;1\leq i\leq 8\\
a_{i,j}\text{ boolean }\;:\;1\leq i\leq 7,\;i+1\leq j\leq 8\\
x_i\text{ integer }\;:\;1\leq i\leq 8
\end{cases}
\end{array}
$$
دستورهای آمادهٔ نرم‌افزار Maple خیلی برای حل این مسأله مناسب نیستند (دست‌کم نسخهٔ ۲۰۲۰ این‌گونه است). برای نمونه می‌توانید از دستور LPSolve از بستهٔ Optimization استفاده کنید.
st := time[real]();
LPSolve(1000*x[8] + 100*x[7] + 10*x[6] + x[5] + 1000*x[4] + 100*x[3] + 10*x[2] + x[1], {seq(seq(`<=`(x[i] - x[j] + 0.5 - 10*a[i, j], 0), j = i + 1 .. 8), i = 1 .. 7), seq(seq(0 <= ((x[i] - x[j] - 0.5) + 10) - 10*a[i, j], j = i + 1 .. 8), i = 1 .. 7), seq(1 <= x[i], i = 1 .. 8), seq(x[i] <= 8, i = 1 .. 8)}, assume = integer, binaryvariables = {seq(seq(a[i, j], j = i + 1 .. 8), i = 1 .. 7)});
time[real]() - st;
حدود ۶ و نیم ثانیه بر روی رایانه‌ای که این کد را اجرا کردم زمان برد و در آخر پیام خطای زیر را داد:
Error, (in Optimization:-LPSolve) maximal depth, 54, of branch and bound search is too small; use depthlimit option to increase depth
حتی با افزایش depthlimit تا ۳۰۰۰ نیز مشکل حل نمی‌شود. اما اگر کران بالای رقم‌ها را به جای ۸ عدد ۹ بگذاریم که در حالت پرسش ما در پاسخ تغییری ایجاد نمی‌کند، آنگاه با مقدار ۱۰۰۰ برای depthlimit به یک پاسخ می‌رسد که اتفاقا پاسخ درست نیست.
st := time[real]();
LPSolve(1000*(x[8] + x[4]) + 100*(x[7] + x[3]) + 10*(x[6] + x[2]) + x[5] + x[1], {seq(seq(`<=`(x[i] - x[j] + 0.5 - 10*a[i, j], 0), j = i + 1 .. 8), i = 1 .. 7), seq(seq(0 <= ((x[i] - x[j] - 0.5) + 10) - 10*a[i, j], j = i + 1 .. 8), i = 1 .. 7), seq(1 <= x[i], i = 1 .. 8), seq(x[i] <= 9, i = 1 .. 8)}, assume = integer, binaryvariables = {seq(seq(a[i, j], j = i + 1 .. 8), i = 1 .. 7)}, depthlimit = 1000);
time[real]() - st;
پاسخی که می‌دهد عبارت است از
$$(x_1,\cdots,x_8)=(1,3,5,6,2,7,4,8),\;y_1+y_2=4104$$
این پاسخ در شرایط مدل بهینه‌سازی‌مان صدق می‌کند ولی کمینهٔ مطلق تابع هدف نیست، لذا الگوریتم استفاده شده در یک کمینهٔ نسبی در مشبکهٔ ایجاد شده بوسیلهٔ شرط‌ها به تله افتاده‌است.
جالب‌تر اینکه اگر ضرایب تابع هدف را فاکتور بگیرید Maple در یک پاسخ نادرست دیگر به تله می‌افتد!
st := time[real]();
LPSolve(1000*(x[8] + x[4]) + 100*(x[7] + x[3]) + 10*(x[6] + x[2]) + x[5] + x[1], {seq(seq(`<=`(x[i] - x[j] + 0.5 - 10*a[i, j], 0), j = i + 1 .. 8), i = 1 .. 7), seq(seq(0 <= ((x[i] - x[j] - 0.5) + 10) - 10*a[i, j], j = i + 1 .. 8), i = 1 .. 7), seq(1 <= x[i], i = 1 .. 8), seq(x[i] <= 9, i = 1 .. 8)}, assume = integer, binaryvariables = {seq(seq(a[i, j], j = i + 1 .. 8), i = 1 .. 7)}, depthlimit = 1000);
time[real]() - st;
این بار پاسخ داده‌شده بوسیلهٔ Maple1 پاسخ زیر است.
$$(x_1,\cdots,x_8)=(1,4,6,5,2,3,7,8),\;y_1+y_2=3843$$
پس می‌بینید که Maple به سبکی که الآن برنامه‌نویسی برای این نوع بهینه‌سازی شده‌است در پاسخ‌های موضعی می‌تواند به تله بیفتد. ولی پاسخ @mdardah هم در شرایط مدل بهینه‌سازی صدق می‌کند و هم کمینهٔ اکید است پس پاسخ این مدل بهینه‌سازی نیز همان است. می‌توانید به یک کتاب پیرامون بهینه‌سازی صحیح خطی مراجعه کنید و یکی از الگوریتم‌های معرفی شده در آنجا را خودتان بر روی این مدل پیاده کنید تا به پاسخ اصلی برسید. ولی دوباره تأکید می‌کنم که استفاده از بهینه‌سازی صحیح خطی بهترین راه برای این پرسش نیست، صرفا یکی از راه‌های ممکن است.
