Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDs

DOI10.1016/J.DAM.2024.10.003MaRDI QIDQ6648288zbMATH OpenFDO

Authors Shin-Ichi Minato, Jun Kawahara, Mutsunori Banbara, Takashi Horiyama, Ichigaku Takigawa, Yutaro Yamaguchi

Publication date 4 December 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2024.10.003

zbMATH Keywords

combinatorial problemscost-bounded solutionsdecision diagramsexact enumeration

Mathematics Subject Classification ID

Theory of computing (68Qxx) Artificial intelligence (68Txx) Mathematical programming (90Cxx)

Recommendations

• Enumerating all subgraphs under given constraints using zero-suppressed sentential decision diagrams
• Zero-suppressed BDDs and their applications
• Enumerating graph partitions without too small connected components using zero-suppressed binary and ternary decision diagrams
• DenseZDD: a compact and fast index for families of sets
• On threshold BDDs and the optimal variable ordering problem

Cites work

• A New Look at BDDs for Pseudo-Boolean Constraints
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• Chinese remainder encoding for Hamiltonian cycles
• Compact representation of near-optimal integer programming solutions
• Compiling finite linear CSP into SAT
• Cost-Bounded Binary Decision Diagrams for 0-1 Programming
• Counterexamples to the long-standing conjecture on the complexity of BDD binary operations
• Discrete optimization with decision diagrams
• FHCP challenge set: the first set of structurally difficult instances of the Hamiltonian cycle problem
• Generating Multiple Solutions for Mixed Integer Programming Problems
• Getting away with more network pruning: from sparsity to geometry and linear regions
• Graph-Based Algorithms for Boolean Function Manipulation
• Hamiltonian cycle reconfiguration with answer set programming
• Incremental encoding of pseudo-Boolean goal functions based on comparator networks
• Principles and practice of constraint programming. 20th international conference, CP 2014, Lyon, France, September 8--12, 2014. Proceedings
• Reducibility among combinatorial problems
• Size of ordered binary decision diagrams representing threshold functions
• Zero-suppressed BDDs and their applications

This page was built for publication: Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6648288)