Maximizing gerrymandering through ising model optimization.
Ontology highlight
ABSTRACT:
SUBMITTER: Okamoto Y
PROVIDER: S-EPMC8655093 | biostudies-literature | 2021 Dec
REPOSITORIES: biostudies-literature
Publications
Maximizing gerrymandering through ising model optimization.
Scientific reports 20211208 1
By using the Ising model formulation for combinatorial optimization with 0-1 binary variables, we investigated the extent to which partisan gerrymandering is possible from a random but even distribution of supporters. Assuming that an electoral district consists of square subareas and that each subarea shares at least one edge with other subareas in the district, it was possible to find the most tilted assignment of seats in most cases. However, in cases where supporters' distribution included m ...[more]
Similar Datasets
Project description:This paper provides a new (second) way, which is completely different from Shor's algorithm, to show the optimistic potential of a D-Wave quantum computer for deciphering RSA and successfully factoring all integers within 10000. Our method significantly reduced the local field coefficient [Formula: see text] and coupling term coefficient [Formula: see text] by more than 33% and 26%, respectively, of those of Ising model, which can further improve the stability of qubit chains and improve the upper bound of integer factorization. In addition, our results obtained the best index (20-bit integer (1028171)) of quantum computing for deciphering RSA via the quantum computing software environment provided by D-Wave. Furthermore, Shor's algorithm requires approximately 40 qubits to factor the integer 1028171, which is far beyond the capacity of universal quantum computers. Thus, post quantum cryptography should further consider the potential of the D-Wave quantum computer for deciphering the RSA cryptosystem in future.
| S-EPMC7188840 | biostudies-literature
Project description:Genomic selection (GS) has become an increasingly popular tool in plant breeding programs, propelled by declining genotyping costs, an increase in computational power, and rediscovery of the best linear unbiased prediction methodology over the past two decades. This development has led to an accumulation of extensive historical datasets with genotypic and phenotypic information, triggering the question of how to best utilize these datasets. Here, we investigate whether all available data or a subset should be used to calibrate GS models for across-year predictions in a 7-year dataset of a commercial hybrid sunflower breeding program. We employed a multi-objective optimization approach to determine the ideal years to include in the training set (TRS). Next, for a given combination of TRS years, we further optimized the TRS size and its genetic composition. We developed the Min_GRM size optimization method which consistently found the optimal TRS size, reducing dimensionality by 20% with an approximately 1% loss in predictive ability. Additionally, the Tails_GEGVs algorithm displayed potential, outperforming the use of all data by using just 60% of it for grain yield, a high-complexity, low-heritability trait. Moreover, maximizing the genetic diversity of the TRS resulted in a consistent predictive ability across the entire range of genotypic values in the test set. Interestingly, the Tails_GEGVs algorithm, due to its ability to leverage heterogeneity, enhanced predictive performance for key hybrids with extreme genotypic values. Our study provides new insights into the optimal utilization of historical data in plant breeding programs, resulting in improved GS model predictive ability.
| S-EPMC10943787 | biostudies-literature
Project description:A prominent approach to solving combinatorial optimization problems on parallel hardware is Ising machines, i.e., hardware implementations of networks of interacting binary spin variables. Most Ising machines leverage second-order interactions although important classes of optimization problems, such as satisfiability problems, map more seamlessly to Ising networks with higher-order interactions. Here, we demonstrate that higher-order Ising machines can solve satisfiability problems more resource-efficiently in terms of the number of spin variables and their connections when compared to traditional second-order Ising machines. Further, our results show on a benchmark dataset of Boolean k-satisfiability problems that higher-order Ising machines implemented with coupled oscillators rapidly find solutions that are better than second-order Ising machines, thus, improving the current state-of-the-art for Ising machines.
| S-EPMC10533504 | biostudies-literature
Project description:BackgroundFor years, US medical schools have relied on community-based, private clinicians to educate medical students. There has been a steady decline in the number of physicians willing to take on medical students in their clinical practices. Recent issues related to the pandemic raise questions about how many patients students should see to have a meaningful clinical experience.MethodsAs part of a 16-week longitudinal clinical experience, medical students spend 2 days each week in a family medicine or internal medicine clinic. As repetition enhances learning, maximizing the number of patients students see is important. Using a mixed integer linear program, we sought to determine the optimal schedule that maximizes the number of patients whom students see during a rotation. Patient visits were collected from January to April 2018 for clinics used by the medical school. By maximizing the minimum number of patients per learner over all non-empty day-clinic combinations, we deliver equitable rotation plans based on our assumptions.ResultsFor this pilot study, multiple experiments were performed with different numbers of students assigned to clinics. Each experiment also generated a weekly rotation plan for a given student. Based on this optimization model, the minimum number of patients per student over 16 weeks was 87 (3 patients per day) and actually increased the number of students who could be assigned to one of the clinics from 1 student per rotation to 8 students.ConclusionsThe mixed integer linear program assigned more students to clinics that have more total visits in order to achieve the optimal and fairest learning quality. In addition, by conducting various experiments on different numbers of students, we observed that we were able to allocate more students without affecting the number of patients students see.
| S-EPMC8741226 | biostudies-literature
Project description:Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.
| S-EPMC7568299 | biostudies-literature
Project description:Messenger RNA (mRNA) vaccines are a new alternative to conventional vaccines with a prominent role in infectious disease control. These vaccines are produced in in vitro transcription (IVT) reactions, catalyzed by RNA polymerase in cascade reactions. To ensure an efficient and cost-effective manufacturing process, essential for a large-scale production and effective vaccine supply chain, the IVT reaction needs to be optimized. IVT is a complex reaction that contains a large number of variables that can affect its outcome. Traditional optimization methods rely on classic Design of Experiments methods, which are time-consuming and can present human bias or based on simplified assumptions. In this contribution, we propose the use of Machine Learning approaches to perform a data-driven optimization of an mRNA IVT reaction. A Bayesian optimization method and model interpretability techniques were used to automate experiment design, providing a feedback loop. IVT reaction conditions were found under 60 optimization runs that produced 12 g · L-1 in solely 2 h. The results obtained outperform published industry standards and data reported in literature in terms of both achievable reaction yield and reduction of production time. Furthermore, this shows the potential of Bayesian optimization as a cost-effective optimization tool within (bio)chemical applications.
| S-EPMC9539360 | biostudies-literature
Project description:Background and objectiveCancer Immunoediting (CI) describes the cellular-level interaction between tumor cells and the Immune System (IS) that takes place in the Tumor Micro-Environment (TME). CI is a highly dynamic and complex process comprising three distinct phases (Elimination, Equilibrium and Escape) wherein the IS can both protect against cancer development as well as, over time, promote the appearance of tumors with reduced immunogenicity. Herein we present an agent-based model for the simulation of CI in the TME, with the objective of promoting the understanding of this process.MethodsOur model includes agents for tumor cells and for elements of the IS. The actions of these agents are governed by probabilistic rules, and agent recruitment (including cancer growth) is modeled via logistic functions. The system is formalized as an analogue of the Ising model from statistical mechanics to facilitate its analysis. The model was implemented in the Netlogo modeling environment and simulations were performed to verify, illustrate and characterize its operation.ResultsA main result from our simulations is the generation of emergent behavior in silico that is very difficult to observe directly in vivo or even in vitro. Our model is capable of generating the three phases of CI; it requires only a couple of control parameters and is robust to these. We demonstrate how our simulated system can be characterized through the Ising-model energy function, or Hamiltonian, which captures the "energy" involved in the interaction between agents and presents it in clear and distinct patterns for the different phases of CI.ConclusionsThe presented model is very flexible and robust, captures well the behaviors of the target system and can be easily extended to incorporate more variables such as those pertaining to different anti-cancer therapies. System characterization via the Ising-model Hamiltonian is a novel and powerful tool for a better understanding of CI and the development of more effective treatments. Since data of CI at the cellular level is very hard to procure, our hope is that tools such as this may be adopted to shed light on CI and related developing theories.
| S-EPMC9150349 | biostudies-literature
Project description:There has been a lot of work fitting Ising models to multivariate binary data in order to understand the conditional dependency relationships between the variables. However, additional covariates are frequently recorded together with the binary data, and may influence the dependence relationships. Motivated by such a dataset on genomic instability collected from tumor samples of several types, we propose a sparse covariate dependent Ising model to study both the conditional dependency within the binary data and its relationship with the additional covariates. This results in subject-specific Ising models, where the subject's covariates influence the strength of association between the genes. As in all exploratory data analysis, interpretability of results is important, and we use ℓ1 penalties to induce sparsity in the fitted graphs and in the number of selected covariates. Two algorithms to fit the model are proposed and compared on a set of simulated data, and asymptotic results are established. The results on the tumor dataset and their biological significance are discussed in detail.
| S-EPMC4425428 | biostudies-literature
Project description:Simulating physical dynamics to solve hard combinatorial optimization has proven effective for medium- to large-scale problems. The dynamics of such systems is continuous, with no guarantee of finding optimal solutions of the original discrete problem. We investigate the open question of when simulated physical solvers solve discrete optimizations correctly, with a focus on coherent Ising machines (CIMs). Having established the existence of an exact mapping between CIM dynamics and discrete Ising optimization, we report two fundamentally distinct bifurcation behaviors of the Ising dynamics at the first bifurcation point: either all nodal states simultaneously deviate from zero (synchronized bifurcation) or undergo a cascade of such deviations (retarded bifurcation). For synchronized bifurcation, we prove that when the nodal states are uniformly bounded away from the origin, they contain sufficient information for exactly solving the Ising problem. When the exact mapping conditions are violated, subsequent bifurcations become necessary and often cause slow convergence. Inspired by those findings, we devise a trapping-and-correction (TAC) technique to accelerate dynamics-based Ising solvers, including CIMs and simulated bifurcation. TAC takes advantage of early bifurcated "trapped nodes" which maintain their sign throughout the Ising dynamics to reduce computation time effectively. Using problem instances from open benchmark and random Ising models, we validate the superior convergence and accuracy of TAC.
| S-EPMC10154334 | biostudies-literature
Project description:Operator learning is a rising field of scientific computing where inputs or outputs of a machine learning model are functions defined in infinite-dimensional spaces. In this paper, we introduce Neon (Neural Epistemic Operator Networks), an architecture for generating predictions with uncertainty using a single operator network backbone, which presents orders of magnitude less trainable parameters than deep ensembles of comparable performance. We showcase the utility of this method for sequential decision-making by examining the problem of composite Bayesian Optimization (BO), where we aim to optimize a function f=g∘h , where h:X→C(Y,Rds) is an unknown map which outputs elements of a function space, and g:C(Y,Rds)→R is a known and cheap-to-compute functional. By comparing our approach to other state-of-the-art methods on toy and real world scenarios, we demonstrate that Neon achieves state-of-the-art performance while requiring orders of magnitude less trainable parameters.
| S-EPMC11589850 | biostudies-literature