Applications and efficient algorithms for integer programming problems on monotone constraints. Issue 1 (9th September 2020)

• Record Type: Journal Article
• Authors: Hochbaum, Dorit S.
• Is Part Of: Networks. Volume 77:Issue 1(2021)
• Page Start: 21
• Page End: 49
• Publication Date: 2020-09-09
• Subjects: image segmentation -- integer programming -- monotone inequalities -- network flow -- parametric cut -- ratio problems; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21983
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: We present here classes of integer programming problems that are solvable efficiently and with combinatorial flow algorithms. The problems are characterized by constraints that have either at most two variables per inequality that appear with opposite sign coefficients, or have in addition a third variable that appears only in one constraint. Such integer programs, referred to here as monotone IP2 or IP3, are shown to be solvable in polynomial time for polynomially bounded variables. This article demonstrates the vast applicability of IP2 and IP3 as models for integer programs in multiple scenarios. Since the problems are easily recognized, the knowledge of their structure enables one to determine easily that they are efficiently solvable. The variety of applications, that previously were not known to be solved as efficiently, underlies the importance of recognizing this structure and, if appropriate, formulating problems as monotone IP2 or IP3. Additionally, if there is flexibility in the modeling of an integer programming problem, the formulation choice as monotone IP2 or IP3 leads to efficient algorithms, whereas slightly different modeling choices would lead to NP‐hard problems.