تولید تمام جواب های بهینه در CPLEX

پارامترهای کنترل تولید جواب در CPLEX

شمارش تعداد جواب‌های بهینه بالاخص زمانی که مساله دارای جواب بهینه چندگانه است از اهمیت خاصی برخوردار است. اهمیت این موضوع در مسایل بهینه‌سازی ترکیبیاتی Combinatorial Optimization یا برنامه‌ریزی عدد صحیح Integer Programming بیشتر احساس می‌شود؛ مخصوصا زمانی که تعداد جواب‌های بهینه نامزد بسیار زیاد بوده و شناسایی این مورد باعث حذف بخش عمده‌ای از فضای شدنی شده و توسعه قواعد غلبه Dominance Rules می‌شود.

یکی از مشهورترین مسایل مکان‌یابی و تخصیص مساله پوشش مجموعه Set Covering است. در این مساله، مجموعه‌ای از مشتری‌ها با تقاضای مشخص برای خدمات و کالاها وجود دارند که باید توسط تعدادی تسهیل خدمت داده شوند. این مساله با هدف کمینه کردن هزینه‌های پوشش (تعداد مجموعه‌ها) مدل‌سازی می‌گردد.

$$ \begin{alignat}{2}
&&\text{minimize} \quad & \sum_{s \in S} x_s \\
&&\text{subject to} \quad & \sum_{s \in S} a_{s,s’} x_s \geq 1,\quad \forall s’\in S, \\
&& & x_s \in \{0,1\},\quad \forall s\in S.
\end{alignat} $$

بدین منظور ابتدا مدل ریاضی بالا به صورت زیر کدنویسی می‌گردد.

{string} ind ={"A","B","C","D","E","F"};
int A[ind][ind] = [[1,1,0,1,0,0],[1,1,0,1,0,0],[0,0,1,0,1,1],[1,1,0,1,1,0],[0,0,1,1,1,0],[0,0,1,0,0,1]];

dvar boolean x[ind];

minimize
  sum (j in ind) x[j];

subject to { 
forall(i in ind)
   sum(j in ind)
     A[i][j]*x[j] >= 1;
 }

سپس یک بلوک پس پردازنده Postprocessing را پس از این کد قرار می‌دهیم. به کمک این بلوک، جواب‌ها در پنل scripting log نشان داده می‌شوند.

execute
{
writeln(x);
}

سپس از یک بلوک کنترل جریان Control Flow جهت کنترل نحوه تولید جواب‌ها در ادامه کد اضافه می‌کنیم.

چگونه این کار انجام می‌شود؟
0
نظر شما چیست؟x

main
{
  thisOplModel.generate();
  cplex.solnpoolintensity=4;
  cplex.solnpoolagap=0;
  cplex.populatelim=64;
  cplex.populate();
var nsolns = cplex.solnPoolNsolns;
writeln("n sol ",nsolns);
for(var s = 0; s < nsolns; s++)
{
thisOplModel.setPoolSolution(s);
thisOplModel.postProcess();
}
cplex.clearModel();
}

پارامتر solnpoolintensity بین تولید جواب‌های بهینه و زمان حل تعادل برقرار می‌کند. هرچه مقدار این پارامتر بیشتر باشد، تعداد جواب‌های تولید شده بیشتر و متعاقبا زمان حل زیادتر خواهد بود. مقدار این پارامتر عدد صحیحی است بین عدد صفر تا چهار. همانطور که در پنل Scripting log زیر ملاحظه می‌کنید، تعداد چهار جواب یافت شده که مقادیر متغیر x به ترتیب نشان داده شده است.

0 Comments
Inline Feedbacks
View all comments