The Cost of Flattening with Common Subexpression Elimination

Research output: Other contribution


Compilingasolver-independentconstraintmodeltosolverinputusu- ally involves flattening, the decomposition of complex constraints into simpler expressions to suit the solver, introducing additional variables and constraints. In previous work, we have proposed extending flattening with common subex- pression elimination (CSE) which can reduce the overhead introduced during flat- tening. In this work, we formally analyse the cost of standard flattening and CSE- based flattening: we compare time and space complexity and investigate the po- tential variable and constraint reduction from CSE-based flattening, its scope and limitations. Furthermore, we discuss flattening whole problem classes and show how to integrate CSE into class-wise flattening. We highlight the differences to instance-wise flattening and discuss open questions. Finally, our empirical analy- sis confirms our theoretical findings and demonstrates the benefits of CSE-based flattening.
Original languageEnglish
TypeWorkshop paper
Number of pages15
Publication statusPublished - 2009

Publication series

NameProceedings of the 8th International Conference on Constraint Modelling and Reformulation (ModRef)


Dive into the research topics of 'The Cost of Flattening with Common Subexpression Elimination'. Together they form a unique fingerprint.

Cite this