LAGRANGIAN RELAXATION AND PEGGING TEST FOR LINEAR ORDERING PROBLEMS(<Special Issue>SCOPE (Seminar on Computation and OPtimization for new Extensions))
-
- Sukegawa Noriyoshi
- University of Tsukuba
-
- Yamamoto Yoshitsugu
- University of Tsukuba
-
- Zhang Liyuan
- University of Tsukuba
書誌事項
- タイトル別名
-
- LAGRANGIAN RELAXATION AND PEGGING TEST FOR LINEAR ORDERING PROBLEMS
この論文をさがす
説明
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 in 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.
収録刊行物
-
- 日本オペレーションズ・リサーチ学会論文誌
-
日本オペレーションズ・リサーチ学会論文誌 54 (4), 142-160, 2011
公益社団法人 日本オペレーションズ・リサーチ学会
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1390001204109907712
-
- NII論文ID
- 110008897239
-
- NII書誌ID
- AA00703935
-
- ISSN
- 21888299
- 04534514
-
- NDL書誌ID
- 023392086
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- NDLサーチ
- Crossref
- CiNii Articles
- OpenAIRE
-
- 抄録ライセンスフラグ
- 使用不可