|
 |
Details of project |
|
|
| Identifier |
91302 |
| Type |
PD |
| Principal investigator |
Gazdag-Tóth, Boglárka |
| Title in Hungarian |
Globális optimalizálási módszerek elhelyezési feladatok megoldására |
| Title in English |
Global optimization methods for solving location problems |
| Keywords in Hungarian |
globális optimalizálás, MINLP, intervallum aritmetika, DC optimalizálás, elhelyezési problémák |
| Keywords in English |
global optimization, MINLP, interval arithmetic, DC optimization, location problems |
| Discipline |
| Mathematics (Council of Physical Sciences) | 50 % | | Ortelius classification: Operations research | | Information Technology (Council of Physical Sciences) | 30 % | | Ortelius classification: Applied informatics | | Economics (Council of Humanities and Social Sciences) | 20 % | | Ortelius classification: Economics |
|
| Panel |
Mathematics and Computing Science |
| Department or equivalent |
Department of Differential Equations (Budapest University of Technology and Economics) |
| Starting date |
2016-02-01 |
| Closing date |
2019-06-30 |
| Funding (in million HUF) |
3.463 |
| FTE (full time equivalent) |
2.21 |
| state |
closed project |
Summary in Hungarian A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
A projekt fő célja hatékony és megbízható algoritmusok fejlesztése nehéz, folytonos illetve kevert egészértekű nemlineáris programozási (MINLP) feladatok megoldására.
A versenyző vállalatok területén célunk vizsgálni különböző új boltválasztási szabályokat, amik jól illeszkednek a valós vásárlói választáshoz. Egyrészről, megbízható algoritmusokat tervezünk a multi-determinisztikus és részben valószínűségi vásárlói szabályokkal adott elhelyezési problémákhoz, másrészt az így kapott eredményeket összevetjük a valószínűségi szabállyal kapott eredményekkel. Egy másik fontos célunk a minőség mint diszkrét változó kezelése, amely nehéz algoritmikus problémákat vet fel.
A Huff-féle Stackelberg feladat megoldására megbízható algoritmust keresünk gráfon értelmezett esetben, ahol célunk a profit maximalizálása működési költségek mellett. További célkitűzésünk az eredmények kiterjesztése minőség változóval nehezített esetre, illetve egyensúlyi helyzetek keresése minőségi játék esetére.
Lefedési problémák esetén célunk egy olyan hatékony módszer kifejlesztése, ami folytonos kereslet mellett is képes befoglalni a globális optimumot. Ehhez éles korlátok megadása, és a feladat diszkrét és folytonos részének hatékony összekapcsolása szükséges. Célunk a kapott algoritmus kiterjesztése a p-Huff feladat megoldására hálózaton, ami hasonló adatszerkezetet igényel.
Végül a síkbeli kapacitásos lefedési feladat megoldása jelent nagy kihívást, hiszen itt egy adott vállalathoz tartozó lefedés kiszámítása már önmagában nemtriviális. A paraméter kiválasztási feladat esetén maguknak a részfeladatoknak a definiálása, és korlátok konstruálása is igen nehéz de érdekesnek ígérkező feladat.
Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
A kutatási projekt során olyan MINLP problémákat kívánunk vizsgálni, amelyekre még nem született egzakt megoldás, és amelyekre a gyakorlati szakemberek felől nagy igény mutatkozik. A MINLP feladatok általános esetben NP nehéz problémák, így megfelelő speciális tulajdonságaik kihasználása nélkül nem konstruálhatóak hatékony megbízható algoritmusok.
A megbízható módszerek segítségével megoldott problémák lehetőséget biztosítanak a felállított modellek vizsgálatára, azok továbbfeljesztésére, illetve nem utolsó sorban gyakorlati problémák megoldására az adott területeken. A megkonstruált algoritmusok vizsgálatával azok általánosabb feladatosztályokra kiterjeszthetők lehetnek, ami nagy előrelépést jelentene.
A feladatok megoldása során választ kaphatunk több érdekes kérdésre.
Egy gyakorlati helyzetben melyik vásárlói boltválasztói szabályt érdemes használni? Mikor ad az eltérő modellezés teljesen eltérő eredményeket? Mekkora változást hoz a minőségi változó diszkrét feltételezése az általánosított folytonos helyett? Mennyire nehezíti ez meg a megoldó algoritmust?
Van-e egyértelmű megoldása a Huff-féle Stackelberg feladatnak működési költség figyelembevétele mellett? Hogyan lehet egy bi-level feladatot hatékonyan megoldani?
Mi a hatása a kereslet folytonos modellezésének? Van-e jelentősége a diszkretizált modell mellett? Milyen eloszlástól független korlátok adhatók meg lefedési és p-Huff probléma esetén? Hogyan érdemes a gráfokon részfeladatokat definiálni?
Meghatározható-e a paraméterek egy lényeges részhalmaza függvényillesztési feladatoknál? Lehetséges több ilyen egymástól nagyon különböző halmaz létezése?
Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
Manapság MINLP és globális optimalizálási algoritmusokra számos tudományterületen nagy szükség van, így az eredmények számottevő alkalmazása várható, hiszen jelentős hatékonyságnövekedés esetén nagyobb, komplexebb feladatok megoldására is lehetőség nyílik. A versenyhelyzetben lévő vállalatláncok esetén a profit pár százalékos növekedése is igen jelentős többletbevételt jelent, így ezeknek a problémáknak a megfelelő modellezése és optimális megoldása nagyon fontos kutatási terület mind elméleti mind gyakorlati szempontból.
A további problémák megoldása is konkrét gyakorlati feladatok megoldásához vezet, például: hipermarketek és szemétlerakók elhelyezése, kórházak, mentőállomások helyének meghatározása, illetve függvény illesztésnél a fontos paraméterek detektálása sok alkalmazásban lenne elengedhetetlen.
A kutatás elméleti jelentősége, hogy ha a kitűzött nehéz feladatokat hatékonyan meg tudjuk oldani, akkor mód nyílik még nehezebb, ill. jelenleg nem kezelhető feladatok hatékony és megbízható megoldására.
Konkrétabban, a hálózatokon értelmezett feladatok megoldásával lehetőség nyílik általánosan megfogalmazott hálózati problémák megoldására, mivel ezekre csak nagyon speciális esetekben van megoldás jelenleg. Hasonlóan, folytonos keresletű modellek csak néhány egyszerűbb eloszlás mellett lettek vizsgálva, így ha célkitűzéseinket elérve sikerülne eloszlástól független módszereket kidolgoznunk, a kapott módszerek alapvetően más folytonos eloszlással rendelkező feladatokra is kiterjeszthetőek lennének. Ez szintén óriási lépés lehet, hiszen a valósághűbb folytonos eloszlás jelenleg elhanyagolt az így adódó feladatok nehézsége miatt.
A paraméter kiválasztási feladat megoldásával lehetőségünk nyílna kiszűrni azokat az adatokat, amelyek igazán fontosak a modell illesztés során, ezzel egy sokkal letisztultabb képet adva a fontos adatokról, paraméterekről. Ezen eredmények nagy előrelépést jelentenének a tágabb adattudomány terén is.
A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
A pályázatomban több még nyitott elhelyezési feladat megoldását tűztem ki célul, ahol a megoldáshoz használt módszerek segítségével más feladatok megoldására is lehetőség nyílhat. A megoldandó feladatoknak rengeteg gyakorlati alkalmazása is van, így a problémák megbízható megoldása számottevő érdeklődést válthat ki.
A vizsgálni kívánt problémák a következők. Versenyző vállalatok elhelyezési problémája a síkon, ahol
• a vásárlók boltválasztási szabálya eltér az irodalomban használt egyszerűbb szabályoktól a valóság pontosabb leírásához
• az új vállalat minősége, mint diszkrét változó adott, ezzel egészértékű változót hozva az eddig folytonos feladatba.
Elhelyezési feladatok hálózatokon, ahol
• versenyző vállalatok egymást követve helyezik el új telephelyeiket, és az első, vezető vállalat profitjának maximalizálása a cél a követő elhelyezése után, aki saját profitját maximalizálja
• egy versenyző vállalat egyszerre több telephelyének elhelyezése, maximalizálva a vállalat piaci részesedését
• több nem versenyző vállalat maximális fedését keressük adott sugár, és folytonos eloszlású kereslet mellett.
Vizsgálni szeretnénk még egy síkon vett lefedési problémát, ahol a vállalatoknak maximális kapacitása adott, és a kereslet folytonos eloszlással adott.
Végül egy paraméter kiválasztási feladat megoldása a cél, ahol adott pontokra függvény illesztéshez szeretnénk kiválasztani a fontos paramétereket.
| Summary Summary of the research and its aims for experts
Describe the major aims of the research for experts.
The main aim of the project is to develop efficient and reliable algorithms for solving hard, continuous and mixed integer nonlinear programming (MINLP) problems.
For competitive facility location problem we aim to study the different new customer choice rules, which fits much better to the real choice of the costumers. In the one hand, we plan to develop exact algorithms for both the multi-deterministic and the partially probabilistic customer rule based location problems. On the other hand we aim to compare the achieved results with the ones using classical rules to draw some conclusions. Another important aim is to handle the quality as a discrete variable, that brings up methodological problems.
For the Huff-type Stackelberg problem we seek a reliable method on networks, maximizing the profit of the facilities, where operational costs are given. Moreover, we aim to extend the results to the case where the quality is also a variable. Finding equilibrium for the quality game is also an important plan.
In case of covering problems our aim is to develop an efficient method which is able to enclose the global optimum with demand continuously distributed. That needs tight bounds and a powerful connection of the continuous and discrete parts of the problem. We aim to extend the reached results for the p-facility Huff problem on networks, since it will need a similar data structure.
Finally, the capacitated covering problem is a big challenge, since already the computation of the covering for a given facility is not trivial. For the parameter selection problem, the definition of the sub-problems and bound construction is a hard, but very interesting problem.
What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
In this research project we want to investigate MINLP problems that are not solved yet exactly, and for which there is considerable demand from engineers. MINLP problems are NP-hard in the general case, thus we cannot develop efficient methods without using their special properties.
Problems solved using reliable methods give opportunity to study the given models, their improvements, and most importantly to solve real-life practical problems on the given field. With the study of the developed algorithms, those may be generalized to wider class of problems, taking a huge step in the research field.
Solving the proposed problems we can get answers to several interesting questions. Just to mention a few:
What customer choice rule should be used in a given real-life situation? When gives the different models completely different results? How much change is caused by the assumption of the discrete quality variable? How much harder the problem gets with this assumption?
Is there an unambiguous solution of the Huff-like Stackelberg problem assuming operational costs? How to solve efficiently such a bi-level problem?
What is the impact of modelling continuously distributed demand? Is it significantly better than the discretized model? What kind of bounds can be constructed independently from the distribution of the demand? How to define subproblems on networks efficiently?
Is it possible to determine a set of important parameters for data fitting? Is it possible that more such sets of parameters exist which are very different?
What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
Nowadays there are huge demand for methods in MINLP and global optimization in various fields of science, thus several application of the results can be expected. Having more efficient and new algorithms, larger and more complex problems can be solved.
In case of competitive facility location, the improvement of the profit even with a few percent may results in huge change in the income. Therefore the adequate modelling of these problems and their optimal solution is a very important research question both for theoretical and practical point of view. The rest of the problems leads also to the solution of practical problems. Optimal location of hypermarkets, landfills, hospitals, ambulance stations, as well as applications of data fitting with the knowledge of important parameters is crucial.
The theoretical interest of the proposed research is opening the way to solve harder and still untreatable problems efficiently and reliably, having solved efficiently the given hard optimization problems. In particular, solving the given problems defined on networks may lead to the solution of general network problems, since only special non-linear network problems are solved until now. Similarly, models with continuously distributed demand has been studied only for a few special case, thus if we succeed in our object to develop methods independent of the distribution of the demand, the achieved results could be extended for other different problems with continuous demand. It would be also a huge step, since the more realistic continuous demand is quite neglected because of its difficulty until now.
Solving the parameter selection problem it would be possible to filter out those parameters, which are really important in data fitting, getting a clarified view from the important data/parameters. These results would give a big improvement for the wider data science field too.
Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
In the present project I have proposed several open problems in location analysis to be solved, with the aim of developing methods which might be used for a wider class of problems as well. The problems to be solved has many practical application, therefore reliable solution of these problems may have considerable interest.
We will focus on the following problems. Competitive facility location problem on the plane, where
• the used customer choice rule is more realistic compared to the simple ones used in the literature
• the quality of the new facility is discrete, bringing an integer variable to the so far continuous problem.
Location problems on networks, where
• the competitors locate their new facilities sequentially, with the leader facility optimizing its profit after the location of the follower, who maximize its own profit
• locating more than one facilities of a chain in a competitive environment, maximizing the market share of the chain
• covering of many facilities is maximized given a covering radius and continuously distributed demand.
We also aim to study a covering problem on the plane, where facilities has capacities and continuous demand is assumed. Finally, an object is to find the important parameters in data fitting, where the fitted functions are overparameterized.
|
|
|
|
|
