Branch-Price-and-Cut for Causal Discovery

James Cussens

Branch-Price-and-Cut for Causal Discovery

James Cussens

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

1 Citation (Scopus)

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.

Original language	English
Title of host publication	Proceedings of Machine Learning Research (PMLR)
Subtitle of host publication	Conference on Causal Learning and Reasoning (CLeaR 23)
Pages	642-661
Number of pages	20
Volume	213
Publication status	Published - 10 Aug 2023
Event	CLeaR 2023: Causal Learning and Reasoning - Tubingen, Germany Duration: 11 Apr 2023 → 14 Apr 2023 https://www.cclear.cc/2023

Publication series

Name	Proceedings of Machine Learning Research
Publisher	ML Research Press
ISSN (Electronic)	2640-3498

Conference

Conference	CLeaR 2023
Country/Territory	Germany
City	Tubingen
Period	11/04/23 → 14/04/23
Internet address	https://www.cclear.cc/2023

Bibliographical note

Publisher Copyright:
© 2023 J. Cussens.

Access to Document

https://proceedings.mlr.press/v213/cussens23a/cussens23a.pdf

Handle.net

Persistent link

Cite this

@inproceedings{3750ac9d504b4f6f88f1fae4120af88d,

title = "Branch-Price-and-Cut for Causal Discovery",

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.",

author = "James Cussens",

note = "Publisher Copyright: {\textcopyright} 2023 J. Cussens.; CLeaR 2023 : Causal Learning and Reasoning ; Conference date: 11-04-2023 Through 14-04-2023",

year = "2023",

month = aug,

day = "10",

language = "English",

volume = "213",

series = "Proceedings of Machine Learning Research",

publisher = "ML Research Press",

pages = "642--661",

booktitle = "Proceedings of Machine Learning Research (PMLR)",

url = "https://www.cclear.cc/2023",

}

TY - GEN

T1 - Branch-Price-and-Cut for Causal Discovery

AU - Cussens, James

PY - 2023/8/10

Y1 - 2023/8/10

N2 - 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.

AB - 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.

UR - https://proceedings.mlr.press/v213/cussens23a.html

UR - https://openreview.net/forum?id=cZK80bf781S

M3 - Conference Contribution (Conference Proceeding)

VL - 213

T3 - Proceedings of Machine Learning Research

SP - 642

EP - 661

BT - Proceedings of Machine Learning Research (PMLR)

T2 - CLeaR 2023

Y2 - 11 April 2023 through 14 April 2023

ER -

Branch-Price-and-Cut for Causal Discovery

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this