Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Method of Digraphs for Multi-dimensional Screening. / Kokovin, Sergey; Nahata, Babu.
в: Annals of Operations Research, Том 253, № 1, 01.06.2017, стр. 431-451.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Method of Digraphs for Multi-dimensional Screening
AU - Kokovin, Sergey
AU - Nahata, Babu
N1 - Publisher Copyright: © 2016, Springer Science+Business Media New York.
PY - 2017/6/1
Y1 - 2017/6/1
N2 - We study a general model of multi-dimensional screening for discrete types of consumers without the single-crossing condition or any other essential restrictions. Such generality motivates us to introduce graph theory into optimization by treating each combination of active constraints as a digraph. Our relaxation of the constraints (a slackness parameter) excludes bunching and cycles among the constraints. Then, the only possible solution structures are rivers, which are acyclic rooted digraphs, and the Lagrange multipliers can be used to characterize the solutions. Relying on these propositions, we propose and justify an optimization algorithm. In the experiments, its branch-and-bound version with a good starting plan shows fewer iterations than a complete search among all rivers.
AB - We study a general model of multi-dimensional screening for discrete types of consumers without the single-crossing condition or any other essential restrictions. Such generality motivates us to introduce graph theory into optimization by treating each combination of active constraints as a digraph. Our relaxation of the constraints (a slackness parameter) excludes bunching and cycles among the constraints. Then, the only possible solution structures are rivers, which are acyclic rooted digraphs, and the Lagrange multipliers can be used to characterize the solutions. Relying on these propositions, we propose and justify an optimization algorithm. In the experiments, its branch-and-bound version with a good starting plan shows fewer iterations than a complete search among all rivers.
UR - http://www.scopus.com/inward/record.url?scp=84988649050&partnerID=8YFLogxK
U2 - 10.1007/s10479-016-2320-3
DO - 10.1007/s10479-016-2320-3
M3 - Article
AN - SCOPUS:84988649050
VL - 253
SP - 431
EP - 451
JO - Annals of Operations Research
JF - Annals of Operations Research
SN - 0254-5330
IS - 1
ER -
ID: 10321238