A MIXED INTEGER PROGRAMMING APPROACH FOR THE MINIMUM MAXIMAL FLOW

• Lu Kuan

  Tokyo Institute of Technology

• Mizuno Shinji

  Tokyo Institute of Technology

• Shi Jianming

  Tokyo University of Science

抄録

This paper concerns a minimum maximal flow (MMF) problem, which finds a minimum maximal flow in a given network. The problem is known to be NP-hard. We show that the MMF problem can be formulated as a mixed integer programming (MIP) problem and we propose to find the minimum maximal flow by solving the MIP problem. By performing computational experiments, we observe that the proposed approach is efficient to the MMF problem even for relatively large instances, where the number of edges is up to 15,000, and that the growth rate of running time of our approach is slower than the rates of previous works when the sizes of the instances grow.

収録刊行物

• 日本オペレーションズ・リサーチ学会論文誌

  日本オペレーションズ・リサーチ学会論文誌 61 (4), 261-271, 2018-10-25

  公益社団法人 日本オペレーションズ・リサーチ学会

キーワード

• Network Flow
• Minimum Maximal Flow
• Linear Programming
• Linear Complementarity Conditions
• Mixed Integer Programming

詳細情報

• CRID: 1390845713015155328
• NII論文ID: 130007502005
• NII書誌ID: AA00703935
• DOI: 10.15807/jorsj.61.261
• ISSN: 21888299
• ISSN: 04534514
• NDL書誌ID: 029291939
• Web Site: http://id.ndl.go.jp/bib/029291939
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I029291939
• Web Site: https://www.jstage.jst.go.jp/article/jorsj/61/4/61_261/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可