A Branch-and-Bound Algorithm for the Minimum Cost Bipartite Perfect Matching Problem with Conflict Pair Constraints
| Autor: | I. Kuban Altınel, Temel Öncan |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
021103 operations research
Branch and bound Total cost Applied Mathematics 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology Solver 01 natural sciences Combinatorics Set (abstract data type) 010201 computation theory & mathematics Bipartite graph Discrete Mathematics and Combinatorics Enhanced Data Rates for GSM Evolution Integer programming MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Popis: | In this study we consider the Minimum Cost Bipartite Perfect Matching Problem with Conflict Pair Constraints (MCBPMPC) on bipartite graphs. Given a bipartite graph G with a cost associated with each edge and a conflict set of edge pairs, the MCBPMPC consists of finding a perfect matching with the lowest total cost such that no more than one edge is selected from each pair in the conflict set. A specially tailored branch-and-bound (B&B) algorithm is introduced. Computational experiments are performed on randomly generated instances. According to the extensive experiments, the suggested B&B algorithm yields promising results compared to a state-of-the-art mixed integer linear programming solver. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|