We present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. The follower must solve an optimization problem that has been previously perturbed by means of a series of attacking actions led by the attacker. These attacking actions aim at augmenting the cost of the decision variables of the follower’s optimization problem. The objective, from the attacker’s viewpoint, is that of choosing an attacking strategy that reduces as much as possible the quality of the optimal solution attainable by the follower. The progressive approximation mechanism consists of the iterative solution of an interdiction problem in which the attacker actions are restricted to a subset of the whole solution space and a pricing subproblem invoked with the objective of proving the optimality of the attacking strategy. This scheme is especially useful when the optimal solutions to the follower’s subproblem intersect with the decision space of the attacker only in a small number of decision variables. In such cases, the progressive approximation method can solve interdiction games otherwise intractable for classical methods. We illustrate the efficiency of our approach on the shortest path, 0-1 knapsack and facility location interdiction games. Summary of Contribution: In this article, we present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. We exploit the discrete nature of this interdiction game to design an effective algorithmic framework that improves the performance of general-purpose solvers. Our algorithm combines elements from mathematical programming and computer science, including a metaheuristic algorithm, a binary search procedure, a cutting-planes algorithm, and supervalid inequalities. Although we illustrate our results on three specific problems (shortest path, 0-1 knapsack, and facility location), our algorithmic framework can be extended to a broader class of interdiction problems.
more »
« less
A note on co-dimension 2 defects in N = 4,d = 7 gauged supergravity
In this note we present a solution of N=4,d=7
gauged supergravity which is holographically dual to a co-dimension two defect living in a six dimensional SCFT. The solution is obtained by double analytic continuation of a two charge supersymmetric black hole solution. The condition that no conical deficits are present in the bulk and on the boundary is satisfied by a one parameter family of solutions for which some holographic observables are computed.
more »
« less
- Award ID(s):
- 1914412
- NSF-PAR ID:
- 10466690
- Publisher / Repository:
- Elsevier
- Date Published:
- Journal Name:
- Nuclear Physics B
- Volume:
- 984
- Issue:
- C
- ISSN:
- 0550-3213
- Page Range / eLocation ID:
- 115969
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We present a discontinuity aware quadrature (DAQ) rule and use it to develop implicit self-adaptive theta (SATh) schemes for the approximation of scalar hyperbolic conservation laws. Our SATh schemes require the solution of a system of two equations, one controlling the cell averages of the solution at the time levels, and the other controlling the space-time averages of the solution. These quantities are used within the DAQ rule to approximate the time integral of the hyperbolic flux function accurately, even when the solution may be discontinuous somewhere over the time interval. The result is a finite volume scheme using the theta time stepping method, with theta defined implicitly (or self-adaptively). Two schemes are developed, self-adaptive theta upstream weighted (SATh-up) for a monotone flux function using simple upstream stabilization, and self-adaptive theta Lax–Friedrichs (SATh-LF) using the Lax–Friedrichs numerical flux. We prove that DAQ is accurate to second order when there is a discontinuity in the solution and third order when it is smooth. We prove that SATh-up is unconditionally stable, provided that theta is set to be at least 1/2 (which means that SATh can be only first order accurate in general). We also prove that SATh-up satisfies the maximum principle, and is total variation diminishing under appropriate monotonicity and boundary conditions. General flux functions require the SATh-LF scheme, so we assess its accuracy through numerical examples in one and two space dimensions. These results suggest that SATh-LF is also stable and satisfies the maximum principle (at least at reasonable Courant-Friedrichs-Lewy numbers). Compared to the solutions of finite volume schemes using Crank–Nicolson and backward Euler time stepping, SATh-LF solutions often approach the accuracy of the former, but without oscillation, and they are numerically less diffuse than the latter.more » « less
-
Excess electrons in liquid acetonitrile are of particular interest because they exist in two different forms in equilibrium: they can be present as traditional solvated electrons in a cavity, and they can form some type of solvated molecular anion. Studies of small acetonitrile cluster anions in the gas phase show two isomers with distinct vertical detachment energies, and it is tempting to presume that the two gas-phase cluster anion isomers are precursors of the two excess electron species present in bulk solution. In this paper, we perform DFT-based ab initio molecular dynamics simulations of acetonitrile cluster anions to understand the electronic species that are present and why they have different binding energies. Using a long-range-corrected density functional that was optimally tuned to describe acetonitrile cluster anion structures, we have theoretically explored the chemistry of (CH3CN)n¯ cluster anions with sizes n=5,7 and 10. Since the temperature of the experimental cluster anions is not known, we performed two sets of simulations that investigated how the way in which the cluster anions are prepared affects the excess electron binding motif: one set of simulations simply attached excess electrons to neutral (CH3CN)n clusters, providing little opportunity for the clusters to relax in the presence of the excess electron, while the other set allowed the cluster anions to thermally equilibrate near room temperature. We find that both sets of simulations show three distinct electron binding motifs: electrons can attach to the surface of the cluster (dipole-bound) or be present as either solvated monomer anions, CH3CN¯, or as solvated molecular dimer anions, (CH3CN)2¯. All three species have higher binding energies at larger cluster sizes. Thermal equilibration strongly favors the formation of the valence-bound molecular anions relative to surface-bound excess electrons, and the dimer anion becomes more stable than the monomer anion and surface-bound species as the cluster size increases. The calculated photoelectron spectra from our simulations in which there was poor thermal equilibration are in good agreement with experiment, suggesting assignment of the two experimental cluster anion isomers as the surface-bound electron and the solvated molecular dimer anion. The simulations also suggest that the shoulder seen experimentally on the low-energy isomer's detachment peak is not part of a vibronic progression but instead results from molecular monomer anions. Nowhere in the size range that we explore do we see evidence for a non-valence, cavity-bound interior-solvated electron, indicating that this species is likely only accessible at larger sizes with good thermal equilibration.more » « less
-
more » « less
We extend a recently proposed kinetic theory of virus capsid assembly based on Model A kinetics and study the dynamics of the interconversion of virus capsids of different sizes triggered by a quench, that is, by sudden changes in the solution conditions. The work is inspired by in vitro experiments on functionalized coat proteins of the plant virus cowpea chlorotic mottle virus, which undergo a reversible transition between two different shell sizes (T = 1 and T = 3) upon changing the acidity and salinity of the solution. We find that the relaxation dynamics are governed by two time scales that, in almost all cases, can be identified as two distinct processes. Initially, the monomers and one of the two types of capsids respond to the quench. Subsequently, the monomer concentration remains essentially constant, and the conversion between the two capsid species completes. In the intermediate stages, a long-lived metastable steady state may present itself, where the thermodynamically less stable species predominate. We conclude that a Model A based relaxational model can reasonably describe the early and intermediate stages of the conversion experiments. However, it fails to provide a good representation of the time evolution of the state of assembly of the coat proteins in the very late stages of equilibration when one of the two species disappears from the solution. It appears that explicitly incorporating the nucleation barriers to assembly and disassembly is crucial for an accurate description of the experimental findings, at least under conditions where these barriers are sufficiently large.
-
null (Ed.)We present data-driven coarse-grained (CG) modeling for polymers in solution, which conserves the dynamic as well as structural properties of the underlying atomistic system. The CG modeling is built upon the framework of the generalized Langevin equation (GLE). The key is to determine each term in the GLE by directly linking it to atomistic data. In particular, we propose a two-stage Gaussian process-based Bayesian optimization method to infer the non-Markovian memory kernel from the data of the velocity autocorrelation function (VACF). Considering that the long-time behaviors of the VACF and memory kernel for polymer solutions can exhibit hydrodynamic scaling (algebraic decay with time), we further develop an active learning method to determine the emergence of hydrodynamic scaling, which can accelerate the inference process of the memory kernel. The proposed methods do not rely on how the mean force or CG potential in the GLE is constructed. Thus, we also compare two methods for constructing the CG potential: a deep learning method and the iterative Boltzmann inversion method. With the memory kernel and CG potential determined, the GLE is mapped onto an extended Markovian process to circumvent the expensive cost of directly solving the GLE. The accuracy and computational efficiency of the proposed CG modeling are assessed in a model star-polymer solution system at three representative concentrations. By comparing with the reference atomistic simulation results, we demonstrate that the proposed CG modeling can robustly and accurately reproduce the dynamic and structural properties of polymers in solution.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1016/j.nuclphysb.2022.115969
