TR2015-056
A Benders Approach to the Minimum Chordal Completion Problem
-
- , "A Benders Approach to the Minimum Chordal Completion Problem", International Conference on Integration of Artificial Intelligence and Operations Research (CPAIOR), DOI: 10.1007/978-3-319-18008-3_4, May 2015, vol. 9075, pp. 47-64.BibTeX TR2015-056 PDF
- @inproceedings{Bergman2015may,
- author = {Bergman, D. and Raghunathan, A.U.},
- title = {A Benders Approach to the Minimum Chordal Completion Problem},
- booktitle = {International Conference on Integration of Artificial Intelligence and Operations Research (CPAIOR)},
- year = 2015,
- volume = 9075,
- pages = {47--64},
- month = may,
- doi = {10.1007/978-3-319-18008-3_4},
- isbn = {978-3-319-18008-3},
- url = {https://www.merl.com/publications/TR2015-056}
- }
- , "A Benders Approach to the Minimum Chordal Completion Problem", International Conference on Integration of Artificial Intelligence and Operations Research (CPAIOR), DOI: 10.1007/978-3-319-18008-3_4, May 2015, vol. 9075, pp. 47-64.
-
MERL Contact:
-
Research Area:
Abstract:
This paper introduces an integer programming approach to the minimum chordal completion problem. This combinatorial optimization problem, although simple to pose, presents considerable computational difficulties and has been tackled mostly by heuristics. In this paper, an integer programming approach based on Benders decomposition is presented. Computational results show that the improvement in solution times over a simple branch-and-bound algorithm is substantial. The results also indicate that the value of the solutions obtained by a state-of-the-art heuristic can be in some cases significantly far away from the previously unknown optimal solutions obtained via the Benders approach.