Exact solution algorithms for the maximum flow problem with additional conflict constraints

DOI10.1016/j.ejor.2020.04.001zbMath1487.90629OpenAlexW3015781022MaRDI QIDQ2023909

Yanyan Li

Publication date: 3 May 2021

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2020.04.001

zbMATH Keywords

combinatorial optimizationbranch-and-boundBenders decompositionconflictmaximum flowRussian doll search

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items

A matheuristic for a customer assignment problem in direct marketing, Hybridizing adaptive large neighborhood search with kernel search: a new solution approach for the nurse routing problem with incompatible services and minimum demand, Minimum cost flow problem with conflicts, Multi-level bottleneck assignment problems: complexity and sparsity-exploiting formulations, Maximum weight perfect matching problem with additional disjunctive conflict constraints

Cites Work

• Unnamed Item
• Combinatorial Benders cuts for decomposing IMRT fluence maps using rectangular apertures
• The minimum cost perfect matching problem with conflict pair constraints
• The maximum flow problem with disjunctive constraints
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• On risk-averse maximum weighted subgraph problems
• The minimum spanning tree problem with conflict constraints and its variations
• Paths, trees and matchings under disjunctive constraints
• Russian doll search for the Steiner triple covering problem
• Approximation algorithms for time constrained scheduling
• Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem
• The transportation problem with exclusionary side constraints
• Partitioning procedures for solving mixed-variables programming problems
• Geometric algorithms and combinatorial optimization.
• Efficient graph representations
• The Benders decomposition algorithm: a literature review
• The transportation problem with exclusionary side constraints and two branch-and-bound algorithms
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A branch and cut algorithm for minimum spanning trees under conflict constraints
• A Benders decomposition approach for a distribution network design problem with consolidation and capacity considerations
• Incidence matrices and interval graphs
• Minimum cost noncrossing flow problem on layered networks
• Decomposition algorithms for solving the minimum weight maximal matching problem
• Algorithms for the Bin Packing Problem with Conflicts
• A Branch-and-Price Algorithm for the Bin Packing Problem with Conflicts
• Minimum-cost flow algorithms: an experimental evaluation
• The Knapsack Problem with Conflict Graphs
• Integer Programming
• Combinatorial Benders' Cuts for Mixed-Integer Linear Programming
• Thick non-crossing paths and minimum-cost flows in polygonal domains
• Determining a Minimum Spanning Tree with Disjunctive Constraints
• Tailoring Benders decomposition for uncapacitated network design
• A new approach to the maximum-flow problem
• Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria
• Transportation problem with nonlinear side constraints a branch and bound approach
• A New Algorithm for Generating All the Maximal Independent Sets
• A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
• Cross decomposition for mixed integer programming
• Algorithm Theory - SWAT 2004
• On the history of the transportation and maximum flow problems
• Benchmarking optimization software with performance profiles.