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

DOI10.1016/J.EJOR.2020.04.001MaRDI QIDQ2023909zbMATH OpenOpenAlexFDO

Authors 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

Benders decompositionbranch-and-boundcombinatorial optimizationconflictmaximum flowRussian doll search

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(11)

• A matheuristic for a customer assignment problem in direct marketing
• The maximum flow problem with conflict and forcing conditions
• 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
• Solving the set covering problem with conflicts on sets: a new parallel GRASP
• Extended formulation and branch-and-cut-and-price algorithm for the two connected subgraph problem with disjunctive constraints
• Hybridizing carousel greedy and kernel search: a new approach for the maximum flow problem with conflict constraints
• An efficient branch-and-bound algorithm for the one-to-many shortest path 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)