Branch-Price-and-Cut for Causal Discovery

James Cussens
Proceedings of the Second Conference on Causal Learning and Reasoning, PMLR 213:642-661, 2023.

Abstract

We show how to extend the integer programming (IP) approach to score-based causal discovery by including pricing. Pricing allows the addition of new IP variables during solving, rather than requiring them all to be present initially. The dual values of acyclicity constraints allow this addition to be done in a principled way. We have extended the GOBNILP algorithm to effect a branch-price-and-cut method for DAG learning. Empirical results show that implementing a delayed pricing approach can be beneficial. The current pricing algorithm in GOBNILP is slow, so further work on fast pricing is required.

Cite this Paper

BibTeX
@InProceedings{pmlr-v213-cussens23a, title = {Branch-Price-and-Cut for Causal Discovery}, author = {Cussens, James}, booktitle = {Proceedings of the Second Conference on Causal Learning and Reasoning}, pages = {642--661}, year = {2023}, editor = {van der Schaar, Mihaela and Zhang, Cheng and Janzing, Dominik}, volume = {213}, series = {Proceedings of Machine Learning Research}, month = {11--14 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v213/cussens23a/cussens23a.pdf}, url = {https://proceedings.mlr.press/v213/cussens23a.html}, abstract = { We show how to extend the integer programming (IP) approach to score-based causal discovery by including pricing. Pricing allows the addition of new IP variables during solving, rather than requiring them all to be present initially. The dual values of acyclicity constraints allow this addition to be done in a principled way. We have extended the GOBNILP algorithm to effect a branch-price-and-cut method for DAG learning. Empirical results show that implementing a delayed pricing approach can be beneficial. The current pricing algorithm in GOBNILP is slow, so further work on fast pricing is required.} }
Endnote
%0 Conference Paper %T Branch-Price-and-Cut for Causal Discovery %A James Cussens %B Proceedings of the Second Conference on Causal Learning and Reasoning %C Proceedings of Machine Learning Research %D 2023 %E Mihaela van der Schaar %E Cheng Zhang %E Dominik Janzing %F pmlr-v213-cussens23a %I PMLR %P 642--661 %U https://proceedings.mlr.press/v213/cussens23a.html %V 213 %X We show how to extend the integer programming (IP) approach to score-based causal discovery by including pricing. Pricing allows the addition of new IP variables during solving, rather than requiring them all to be present initially. The dual values of acyclicity constraints allow this addition to be done in a principled way. We have extended the GOBNILP algorithm to effect a branch-price-and-cut method for DAG learning. Empirical results show that implementing a delayed pricing approach can be beneficial. The current pricing algorithm in GOBNILP is slow, so further work on fast pricing is required.
APA
Cussens, J.. (2023). Branch-Price-and-Cut for Causal Discovery. Proceedings of the Second Conference on Causal Learning and Reasoning, in Proceedings of Machine Learning Research 213:642-661 Available from https://proceedings.mlr.press/v213/cussens23a.html.

Related Material