الگوریتم آزادسازی لاگرانژ در گروبی Gurobi

 

آزاد سازی لاگرانژ Lagrangian Relaxation یکی از تکنیک‌های ابتکاری رایج در حل مسائل بهینه‌سازی ترکیبیاتی است. این الگوریتم که مبتنی بر قضیه لاگرانژ است با آزادسازی همه یا برخی از محدودیت‌های مسئله، اطلاعاتی از جواب بهینه مسئله اصلی فراهم می‌کند. در این پست قصد داریم تکنیک آزادسازی لاگرانژ را بر روی مسئله تخصیص تعمیم‌یافته Generalized Assignment Problem به کمک نرم‌افزار Gurobi در پلتفرم پایتون پیاده‌سازی نماییم. هدف این مسئله بیشینه نمودن میزان تخصیص هر تسهیل به گره تقاضا به شرط محدودیت‌های متناظر است.

$$ \textbf{maximize} \quad \textstyle{\sum}_i \textstyle{\sum}_j c_{ij}x_{ij} \\ \textbf{subject to} \quad \textstyle{\sum}_i x_i \le 1, \quad \forall i \\ \textstyle{\sum}_i a_{ij}x_{ij} \le b_j, \quad \forall j \\ x_i \in \{0,1\} $$

توجه !
جهت نصب و یکپارچه‌سازی نرم‌افزار Gurobi با پلتفرم پایتون به این پست مراجعه نمایید.

در الگوریتم آزادسازی لاگرانژ ابتدا محدودیت (هایی) که ارضای آن‌ها سخت‌تر هستند را با ضریبی مشخص به تابع هدف اضافه نمونه و به کمک روش‌های زیرگرادیان subgradient در تکرارهای مختلف مقدار آن را مشخص می‌نماییم. بدیهی است که رفتار کاهش تابع هدف به‌صورت نوسانی باشد. این خلاصه‌ای از الگوریتم آزادسازی لاگرانژ است؛ مفاهیم و قضایای ارزشمندی در این مورد وجود دارد. جهت کسب اطلاعات بیشتر لطفا به منبع انتهای پست مراجعه شود.

در این مسئله محدودیت اول جهت آزادسازی انتخاب می‌شود.

به عبارتی برای عبارت \( \lambda u \) شرایط مکمل زائد بایستی برقرار باشد؛ یعنی یکی از دو متغیر \( \lambda \) یا \( u \) مقدار صفر را اخذ خواهند کرد.

$$ \textbf{maximize} \quad \textstyle{\sum}_i \textstyle{\sum}_j c_{ij}x_{ij} – \textstyle{\sum}_i \lambda_i u_i \\ \textbf{subject to} \quad u _i = 1- \textstyle{\sum}_i x_i, \quad \forall i \\ \textstyle{\sum}_i a_{ij}x_{ij} \le b_j, \quad \forall j \\ x_i \in \{0,1\}$$

هم‌چنین فرض می‌کنیم که در هر تکرار مقادیر متغیرهای \( \lambda \)  و گام، از روابط زیر حاصل می‌شود:

$$\textit{step} = \frac{\textit{step}}{\textit{iteration}}, \quad \lambda_i = \textbf{max} ( \lambda_i – \textit{step} \times u_i , 0)$$ 

مرحله اول

فراخوانی کتابخانه‌های اصلی گروبی و تشکیل شی‌ء مسئله از روی کلاس Model

from gurobipy import GRB, Model
model = Model(‘LR of Generalized Assignment Problem’)

 

مرحله دوم

وارد کردن پارامترها و داده‌های مسئله مطابق فرمت زیر

b = [x, x, x, x, x, x, x, x]
c = [
    [x, x, x, x, x],
    [x, x, x, x, x],
    [x, x, x, x, x],
    [x, x, x, x, x],
    [x, x, x, x, x],
    [x, x, x, x, x]
]

a = [
    [x, x, x],
    [x, x, x],
    [x, x, x],
    [x, x, x],
    [x, x, x]
]

 

مرحله سوم

اخذ اطلاعات ابعادی جهت تشکیل مقادیر ثابت و مجموعه‌ها

NB_fac = len(a) #number of facilities
NB_dem = len(b) #number of demand nodes
lambda = [2]*NB_fac
fac = range(NB_fac)
dem = range(NB_dem)

 

مرحله چهارم

تعریف متغیرهای مسئله

x = model.addVars(NB_fac,NB_dem,vtype=GRB.BINARY)
u = model.addVars(NB_fac)

 

مرحله پنجم

تعریف محدودیت‌های مسئله (لازم به توضیح است که چون محدودیت‌های مسئله در هر تکرار ثابت است آن را وارد حلقه نمی‌کنیم.)

for i in fac:
    model.addConstr(u[i] == 1 - sum(x[i,j] for j in dem))
for j in dem:
    model.addConstr(sum(a[i][j] * x[i,j] for i in fac) <= b[j])

 

مرحله ششم

در این مرحله ضریب تابع هدف \( \lambda  \) در هر تکرار به کمک روش زیرگرادیان تغییر می‌کند.

model.modelSense = GRB.MAXIMIZE
model.setParam('OutputFlag', False)
for iter in range(1, 101):
    model.setObjective( sum( c[i][j] * x[i,j] for i in fac for j in dem) 
                      + sum ( la[i] * u[i] for i in fac) )

    model.optimize()

    print 'iteration', iter, 'obj =', model.objVal, \
        'u =', lambda, 'penalties =', [u[i].x for i in fac]

    # Test for complementary slackness
    stop = True
    eps = 10e-6
    for i in fac:
        if abs(lambda[i]) > eps and abs(u[i].x) > eps:
            stop = False
            break
    if stop:
        print 'primal feasible & optimal'
        break
    else:
        step = 1.0 / iter
        for i in fac:
            lambda[i] = max(lambda[i] - step*(u[i].x), 0.0)

 

مرحله هفتم

نمایش متغیرها و مقدار تابع هدف

print 'objective =', model.objVal
print 'x = ['
print '   ', [۱ if x[i,j].x >= 0.5 else 0 for i in fac for j in dem]
print ']'

 

کد این مسئله به همراه منابع تکمیلی در لینک‌های زیر بارگذاری شده است.

این محتوا برای اعضا قابل مشاهده است. لطفا وارد شوید

دیدگاه بگذارید