2次割当て問題への適用におけるIntegral Basis Methodの改良の提案  [in Japanese] Improving the Integral Basis Method in Application to the Quadratic Assignment Problem  [in Japanese]

Access this Article

Search this Article

Author(s)

Abstract

Integral Basis MethodはHaus,Koppe,Weismantelによって提案された,整数線形計画問題に対する新たな厳密解法である.本稿では2次割当て問題への適用を通して,Integral Basis Methodの性質を調べて,その効率を改良する方法を提案する.提案する改良は,QAPの制約式の持つ特徴を緩和に利用することである.17問のベンチマーク問題に対する実験の結果,すべての問題で反復回数が大きく減少し,11問の問題で計算時間を短縮した.これらの技法は,QAPに限らず,一般の整数線形計画問題にも応用可能であると考えられる.The Integral Basis Method is a new exact method for solving the integer linear programming problem (ILP), which is proposed by Haus, Koppe and Weismantel. In this paper, we propose some improving techniques for the Integral Basis Method, and show their appication to the Quadratic Assignment Problem (QAP). The constraints of QAP have several remarkable characteristics. One of our proposals is to use these characteristics for relaxation. Our computational experiments show that these improvement techniques work quite effectively in reducing the number of iterations for all of the 17 instances and in reducing the computation time for 11 instances. These techniques could be effectively applicable also in general ILP.

The Integral Basis Method is a new exact method for solving the integer linear programming problem (ILP), which is proposed by Haus, Koppe and Weismantel. In this paper, we propose some improving techniques for the Integral Basis Method, and show their appication to the Quadratic Assignment Problem (QAP). The constraints of QAP have several remarkable characteristics. One of our proposals is to use these characteristics for relaxation. Our computational experiments show that these improvement techniques work quite effectively in reducing the number of iterations for all of the 17 instances and in reducing the computation time for 11 instances. These techniques could be effectively applicable also in general ILP.

Journal

  • 情報処理学会論文誌数理モデル化と応用(TOM)

    情報処理学会論文誌数理モデル化と応用(TOM) 47(SIG14(TOM15)), 54-61, 2006-10-15

    Information Processing Society of Japan (IPSJ)

References:  14

Codes

  • NII Article ID (NAID)
    110004856977
  • NII NACSIS-CAT ID (NCID)
    AA11464803
  • Text Lang
    JPN
  • Article Type
    Article
  • ISSN
    1882-7780
  • NDL Article ID
    8553221
  • NDL Call No.
    Z74-C192
  • Data Source
    CJP  NDL  NII-ELS  IPSJ 
Page Top