بهینه سازی استوار در گروبی GUROBI

 

در این پست ابتدا یک مساله اسباب‌بازی (!) یعنی کوله پشتی knapsack را تحت مجموعه عدم قطعیت بودجه‌ای budgeted uncertinay set (برتسیماس و سیم ۲۰۰۴) مدل‌سازی کرده و سپس مدل استوار شده را به کمک پارامتر بودجه تحلیل حساسیت می‌نماییم.

مدل ریاضی استاندارد مساله کوله پشتی به فرم زیر را در نظر بگیرید:

$$ \textbf(P): \max_{x \in \mathbb{Z}_+} \sum_{i \in N} c_i x_i \\ \sum_{i \in N} w_i x_i \leq C $$

در ادامه فرض می‌شود که پارامتر وزن \( w \) غیر قطعی بوده و در بازه \( [\bar{w},\bar{w}+\hat{w}]  \) نوسان دارد. به عبارت دقیق‌تر،

$$ U^\Gamma = \left \{ \xi \in [0,1]^{|N|} \left | \widetilde{w}_i=\bar{w}_i + \xi_i \hat{w}_i , \; \sum_{i \in N} \xi_i = \Gamma \right. \right \} $$

همزاد استوار robust counterpart مساله P به فرم زیر قابل بیان است:

$$ \max_{x \in \mathbb{Z}_+ ,\lambda,\tau \in \mathbb{R}_+ } \sum_{i \in N} c_i x_i \\ \sum_{i \in N} \bar{w}_i x_i + \tau \Gamma + \sum_{i \in N} \lambda_i \leq C, \\ \lambda_i + \tau \geq \hat{w_i} x_i, \; \forall i \in N $$

در ادامه مدل استوار حاصل شده را در پلتفرم پایتون به کمک کتابخانه‌های گروبی GUROBI کدنویسی نموده و حل می‌نماییم.

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

فراخوانی کتابخانه GUROBI

from gurobipy import GRB,Model

تعریف و مقداردهی پارامترها، بردارها و مجموعه‌ها

utility = [26,65,35,48,26,53,32,56,58,62] # c
weight = [27,28,16,28,24,16,19,23,29,29] # w
capacity = 120 # C
numItems = len(weight) 
items = range(numItems) # N

تعریف کلاس مساله، متغیرهای تصمیم، تابع هدف و محدودیت‌ها

problem = Model("robustKnapsack")
x = problem.addVars(numItems, vtype=GRB.INTEGER, name='x')
la = problem.addVars(numItems, name='lambda')
tau = problem.addVar(name='tau')
problem.setObjective(sum(x[i] * utility[i] for i in items), GRB.MAXIMIZE)
for i in items: 
 problem.addConstr(la[i] + tau >= .1 * weight[i] * x[i],'c2')

توجه شود که \( \hat{w}_i = 0.1\bar{w}_i \)  در نظر گرفته شده است.

افزایش پارامتر بودجه و حل

objLog = [0 for i in items]
problem.setParam('OutputFlag', 0)
for GAMMA in items:
 problem.update()
 problem.addConstr(sum(x[i] * weight[i] for i in items) + GAMMA*tau + sum(la[i] for i in items) <= capacity,'c1')
 for i in items:
  problem.addConstr(la[i] + tau >= .1 * weight[i] * x[i],'c2')
 problem.optimize()
 objLog[GAMMA]=problem.objVal
 problem.remove("You should purchase to see this section!")
 problem.remove("You should purchase to see this section!")

واضح است که پس از افزایش پارامتر بودجه، محدودیت درگیر با این پارامتر در یک تکرار اضافه و در تکرار دیگر حذف می‌شود. جهت حذف محدودیت از متد جالب getConstrByName یعنی حذف محدودیت به ازای نام محدودیت (که در این مورد string تعریف شده است) استفاده شده است. 

دستورات اختیاری جهت تولید نمودار

import matplotlib.pyplot as plt
plt.plot(objLog)
plt.ylabel('objective')
plt.xlabel('GAMMA')
del problem

 

نمودار نهایی بر حسب تغییرات پارامتر بودجه

 

واضح است که مقدار تابع هدف به تغییرات پارامتر بودجه پس از مقدار ۲ (با لحاظ تنها دو پارمتر غیرقطعی) واکنشی نشان نمی‌دهد. بنابراین حداقل مقدار پارامتر بودجه که منجر به محافظه‌کاری conservatism کامل مدل می‌شود، مقدار ۲ است.

 

شما می‌توانید با خرید این محصول (کد پایتون)، از این سایت و توسعه دهنده کد حمایت کنید.

 

مراجع

Bertsimas, D., & Sim, M. (2004). The Price of robustness. Operations Research, 52(1), 35 – 53

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