An official website of the United States government
The effectiveness of satisfiability solvers strongly depends on the quality of the encoding of a given problem into conjunctive normal form. Cardinality constraints are prevalent in numerous problems, prompting the development and study of various types of encoding. We present a novel approach to optimizing cardinality constraint encodings by exploring the impact of literal orderings within the constraints. By strategically placing related literals nearby each other, the encoding generates auxiliary variables in a hierarchical structure, enabling the solver to reason more abstractly about groups of related literals. Unlike conventional metrics such as formula size or propagation strength, our method leverages structural properties of the formula to redefine the roles of auxiliary variables to enhance the solver's learning capabilities. The experimental evaluation on benchmarks from the maximum satisfiability competition demonstrates that literal orderings can be more influential than the choice of the encoding type. Our literal ordering technique improves solver performance across various encoding techniques, underscoring the robustness of our approach.
more »
« less
SAT-assembly: a new approach for designing self-assembling systems
Abstract We propose a general framework for solving inverse self-assembly problems, i.e. designing interactions between elementary units such that they assemble spontaneously into a predetermined structure. Our approach uses patchy particles as building blocks, where the different units bind at specific interaction sites (the patches), and we exploit the possibility of having mixtures with several components. The interaction rules between the patches is determined by transforming the combinatorial problem into a Boolean satisfiability problem (SAT) which searches for solutions where all bonds are formed in the target structure. Additional conditions, such as the non-satisfiability of competing structures (e.g. metastable states) can be imposed, allowing to effectively design the assembly path in order to avoid kinetic traps. We demonstrate this approach by designing and numerically simulating a cubic diamond structure from four particle species that assembles without competition from other polymorphs, including the hexagonal structure.
more »
« less
- Award ID(s):
- 1931487
- PAR ID:
- 10480079
- Publisher / Repository:
- IOP
- Date Published:
- Journal Name:
- Journal of Physics: Condensed Matter
- Volume:
- 34
- Issue:
- 35
- ISSN:
- 0953-8984
- Page Range / eLocation ID:
- 354002
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract While dominant species are known to be important in ecosystem functioning and community assembly, biodiversity responses to the presence of dominant species can be highly variable. Dominant species can increase the importance of deterministic community assembly by competitively excluding species in a consistent way across local communities, resulting in low site‐to‐site variation in community composition (beta‐diversity) and nonrandom community structure. In contrast, dominant species could increase the importance of stochastic community assembly by reducing the total number of individuals in local communities (community size), resulting in high beta‐diversity and more random community structure. We tested these hypotheses in a large, temperate oak‐hickory forest plot containing a locally dominant tree species, pawpaw (Asimina triloba; Annonaceae), an understory tree species that occurs in dense, clonal patches in forests throughout the east‐central United States. We determined how the presence of pawpaw influences local species diversity, community size, and beta‐diversity by measuring the abundance of all vascular plant species in 1 × 1‐m plots both inside and outside pawpaw patches. To test whether the presence of pawpaw influences local assembly processes, we compared observed patterns of beta‐diversity inside and outside patches to a null model in which communities were assembled at random with respect to species identity. We found lower local species diversity, lower community size, and higher observed beta‐diversity inside pawpaw patches than outside pawpaw patches. Moreover, standardized effect sizes of beta‐diversity from the null model were lower inside pawpaw patches than outside pawpaw patches, indicating more random species composition inside pawpaw patches. Together these results suggest that pawpaw increases the importance of stochastic relative to deterministic community assembly at local scales, likely by decreasing overall numbers of individuals and increasing random local extinctions inside patches. Our findings provide insights into the ecological processes by which locally dominant tree species shape the assembly and diversity of understory plant communities at different spatial scales.more » « less
-
Abstract A fragment‐based approach has proven successful in drug design and protein assemblies, yet its potential for constructing biomaterials from simple organic building blocks remains underexplored, particularly for self‐assembly in aqueous phases, where water disrupts intermolecular hydrogen bonding. To the best of our knowledge, this study introduces the first case of integrating fragments from self‐assembling molecules to design a small organic molecule that forms novel hierarchical nanotubes with polymorphism. The molecule's compact design incorporates three structural motifs derived from known nanotube assemblies, enabling a hierarchical assembly process: individual molecules with two conformations form dimers, which organize into hexameric units. These hexamers further assemble into nanotubes comprising 2‐, 5‐, and 6‐protofilament fibers. The nanofibers share a nearly identical asymmetric unit – a hexameric triangular plate – with similar axial and lateral interfaces. The lateral interface, involving interactions between phosphate groups and aromatic rings, exhibits plasticity, allowing slight rotational variations between adjacent units. This adaptability facilitates the formation of diverse nanofiber architectures, showcasing the flexibility of these systems in aqueous environments. By leveraging fragments of self‐assembling molecules, this work demonstrates a straightforward strategy that combines conformational flexibility and self‐assembling fragments to construct advanced supramolecular biomaterials from small organic building blocks in aqueous settings.more » « less
-
Just like atoms combine into molecules, colloids can self-organize into predetermined structures according to a set of design principles. Controlling valence—the number of interparticle bonds—is a prerequisite for the assembly of complex architectures. The assembly can be directed via solid “patchy” particles with prescribed geometries to make, for example, a colloidal diamond. We demonstrate here that the nanoscale ordering of individual molecular linkers can combine to program the structure of microscale assemblies. Specifically, we experimentally show that covering initially isotropic microdroplets withNmobile DNA linkers results in spontaneous and reversible self-organization of the DNA intoZ(N) binding patches, selecting a predictable valence. We understand this valence thermodynamically, deriving a free energy functional for droplet–droplet adhesion that accurately predicts the equilibrium size of and molecular organization within patches, as well as the observed valence transitions withN. Thus, microscopic self-organization can be programmed by choosing the molecular properties and concentration of binders. These results are widely applicable to the assembly of any particle with mobile linkers, such as functionalized liposomes or protein interactions in cell–cell adhesion.more » « less
-
Abstract Designing 3D porous metamaterial units while ensuring complete connectivity of both solid and pore phases presents a significant challenge. This complete connectivity is crucial for manufacturability and structure-fluid interaction applications (e.g., fluid-filled lattices). In this study, we propose a generative graph neural network-based framework for designing the porous metamaterial units with the constraint of complete connectivity. First, we propose a graph-based metamaterial unit generation approach to generate porous metamaterial samples with complete connectivity in both solid and pore phases. Second, we establish and evaluate three distinct variational graph autoencoder (VGAE)-based generative models to assess their effectiveness in generating an accurate latent space representation of metamaterial structures. By choosing the model with the highest reconstruction accuracy, the property-driven design search is conducted to obtain novel metamaterial unit designs with the targeted properties. A case study on designing liquid-filled metamaterials for thermal conductivity properties is carried out. The effectiveness of the proposed graph neural network-based design framework is evaluated by comparing the performances of the obtained designs with those of known designs in the metamaterial database. Merits and shortcomings of the proposed framework are also discussed.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1088/1361-648X/ac5479
