LAGRANGIAN RELAXATION AND PEGGING TEST FOR LINEAR ORDERING PROBLEMS(<Special Issue>SCOPE (Seminar on Computation and OPtimization for new Extensions))

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

著者

• Yamamoto Yoshitsugu

  University Of Tsukuba

• Sukegawa Noriyoshi

  University Of Tsukuba

• Zhang Liyuan

  University of Tsukuba

関連論文

• A NOTE ON A THEOREM OF CONTINUUM OF ZERO POINTS
• A PARAMETRIC SUCCESSIVE UNDERESTIMATION METHOD FOR CONVEX PROGRAMMING PROBLEMS WITH AN ADDITIONAL CONVEX MULTIPLICATIVE CONSTRAINT
• OUTER APPROXIMATION METHOD FOR THE MINIMUM MAXIMAL FLOW PROBLEM
• RANKING BY RELATIONAL POWER BASED ON DIGRAPHS
• A STUDY ON LINEAR INEQUALITY REPRESENTATION OF SOCIAL WELFARE FUNCTIONS
• LAGRANGIAN RELAXATION AND PEGGING TEST FOR LINEAR ORDERING PROBLEMS(SCOPE (Seminar on Computation and OPtimization for new Extensions))

スポンサーリンク