جواب تقريبي مسائل mp-MILP با استفاده از آزادسازي مك كورميك قطعه اي تظريف شده

Approximate Answer to MP-MILP Problems Using McCormic Release of Modified Components

ﭼﮑﯿﺪه ﻧﻈﺮﯾﻪ ﺑﺮﻧﺎﻣﻪرﯾﺰي ﭼﻨﺪﭘﺎراﻣﺘﺮﯾﮏ اﺑﺰار ارزﺷﻤﻨﺪي ﺑﺮاي ﺗﺼﻤﯿﻢﮔﯿﺮي ﺗﺤﺖ ﻋﺪم ﻗﻄﻌﯿﺖ ﻣﯽﺑﺎﺷﺪ و ﺣﯿﻄﻪ ﻓﻌﺎﻟﯽ از ﺗﺤﻘﯿﻘﺎت را ﺑﻪ ﺧﻮد اﺧﺘﺼﺎص داده اﺳﺖ. اﮔﺮﭼﻪ ﺑﻬﯿﻨﻪﺳﺎزي ﭼﻨﺪ ﭘﺎراﻣﺘﺮﯾﮏ ﺑﺎ ﻋﺪم ﻗﻄﻌﯿﺖ در ﺿﺮاﯾﺐ ﺗﺎﺑﻊ ﻫﺪف و ﻣﻘﺎدﯾﺮ ﺳﻤﺖ راﺳﺖ ﻣﺤﺪودﯾﺖﻫﺎ ﺑﺴﯿﺎر ﻣﻮرد ﺗﻮﺟﻪ واﻗﻊ ﺷﺪه و روشﻫﺎي ﮔﻮﻧﺎﮔﻮﻧﯽ ﺑﺮاي ﺣﻞ آنﻫﺎ ﺗﺎﮐﻨﻮن اراﺋﻪ ﺷﺪه اﺳﺖ، ﻋﺪم ﻗﻄﻌﯿﺖ در ﻣﺎﺗﺮﯾﺲ ﺿﺮاﯾﺐ )ﺑﻪ ﻋﺒﺎرﺗﯽ ﺳﻤﺖ ﭼﭗ( ﮐﻤﺘﺮ ﻣﻮرد ﺗﻮﺟﻪ ﻗﺮار ﮔﺮﻓﺘﻪ اﺳﺖ. در اﯾﻦ ﮐﺎر ﯾﮏ روش ﺟﺪﯾﺪ ﺑﺮاي ﺣﻞ ﻣﺴﺎﺋﻞ ﭼﻨﺪﭘﺎرﻣﺘﺮﯾﮏ ﻋﺪد ﺻﺤﯿﺢ ﻣﺨﺘﻠﻂ )mp-MILP( ﺑﺎ ﻋﺪم ﻗﻄﻌﯿﺖ در ﻣﺤﺪودﯾﺖ ﻫﺎ اراﺋﻪ ﺷﺪه اﺳﺖ. اﯾﻦ روش ﺷﺎﻣﻞ دو ﻣﺮﺣﻠﻪ اﺳﺖ ﮐﻪ در ﻣﺮﺣﻠﻪ اول ﺑﺎ اﺳﺘﻔﺎده از آزادﺳﺎزي ﻣﮏﮐﻮرﻣﯿﮏ ﺗﻈﺮﯾﻒ ﺷﺪه ﮐﺮانﻫﺎي ﺟﻤﻼت دوﺧﻄﯽ ﺑﻬﺒﻮد ﻣﯽﯾﺎﺑﺪ و در ﻣﺮﺣﻠﻪ دوم ﺑﺮﭘﺎﯾﻪ اﯾﻦ ﮐﺮانﻫﺎي ﺑﻬﺒﻮد ﯾﺎﻓﺘﻪ و ﺗﺨﻤﯿﻦ ﺟﻤﻼت دوﺧﻄﯽ، ﻣﺪل ﺗﻘﺮﯾﺒﯽ از mp-MILP ﺑﺪﺳﺖ آﻣﺪه اﺳﺖ. در اﻧﺘﻬﺎ ﮐﺎراﯾﯽ روش ﺗﻘﺮﯾﺒﯽ اراﺋﻪ ﺷﺪه ﺗﻮﺳﻂ دو ﻣﺜﺎل ﻣﻮرد ﺑﺮرﺳﯽ ﻗﺮار ﮔﺮﻓﺘﻪ اﺳﺖ. ﺑﺮاي اﻧﺠﺎم اﯾﻦ ﮐﺎر در اﻓﺰارﻫﺎي ﻣﺘﻔﺎوت ﺗﻘﺮﯾﺐ ﻣﺴﺎﻟﻪ اﻧﺠﺎم ﺷﺪه و ﻣﯿﺰان ﻣﺤﺎﺳﺒﺎت ﻻزم ﺑﺮاي ﺣﻞ آنﻫﺎ ﻣﻘﺎﯾﺴﻪ ﮔﺮدﯾﺪه اﺳﺖ.

Multi-parametric programming theory is a valuable tool for decision making under uncertainty and has been an active area of research. Although multi-parametric programming with uncertainty in the objective function coefficients and right-hand side of constraints has been extensively discussed and various methods have been proposed for this, uncertainty in the coefficients matrix (i.e. left-hand side uncertainty) have been less considered. In this work, a new method for solving multi-parametric mixed-integer linear problems (mp-MILP) with uncertainty in constraints is presented. This procedure consists of two steps, which in the first step, the bounds of the bilinear terms are improved by using tightening piecewise McCormick relaxations and secondly, based on these improved bounds and estimating bilinear terms, an approximate model of mp-MILP is obtained. The performance of the presented method is investigated by two examples. To do this, the approximation of the problem has been done in different partitioning factors and computational requirements to solve them have been compared.