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

Search this Article

Author(s)

    • 鴻池 祐輔 KOUNOIKE YUUSUKE
    • 東京農工大学工学部情報コミュニケーション工学科 Department of Computer, Information and Communication Sciences, Faculty of Engineering, Tokyo University of Agriculture and Technology
    • 品野 勇治 SHINANO YUJI
    • 東京農工大学工学部情報コミュニケーション工学科 Department of Computer, Information and Communication Sciences, Faculty of Engineering, Tokyo University of Agriculture and Technology

Abstract

Integral Basis MethodはHaus, Koppe, Weismantelによって提案された, 整数線形計画問題に対する新たな厳密解法である.本稿では2次割当問題への適用を通して, Integral Basis Methodの性質を調べて, その効率を改良する方法を提案する.提案する改良は, QAPの制約式の持つ特徴を緩和に利用することである.17問のベンチマーク問題に対する実験の結果, すべての問題で反復回数が大きく減少し, 6問の問題を除いて計算時間の短縮に成功している.これらの技法は, 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 out 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 are could be effectively applicable also in general ILP.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 2005(93), 37-40, 2005-09-21

    Information Processing Society of Japan (IPSJ)

Codes

  • NII Article ID (NAID)
    110002952281
  • NII NACSIS-CAT ID (NCID)
    AN10505667
  • Text Lang
    JPN
  • ISSN
    0919-6072
  • NDL Article ID
    7469323
  • NDL Call No.
    Z14-1121
  • Data Source
    NDL  NII-ELS 
Page Top