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

DOI10.1016/J.EJOR.2020.04.001zbMATH Open1487.90629OpenAlexW3015781022MaRDI QIDQ2023909FDOQ2023909

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

Recommendations

• The maximum flow problem with conflict and forcing conditions
• The maximum flow problem with disjunctive constraints
• Assignment problem with conflicts
• Polynomial-time algorithms for special cases of the maximum confluent flow problem
• Capacitated Confluent Flows: Complexity and Algorithms

zbMATH Keywords

combinatorial optimizationconflictmaximum flowbranch-and-boundBenders decompositionRussian doll search

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Solving the set covering problem with conflicts on sets: a new parallel GRASP
• A matheuristic for a customer assignment problem in direct marketing
• The maximum flow problem with disjunctive constraints
• 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

This page was built for publication: Exact solution algorithms for the maximum flow problem with additional conflict constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2023909)