A Branch-and-Bound Algorithm for the Maximum Weight Perfect Matching Problem with Conflicting Edge Pairs

Temel Öncan; Hakan Akyuz; Kuban Altınel

A Branch-and-Bound Algorithm for the Maximum Weight Perfect Matching Problem with Conflicting Edge Pairs

Temel Öncan^*, Hakan Akyuz, Kuban Altınel

^*Corresponding author for this work

Research output: Chapter/Conference proceeding › Conference proceeding › Academic › peer-review

Abstract

This paper introduces a branch-and-bound (B&B) algorithm for the maximum weight perfect matching problem with conflicting edge pairs which is an N P-hard problem. The proposed B&B algorithm is based on the relaxation obtained by removing the cardinality restriction on the feasible matchings and uses a nondichotomized branching rule considering exposed vertices in a relaxed optimum solution. We have performed extensive computational experiments on randomly generated test instances and compared the proposed B&B algorithm with two Binary Integer Linear Programming models solved with an off-the-shelf commercial solver. According to our experiments, we have observed that the proposed B&B algorithm yields promising performance.

Original language	English
Title of host publication	Proceedings of the 9th International Network Optimization Conference (INOC)
Publisher	OpenProceedings.org
Pages	31-36
Publication status	Published - 2019
Externally published	Yes

Erasmus Sectorplan

Sectorplan SSH-Breed

Access to Document

INOC_2019_paper_17Final published version, 669 KBLicence: CC BY-NC-ND

https://openproceedings.org/2019/conf/inoc/INOC_2019_paper_17.pdfLicence: CC BY-NC-ND

Cite this

@inproceedings{b9a4aee7ef0742df8f17bbbf010899ad,

title = "A Branch-and-Bound Algorithm for the Maximum Weight Perfect Matching Problem with Conflicting Edge Pairs",

abstract = "This paper introduces a branch-and-bound (B&B) algorithm for the maximum weight perfect matching problem with conflicting edge pairs which is an N P-hard problem. The proposed B&B algorithm is based on the relaxation obtained by removing the cardinality restriction on the feasible matchings and uses a nondichotomized branching rule considering exposed vertices in a relaxed optimum solution. We have performed extensive computational experiments on randomly generated test instances and compared the proposed B&B algorithm with two Binary Integer Linear Programming models solved with an off-the-shelf commercial solver. According to our experiments, we have observed that the proposed B&B algorithm yields promising performance.",

author = "Temel {\"O}ncan and Hakan Akyuz and Kuban Altınel",

year = "2019",

language = "English",

pages = "31--36",

booktitle = "Proceedings of the 9th International Network Optimization Conference (INOC)",

publisher = "OpenProceedings.org",

address = "Germany",

}

TY - GEN

T1 - A Branch-and-Bound Algorithm for the Maximum Weight Perfect Matching Problem with Conflicting Edge Pairs

AU - Öncan, Temel

AU - Akyuz, Hakan

AU - Altınel, Kuban

PY - 2019

Y1 - 2019

N2 - This paper introduces a branch-and-bound (B&B) algorithm for the maximum weight perfect matching problem with conflicting edge pairs which is an N P-hard problem. The proposed B&B algorithm is based on the relaxation obtained by removing the cardinality restriction on the feasible matchings and uses a nondichotomized branching rule considering exposed vertices in a relaxed optimum solution. We have performed extensive computational experiments on randomly generated test instances and compared the proposed B&B algorithm with two Binary Integer Linear Programming models solved with an off-the-shelf commercial solver. According to our experiments, we have observed that the proposed B&B algorithm yields promising performance.

AB - This paper introduces a branch-and-bound (B&B) algorithm for the maximum weight perfect matching problem with conflicting edge pairs which is an N P-hard problem. The proposed B&B algorithm is based on the relaxation obtained by removing the cardinality restriction on the feasible matchings and uses a nondichotomized branching rule considering exposed vertices in a relaxed optimum solution. We have performed extensive computational experiments on randomly generated test instances and compared the proposed B&B algorithm with two Binary Integer Linear Programming models solved with an off-the-shelf commercial solver. According to our experiments, we have observed that the proposed B&B algorithm yields promising performance.

UR - https://openproceedings.org/html/pages/index.html

M3 - Conference proceeding

SP - 31

EP - 36

BT - Proceedings of the 9th International Network Optimization Conference (INOC)

PB - OpenProceedings.org

ER -

A Branch-and-Bound Algorithm for the Maximum Weight Perfect Matching Problem with Conflicting Edge Pairs

Abstract

Erasmus Sectorplan

Access to Document

Other files and links

Fingerprint

Cite this