Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “solving”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 37 records · Page 2

General features of supersymmetric signals at the ILC: Solving the CERN LHC inverse problem

We present the first detailed, large-scale study of the minimal supersymmetric standard model (MSSM) at the {radical}(s)=500 GeV International Linear Collider (ILC), including full standard model backgrounds and detector simulation. This is the first realistic study of the capabilities of the ILC examining the physics of many distinct points in MSSM parameter space which are not linked to a particular supersymmetry (SUSY) breaking mechanism. Specifically, we investigate 242 points in the MSSM parameter space, which we term models, that correspond to the 162 pairs of models that were found by Arkani-Hamed et al. to give indistinguishable signatures at the LHC. We first determine whether the production of the various SUSY particles is visible above the standard model background for each of these parameter space points, and then make a detailed comparison of their various signatures. Assuming an integrated luminosity of 500 fb{sup -1} with 80% electron beam polarization, we find that only 82 out of 242 models lead to visible signatures of some kind with a significance {>=}5 and that only 57 (63) out of the 162 model pairs are distinguishable at 5 (3){sigma}. Our analysis includes PYTHIA and CompHEP SUSY signal generation, full matrix element SM backgrounds for all 2{yields}2, 2{yields}4 and 2{yields}6 processes, ILC-specific initial state radiation and beamstrahlung generated via WHIZARD/GuineaPig, and employs the fast SiD detector simulation org.lcsim. If SUSY is light, the ILC will do a good job at examining its details.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

CSGID Solves Structures and Identifies Phenotypes for Five Enzymes in Toxoplasma gondii

Toxoplasma gondii, an Apicomplexan parasite, causes significant morbidity and mortality, including severe disease in immunocompromised hosts and devastating congenital disease, with no effective treatment for the bradyzoite stage. To address this, we used the Tropical Disease Research database, crystallography, molecular modeling, and antisense to identify and characterize a range of potential therapeutic targets for toxoplasmosis. Phosphoglycerate mutase II (PGMII), nucleoside diphosphate kinase (NDK), ribulose phosphate 3-epimerase (RPE), ribose-5-phosphate isomerase (RPI), and ornithine aminotransferase (OAT) were structurally characterized. Crystallography revealed insights into the overall structure, protein oligomeric states and molecular details of active sites important for ligand recognition. Literature and molecular modeling suggested potential inhibitors and druggability. The targets were further studied with vivoPMO to interrupt enzyme synthesis, identifying the targets as potentially important to parasitic replication and, therefore, of therapeutic interest. Targeted vivoPMO resulted in statistically significant perturbation of parasite replication without concomitant host cell toxicity, consistent with a previous CRISPR/Cas9 screen showing PGM, RPE, and RPI contribute to parasite fitness. PGM, RPE, and RPI have the greatest promise for affecting replication in tachyzoites. These targets are shared between other medically important parasites and may have wider therapeutic potential.

59 BASIC BIOLOGICAL SCIENCES↗

Comparing Model Ozone Loss during the SOLVE and SOLVE-2 Winters

Model simulations have been used to analyze the factors influencing ozone loss during the 1999-2000 and 2002-2003 js. For both winters, the evolution of the Arctic vortex from November to April has been simulated using a trajectory-based microphysical and photochemical model. Extensive PSC formation and strong ozone depletion are evident in both winters. However, the ozone loss begins earlier in the 2002-2003 winter, with significant ozone depletion by early January. Analysis of the model results shows that during December 2002 not only cold temperatures but also the vortex structure was critical, allowing PSC-processed air parcels to experience significant solar exposure. The resultant ozone loss can be differentiated from ozone loss that occurs in the springtime, in particular because of the continued exposure to PSCs. For example, chlorine reactivation by the PSCs causes ozone loss to be insensitive to denitrification. Therefore, diagnosing the extent of ozone loss early in the winter is critical In understanding the overall winter-long ozone depletion.

Drdla, K.↗

Addressing Over-Solving in Multiphysics Codes with Nested Solvers

Examples of multiphysics problems in the field of nuclear engineering are numerous. For light water reactors the coupling of neutronics with thermal-hydraulics is the most predominant. Often this coupling is modeled by combining existing codes in a Picard Iteration scheme, that is, by solving one physics then using that answer to solve the other and iterating until both answers stabilize. However, simply solving to a high precision on every Picard (multiphysics) iteration is much less efficient than progressively solving to higher precisions. This unneeded work is known as over-solving. Over-solving in single-physics solvers has been studied previously for the Newton method and Chebyshev iteration. Both of these methods solve an inner linear problem that determines the next update step for the outer loop. If the inner problem is solved to a high precision in every outer iteration, the result will be substantially more computational expense (over-solving) and a higher probability of reaching the 'wrong' solution. Methods for reducing over-solving in partitioned multiphysics codes have only been developed recently. This work introduces further improvements, including an investigation of over-solving methods on both the multiphysics and single-physics levels.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

Learning to Solve Large-Scale Security-Constrained Unit Commitment Problems

Security-constrained unit commitment (SCUC) is a fundamental problem in power systems and electricity markets. In practical settings, SCUC is repeatedly solved via mixed-integer linear programming (MIP), sometimes multiple times per day, with only minor changes in input data. In this work, we propose a number of machine learning techniques to effectively extract information from previously solved instances in order to significantly improve the computational performance of MIP solvers when solving similar instances in the future. Based on statistical data, we predict redundant constraints in the formulation, good initial feasible solutions, and affine subspaces where the optimal solution is likely to lie, leading to a significant reduction in problem size. Computational results on a diverse set of realistic and large-scale instances show that using the proposed techniques, SCUC can be solved on average 4.3 times faster with optimality guarantees and 10.2 times faster without optimality guarantees, with no observed reduction in solution quality. Out-of-distribution experiments provide evidence that the method is somewhat robust against data-set shift. Summary of Contribution. The paper describes a novel computational method, based on a combination of mixed-integer linear programming (MILP) and machine learning (ML), to solve a challenging and fundamental optimization problem in the energy sector. The method advances the state-of-the-art, not only for this particular problem, but also, more generally, in solving discrete optimization problems via ML. We expect that the techniques presented can be readily used by practitioners in the energy sector and adapted, by researchers in other fields, to other challenging operations research problems that are solved routinely.

Machine Learning↗

Decomposition and Algorithmic Approaches for Solving Large-Scale Process Family Design Problems

Our most recent work expands the water desalination case study from 76 variants to 10,897 variants using the equation-oriented model built in Pyomo as part of the PARETO project. Using the discretization formulation presented in Stinchfield (2024a), rather than solving for all 10,897 variants simultaneously, we decompose the formulation into subproblems containing subsets of variants from the process family. We solve the overall problem with Progressive Hedging (PH) deployed in parallel on a distributed HPC cluster using the open-source Python package mpi-sppy (Knueven et al., 2023). This approach allowed us to solve this process family design problem to ~1.5% relative optimality gap in about 5 hours; in comparison, Gurobi reached ~50% relative optimality gap in about 6 hours (Stinchfield et al., 2024b). However, this approach still requires discretization of the common unit module design ranges; additionally, PH acts as a heuristic for MILP’s with gap-closing capabilities. Ideally, we would not have to use ML surrogates or discretization to solve this problem, instead solving the process family design problem with the equation-oriented model directly to achieve the most accurate results. However, recall that we did not consider solving the MINLP directly due to complexity and size. In this work, we aim to decompose and solve this large-scale MINLP using a Structured Nonlinear Global Optimization algorithm presented by Cao and Zavala (2019).

Stinchfield, Georgia↗

Solving a system of linear equations: From centralized to distributed methods

For a wide range of control engineering applications, the problem of solving a system of linear equations is often encountered and has been well studied. Traditionally, this problem has been mainly solved in a centralized manner. However, for applications related to large-scale complex networked systems, centralized algorithms are often subjected to some practical issues due to limited computational power and communication bandwidth. As a promising and viable alternative, distributed algorithms can effectively address the issues associated with centralized algorithms by solving the problem efficiently in a multi-agent setting that accords with the distributed nature of networked systems. Distributed algorithms decompose the entire problem into many sub-problems that are solved by individual agents in a cooperative manner. In this survey paper, we provide a detailed overview of the state of the art relevant to distributed algorithms for solving a system of linear equations. We will first review basic distributed algorithms including both discrete-time and continuous-time algorithms. Then we will discuss the extended algorithms to achieve communication efficiency. Furthermore, we will also introduce distributed algorithms to obtain the minimum-norm solution for a system of linear equations with multiple solutions, as well as the least-squares solutions when there is no solution. Finally, the relationship of distributed algorithms for solving a system of linear equations to the existing distributed optimization algorithms is discussed.

Wang, Peng↗

A comparative study of two numerical approaches for solving Kim–Kim–Suzuki phase-field models

Among the standard multi-phase multi-component phase-field (PF) methods, the Kim–Kim–Suzuki (KKS) method has the advantage of decoupling interfacial energy from bulk energy and solving concentration as the conserved variable. There are two approaches to numerically solving a KKS method: the global solution approach (GSA) solves all variables in a global system simultaneously, and the local solution approach (LSA) solves phase concentrations locally using a Newton solver. This work compares the performance of LSA and GSA for solving four KKS models of increasing complexity with the finite element method using the MOOSE framework. The solution accuracy, degrees of freedom (DOFs), memory usage, and computational efficiency are compared. We find that GSA and LSA generate similar solutions, with a maximum difference of only 0.34%. For each model, LSA has a lower number of DOFs, utilizes less memory, and less wall time. Additionally, the savings of memory and wall time in LSA increase with increasing mesh density of the same model and are more pronounced in models with higher dimensionality and more nodes. However, GSA is easier to implement in existing codes and can better solve highly nonlinear systems by utilizing sophisticated solvers.

36 MATERIALS SCIENCE↗

Matrix Methods for Solving Hartree-Fock Equations in Atomic Structure Calculations and Line Broadening

Atomic structure of N-electron atoms is often determined by solving the Hartree-Fock equations, which are a set of integro-differential equations. The integral part of the Hartree-Fock equations treats electron exchange, but the Hartree-Fock equations are not often treated as an integro-differential equation. The exchange term is often approximated as an inhomogeneous or an effective potential so that the Hartree-Fock equations become a set of ordinary differential equations (which can be solved using the usual shooting methods). Because the Hartree-Fock equations are an iterative-refinement method, the inhomogeneous term relies on the previous guess of the wavefunction. In addition, there are numerical complications associated with solving inhomogeneous differential equations. This work uses matrix methods to solve the Hartree-Fock equations as an integro-differential equation. It is well known that a derivative operator can be expressed as a matrix made of finite-difference coefficients; energy eigenvalues and eigenvectors can be obtained by using linear-algebra packages. The integral (exchange) part of the Hartree-Fock equation can be approximated as a sum and written as a matrix. The Hartree-Fock equations can be solved as a matrix that is the sum of the differential and integral matrices. We compare calculations using this method against experiment and standard atomic structure calculations. This matrix method can also be used to solve for free-electron wavefunctions, thus improving how the atoms and free electrons interact. This technique is important for spectral line broadening in two ways: it improves the atomic structure calculations, and it improves the motion of the plasma electrons that collide with the atom.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Participation of HNO3 CIMS Instrument in the Sage III Ozone Loss and Validation Experiment (SOLVE)

This project was part of a larger SOLVE project led by Paul Wennberg at California Institute of Technology. The work completed on this project included participating in the installation and preflight testing of a new chemical ionization mass spectrometer for measuring gas and particle phase nitric acid on the ER-2. The investigators subsequently participated in SOLVE where additional instrument improvements were made and a substantial data set was generated. The two Georgia Tech investigators that participated in this work (Fred Eisele and Dave Tanner) had previously been responsible for much of the design and construction of the ion source and mass spectrometer which would be used to measure HNO3 in SOLVE, with Caltech focusing on inlets, calibration, gas supplies/pumping computer control, and overall integration. Thus, a similar focus remained during the SOLVE measurements though all investigators worked on most if not all aspects of the instrument at some point in the mission. Some of the more interesting results from the study included measurements of nitric acid on what are thought to be 5-20 microns diameter individual particles which could supply a local mechanism for HNO3 removal, Nitric acid measurements on SOLVE were completed as a collaborative effort with a great deal of overlap between this project and the larger parent project led by Paul Wennberg. As such, the instrumentation used, its operation, and the resulting measurements are far more fully discussed in the attached report (appendix A) which describes the joint SOLVE nitric acid measurement effort.

Eisele, F. L.↗

Novel Problem Solving - The NASA Solution Mechanism Guide

Over the past five years, the Human Health and Performance (HH&P) Directorate at the NASA Johnson Space Center (JSC) has conducted a number of pilot and ongoing projects in collaboration and open innovation. These projects involved the use of novel open innovation competitions that sought solutions from "the crowd", non-traditional problem solvers. The projects expanded to include virtual collaboration centers such as the NASA Human Health and Performance Center (NHHPC) and more recently a collaborative research project between NASA and the National Science Foundation (NSF). These novel problem-solving tools produced effective results and the HH&P wanted to capture the knowledge from these new tools, to teach the results to the directorate, and to implement new project management tools and coursework. The need to capture and teach the results of these novel problem solving tools, the HH&P decided to create a web-based tool to capture best practices and case studies, to teach novice users how to use new problem solving tools and to change project management training/. This web-based tool was developed with a small, multi-disciplinary group and named the Solution Mechanism Guide (SMG). An alpha version was developed that was tested against several sessions of user groups to get feedback on the SMG and determine a future course for development. The feedback was very positive and the HH&P decided to move to the beta-phase of development. To develop the web-based tool, the HH&P utilized the NASA Tournament Lab (NTL) to develop the software with TopCoder under an existing contract. In this way, the HH&P is using one new tool (the NTL and TopCoder) to develop the next generation tool, the SMG. The beta-phase of the SMG is planed for release in the spring of 2014 and results of the beta-phase testing will be available for the IAC meeting in September. The SMG is intended to disrupt the way problem solvers and project managers approach problem solving and to increase the use of novel and more cost and time effective problem solving tools such as open innovation, collaborative research, and virtual collaborative project centers. The HH&P envisions changing project management coursework by including the SMG in the teaching of project management problem solving tools.

Keeton, Kathryn E.↗

A modified model parametrization algorithm for solving a special type of heat and mass transfer systems

A new method for solving nonlinear heat and mass transfer design tasks was considered. Systems using the Number of Transfer Units (NTU) method are a special type of mathematical model of heat and mass exchangers. It was observed, that the NTU models in a form of differential-algebraic equations (DAEs) cannot be directly solved with higher values of NTU. The requirements for consistent initial conditions, as well as numerical limitations of DAEs solvers, result, that the solution to the considered design problems that cannot be obtained by a classical direct shooting procedure. To overcome the presented difficulties, the αDAE model optimization algorithm was adjusted for solving NTU-based models. The new approach consists of 3 main steps: 1) task discretization by a multiple-shooting approach, 2) design an appropriate function $f_{NTU}$(α) to effectively influence the variability of the state variables described by dynamical relations, 3) the iterative numerical optimization algorithm for the new parametrized system. Moreover, computations can be performed by a chosen numerical optimization approach, which can be communicated with an available outer procedure for solving differential-algebraic equations. The presented algorithm was implemented and applied to solve the design task with the NTU model of a counter-flow exchanger. Here, the new approach was used to modify the system dynamics to influence the difficulty of the considered problem. Finally, the presented method enabled failure-free numerical computations for the higher values of the NTU parameter.

97 MATHEMATICS AND COMPUTING↗

Students’ conceptions and problem-solving ability on topic chemical thermodynamics

The enthalpy concept and its change were introduced to describe the forms of internal energy transfer in chemical reactions. Likewise, the concepts of exothermic and endothermic reactions introduced as a consequence of heat transfer form. In the heat measurement process at constant pressure, work is often ignored. The exothermic or endothermic reactions, usually only based on the increase or decrease of the reaction temperature, without associated with the internal energy. Depictions of enthalpy and its change assumed closely related to students’ problem-solving ability. Therefore, the study to describe pre-service chemistry teacher student’s conceptions and problem-solving ability on topic chemical thermodynamics has been done. This research was a case study of chemical education course in Provinsi Lampung. The subjects of this study were 42 students who attend the chemical thermodynamics course. Questions about exothermic and endothermic reactions, enthalpy and its change, as well as internal energy and its change were given in the form of an essay exam questions. Answers related to conception qualitatively categorized, while problem solving answers were scored and assessed. The results showed that, in general, students were having problems in enthalpy and describe the changes in the form of heat and work. The highest value of problem solving ability obtained 26.67 from the maximum value of 100. The lowest value was 0, and the average value was 14.73. These results show that the problem-solving ability of pre-service chemistry teacher students was low. The results provide insight to researchers, and educators to develop learning or lab work on this concept.

42 ENGINEERING↗

Solving modal equations of motion with initial conditions using MSC/NASTRAN DMAP. Part 1: Implementing exact mode superposition

Within the MSC/NASTRAN DMAP (Direct Matrix Abstraction Program) module TRD1, solving physical (coupled) or modal (uncoupled) transient equations of motion is performed using the Newmark-Beta or mode superposition algorithms, respectively. For equations of motion with initial conditions, only the Newmark-Beta integration routine has been available in MSC/NASTRAN solution sequences for solving physical systems and in custom DMAP sequences or alters for solving modal systems. In some cases, one difficulty with using the Newmark-Beta method is that the process of selecting suitable integration time steps for obtaining acceptable results is lengthy. In addition, when very small step sizes are required, a large amount of time can be spent integrating the equations of motion. For certain aerospace applications, a significant time savings can be realized when the equations of motion are solved using an exact integration routine instead of the Newmark-Beta numerical algorithm. In order to solve modal equations of motion with initial conditions and take advantage of efficiencies gained when using uncoupled solution algorithms (like that within TRD1), an exact mode superposition method using MSC/NASTRAN DMAP has been developed and successfully implemented as an enhancement to an existing coupled loads methodology at the NASA Lewis Research Center.

Abdallah, Ayman A.↗

The Citizen Cyberscience Lectures - 1) Mobile phones and Africa: a success story 2) Citizen Problem Solving

Mobile phones and Africa: a success story Dr. Mo Ibrahim, Mo Ibrahim Foundation Citizen Problem Solving Dr. Alpheus Bingham, InnoCentive The Citizen Cyberscience Lectures are hosted by the partners of the Citizen Cyberscience Centre, CERN, The UN Institute of Training and Research and the University of Geneva. The goal of the Lectures is to provide an inspirational forum for participants from the various international organizations and academic institutions in Geneva to explore how information technology is enabling greater citizen participation in tackling global development challenges as well as global scientific research. The first Citizen Cyberscience Lectures will welcome two speakers who have both made major innovative contributions in this area. Dr. Mo Ibrahim, founder of Celtel International, one of Africa’s most successful mobile network operators, will talk about “Mobile phones and Africa: a success story”. Dr. Alpheus Bingham, founder of InnoCentive, a Web-based community that solves industrial R&D; challenges, will discuss “Citizen Problem Solving”. The Citizen Cyberscience Lectures are open and free of charge. Participants from outside CERN must register by sending an email to Yasemin.Hauser@cern.ch BEFORE the 23rd october to be able to access CERN. THE LECTURES Mobile phones and Africa: a success story Dr. Mo Ibrahim, Mo Ibrahim Foundation Abstract The introduction of mobile phones into Africa changed the continent, enabling business and the commercial sector, creating directly and indirectly, millions of jobs. It enriched the social lives of many people. Surprisingly, it supported the emerging civil society and advanced the course of democracy Bio Dr Mo Ibrahim is a global expert in mobile communications with a distinguished academic and business career. In 1998, Dr Ibrahim founded Celtel International to build and operate mobile networks in Africa. Celtel became one of Africa’s most successful companies with operations in 15 countries, covering more than a third of the continent’s population and investing more than US 750 millionin Africa.The company was sold to MTC Kuwaitin 2005 for 3.4billion. In 2006 Dr Ibrahim established the Mo Ibrahim Foundation to support great African leadership. The Foundation focuses on two major initiatives to stimulate debate around, and improve the quality of, governance in Africa. The Ibrahim Prize for Achievement in African Leadership recognises and celebrates excellence; and the Ibrahim Index of African Governance provides civil society with a comprehensive and quantifiable tool to promote government accountability. Dr Ibrahim is also Founding Chairman of Satya Capital Ltd, an investment company focused on opportunities in Africa. Dr Ibrahim has been awarded an Honorary Doctorate by the University of London’s School of Oriental and African Studies, the University of Birmingham and De Montfort University, Leicester as well as an Honorary Fellowship Award from the London Business School. He has also received the Chairman’s Award for Lifetime Achievement from the GSM Association in 2007 and the Economists Innovation Award 2007 for Social & Economic Innovation. In 2008 Dr Ibrahim was presented with the BNP Paribas Prize for Philanthropy, and also listed by TIME magazine as one of the 100 most influential people in the world. Citizen Problem Solving Dr. Alpheus Bingham, InnoCentive Abstract American playwright Damien Runyon (Guys and Dolls) once remarked, "the race is not always to the swift, nor the victory to the strong -- but that IS how you bet." Not only does a system of race handicapping follow from this logic, but the whole notion of expertise and technical qualifications. Such 'credentials' allow one to 'bet' on who might most likely solve a difficult challenge, whether as consultant, contractor or employee. Of course, the approach would differ if one were allowed to bet AFTER the race. When such systems came into broad use, i.e., chat rooms, usenets, innocentive, etc., and were subsequently studied, it was often found that the greatest probability of solution lies in the "long tail" of the function rather than in the head representing formally vetted 'experts.' Insight into a problem is often the intersection of training, experience, metaphor and provocation (think Archimedes). Examples of "citizens" outside a targeted field of expertise providing uniques solutions will illustrate the principles involved. Bio Dr. Alph Bingham is a pioneer in the field of open innovation and an advocate of collaborative approaches to research and development. He is co-founder, and former president and chief executive officer of InnoCentive Inc., a Web-based community that matches companies facing R&D; challenges with scientists who propose solutions. Through InnoCentive, a platform that leverages the ability to connect to a whole planet of people through the Internet, organizations can access individuals – problem solvers – who might never have been found. Alph spent more than 25 years with Eli Lilly and Company, and offers deep experience in pharmaceutical research and development, research acquisitions and collaborations, and R&D; strategic planning. During his career he was instrumental in creating and developing Eli Lilly's portfolio management process as well as establishing the divisions of Research Acquisitions, the Office of Alliance Management and e.Lilly, a business innovation unit, from which various other ventures were spun out that create the advantages of open and networked organizational structures, including: InnoCentive, YourEncore, Inc., Coalesix, Inc., Maaguzi, Inc., Indigo Biosystems, Seriosity, Chorus and Collaborative Drug Discovery, Inc. He currently serves on the Board of Directors of InnoCentive, Inc., and Collaborative Drug Discovery, Inc.; the advisory boards of the Center for Collective Intelligence (MIT), and the Business Innovation Factory, as well as a member of the board of trustees of the Bankinter Foundation for Innovation in Madrid. He has lectured extensively at both national and international events and serves as a Visiting Scholar at the National Center for Supercomputing Application at the University of Illinois at Champaign-Urbana. He is also the former chairman of the Board of Editors of the Research Technology Management Journal. Dr. Bingham was the recipient of the Economist's Fourth Annual Innovation Summit "Business Process Award" for InnoCentive. He was also named as one of Project Management Institute's "Power 50" leaders in October 2005. Dr. Bingham received a Ph.D. in organic chemistry from Stanford University.

99 GENERAL AND MISCELLANEOUS↗

Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms

The quantum approximate optimization algorithm (QAOA) has the potential to approximately solve complex combinatorial optimization problems in polynomial time. However, current noisy quantum devices cannot solve large problems due to hardware constraints. In this work, we develop an algorithm that decomposes the QAOA input problem graph into a smaller problem and solves MaxCut using QAOA on the reduced graph. The algorithm requires a subroutine that can be classical or quantum—in this work, we implement the algorithm twice on each graph. One implementation uses the classical solver Gurobi in the subroutine and the other uses QAOA. We solve these reduced problems with QAOA. On average, the reduced problems require only approximately 1/10 of the number of vertices than the original MaxCut instances. Furthermore, the average approximation ratio of the original MaxCut problems is 0.75, while the approximation ratios of the decomposed graphs are on average of 0.96 for both Gurobi and QAOA. With this decomposition, we are able to measure optimal solutions for ten 100-vertex graphs by running single-layer QAOA circuits on the Quantinuum trapped-ion quantum computer H1-1, sampling each circuit only 500 times. This approach is best suited for sparse, particularly k-regular graphs, as k-regular graphs on n vertices can be decomposed into a graph with at most $\frac{nk}{k+1}$ vertices in polynomial time. Further reductions can be obtained with a potential trade-off in computational time. In conclusion, while this paper applies the decomposition method to the MaxCut problem, it can be applied to more general classes of combinatorial optimization problems.

97 MATHEMATICS AND COMPUTING↗