2011年
Lagrangian relaxation and pegging test for linear ordering problems
Journal of the Operations Research Society of Japan
- ,
- ,
- 巻
- 54
- 号
- 4
- 開始ページ
- 142
- 終了ページ
- 160
- 記述言語
- 英語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- DOI
- 10.15807/jorsj.54.142
- 出版者・発行元
- Operations Research Society of Japan
We develop an algorithm for the linear ordering problem, which has a large number of applications such as triangulation of input-output matrices, minimizing total weighted completion time one-machine scheduling, and aggregation of individual preferences. The algorithm is based on the Lagrangian relaxation of a binary integer linear programming formulation of the problem. Since the number of the constraints is proportional to the third power of the number of items and grows rapidly, we propose a modified subgradient method that temporarily ignores a large part of the constraints and gradually adds constraints whose Lagrangian multipliers are likely to be positive at an optimal multiplier vector. We also propose an improvement on the ordinary pegging test by using the problem structure. © The Operations Research Society of Japan.
- ID情報
-
- DOI : 10.15807/jorsj.54.142
- ISSN : 0453-4514
- SCOPUS ID : 84880421114