A MIXED INTEGER PROGRAMMING APPROACH FOR THE MINIMUM MAXIMAL FLOW

Access this Article

Search this Article

Author(s)

Abstract

<p>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. </p><p>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.</p>

Journal

  • Journal of the Operations Research Society of Japan

    Journal of the Operations Research Society of Japan 61(4), 261-271, 2018

    The Operations Research Society of Japan

Codes

  • NII Article ID (NAID)
    130007502005
  • NII NACSIS-CAT ID (NCID)
    AA00703935
  • Text Lang
    ENG
  • ISSN
    0453-4514
  • NDL Article ID
    029291939
  • NDL Call No.
    Z53-M226
  • Data Source
    NDL  J-STAGE 
Page Top