Inverse problem for a quasilinear hyperbolic equation with a nonlocal boundary condition containing a delay argument

We consider a problem for a quasilinear hyperbolic equation with a nonlocal condition that contains a retarded argument. By reducing this problem to a nonlinear integrofunctional equation, we prove the existence and uniqueness theorem for its solution. We pose an inverse problem of finding a solution-dependent coefficient of the equation on the basis of additional information on the solution; the information is given at a fixed point in space and is a function of time. We prove the uniqueness theorem for the solution of the inverse problem. The proof is based on the derivation and analysis of an integro-functional equation for the difference of two solutions of the inverse problem.     

Application of the Laplace transform to the analysis of a mixed problem describing the vibrations of a compound rod

We suggest a method for finding a closed-form expression for the solution of the mixed problem on the vibrations excited in a compound rod by boundary conditions of the first, second, and third kind. The method uses the Laplace transform. We also suggest one possible numerical method for finding the solution.     

Finite-time singularity formation at a magnetic neutral line in Hall magnetohydrodynamics

The formation of a current sheet in a weakly collisional plasma can be modelled as a finite-time singularity solution of magnetohydrodynamic equations. We use an exact self-similar solution to confirm and generalise a previous finding that, in sharp contrast to two-dimensional solutions in standard MHD, a finite-time collapse to a current sheet can occur in Hall MHD. We derive a criterion for the finite-time singularity in terms of initial conditions, and we use an intermediate asymptotic solution for the evolution of an axial magnetic field to obtain a general expression for the singularity formation time. We illustrate the analytical results by numerical solutions.     

An algorithm for finding a matroid basis which maximizes the product of the weights of the elements

Consider the problem of finding a spanning tree in an edge-weighted connected graph that maximizes the product of its edge weights, where negative edge weights are allowed. We generalize this problem to matroids and give a polynomial time algorithm for its solution.     

Inverse problem for a pseudoparabolic equation with integral overdetermination conditions

We consider inverse problems of finding an unknown coefficient in the leading term of a linear pseudoparabolic equation of filtration type on the basis of integral data over the entire boundary or its part under the assumption that the unknown coefficient depends on time. We derive conditions for the time-global solvability and uniqueness of the solution of the inverse problem.     

Inverse problem of finding the coefficient of a lower derivative in a parabolic equation on the plane

We study the existence and uniqueness of the solution of the inverse problem of finding an unknown coefficient b(x) multiplying the lower derivative in the nondivergence parabolic equation on the plane. The integral of the solution with respect to time with some given weight function is given as additional information. The coefficients of the equation depend on the time variable as well as the space variable.     

Determination of the Spectral Index of Ergodicity of a Birth-and-Death Process

We obtain a new explicit relation for the calculation of the spectral index of ergodicity of a birth-and-death process with continuous time. The calculation of the index is reduced to the solution of an optimization problem of nonlinear programming that contains the infinitesimal matrix of the process. As an example, we use the proposed method for finding the exact values of the indices of exponential ergodicity for certain Markov queuing systems.     

On the empirical scaling of running time for finding optimal solutions to the TSP

We study the empirical scaling of the running time required by state-of-the-art exact and inexact TSP algorithms for finding optimal solutions to Euclidean TSP instances as a function of instance size. In particular, we use a recently introduced statistical approach to obtain scaling models from observed performance data and to assess the accuracy of these models. For Concorde, the long-standing state-of-the-art exact TSP solver, we compare the scaling of the running time until an optimal solution is first encountered (the finding time) and that of the overall running time, which adds to the finding time the additional time needed to complete the proof of optimality. For two state-of-the-art inexact TSP solvers, LKH and EAX, we compare the scaling of their running time for finding an optimal solution to a given instance; we also compare the resulting models to that for the scaling of Concorde’s finding time, presenting evidence that both inexact TSP solvers show significantly better scaling behaviour than Concorde.     

A recurrence method for a special class of continuous time linear programming problems

This article studies a numerical solution method for a special class of continuous time linear programming problems denoted by (SP). We will present an efficient method for finding numerical solutions of (SP). The presented method is a discrete approximation algorithm, however, the main work of computing a numerical solution in our method is only to solve finite linear programming problems by using recurrence relations. By our constructive manner, we provide a computational procedure which would yield an error bound introduced by the numerical approximation. We also demonstrate that the searched approximate solutions weakly converge to an optimal solution. Some numerical examples are given to illustrate the provided procedure.     

Nodal aggregation of resource constraints in a shortest path problem

The shortest path problem with resource constraints consists of finding the minimum cost path between two specified points while respecting constraints on resource consumption. Its solving by a dynamic programming algorithm requires a computation time increasing with the number of resources. With the aim of producing rapidly a good heuristic solution we propose to reduce the state space by aggregating resources. Our approach consists of projecting the resources on a vector of smaller dimension and then to dynamically adjust the projection matrix to get a better approximation of the optimal solution. We propose an adjustment based on Lagrangian and surrogate relaxations in a column generation framework, in which the sub-problems are shortest path problems with resource constraints. We adjust the multipliers only one time at each column generation iteration. This permit to obtain good solutions of the scheduling problem in few time.     

Adaptive Interpolation Algorithm Based on a kd-Tree for Numerical Integration of Systems of Ordinary Differential Equations with Interval Initial Conditions

We consider issues related to the numerical solution of interval systems of ordinary differential equations. We suggest an algorithm that permits finding interval estimates of solutions with prescribed accuracy in reasonable time. The algorithm constructs an adaptive partition (a dynamic structured grid) based on a kd-tree over the space formed by interval initial conditions for the ordinary differential equations. In the operation of the algorithm, a piecewise polynomial function interpolating the dependence of the solution on the specific values of interval parameters is constructed at each step of solution of the original problem. We prove that the global error estimate linearly depends on the height of the kd-tree. The algorithm is tested on several examples; the test results show its efficiency when solving problems of the class under study.     

Solvability of the Inverse Problem of Finding Thermal Conductivity

We study the inverse problem of finding the coefficient of thermal conductivity of the heat equation (along with the solution). As the overdetermination condition we take the values of the solution at the final time. Existence of a regular solution is proven.     

A stability estimate for a solution to an inverse problem of electrodynamics

We consider the integrodifferential system of equations of electrodynamics which corresponds to a dispersive nonmagnetic medium. For this system we study the problem of determining the spatial part of the kernel of the integral term. This corresponds to finding the part of dielectric permittivity depending nonlinearly on the frequency of the electromagnetic wave. We assume that the support of dielectric permittivity lies in some compact domain Ω ⊂ ℝ³. In order to find it inside Ω we start with known data about the solution to the corresponding direct problem for the equations of electrodynamics on the whole boundary of Ω for some finite time interval. On assuming that the time interval is sufficiently large we estimate the conditional stability of the solution to this inverse problem.     

An integer linear programming approach for a class of bilinear integer programs

We propose an Integer Linear Programming (ILP) approach for solving integer programs with bilinear objectives and linear constraints. Our approach is based on finding upper and lower bounds for the integer ensembles in the bilinear objective function, and using the bounds to obtain a tight ILP reformulation of the original problem, which can then be solved efficiently. Numerical experiments suggest that the proposed approach outperforms a latest iterative ILP approach, with notable reductions in the average solution time.     

Numerical identification of the leading coefficient of a parabolic equation

For a multidimensional parabolic equation, we study the problem of finding the leading coefficient, which is assumed to depend only on time, on the basis of additional information about the solution at an interior point of the computational domain. For the approximate solution of the nonlinear inverse problem, we construct linearized approximations in time with the use of ordinary finite-element approximations with respect to space. The numerical algorithm is based on a special decomposition of the approximate solution for which the transition to the next time level is carried out by solving two standard elliptic problems. The capabilities of the suggested numerical algorithm are illustrated by the results of numerical solution of a model inverse two-dimensional problem.     

Parametrization of a solution at bifurcation points

We suggest algorithms for finding bifurcation points numerically. The suggested approach is based on the method of extension of a solution with respect to the best parameter. We prove theorems and analyze specific features and properties of algorithms, whose efficiency is illustrated by numerical examples.     

Weakly nonlinear boundary-value problem in a special critical case

We investigate the problem of the determination of conditions for the existence of solutions of weakly nonlinear Noetherian boundary-value problems for systems of ordinary differential equations and the construction of these solutions. We consider the special critical case where the equation for finding the generating solution of a weakly nonlinear Noetherian boundary-value problem turns into an identity. We improve the classification of critical cases and construct an iterative algorithm for finding solutions of weakly nonlinear Noetherian boundary-value problems in the special critical case.     

Inverse problems for a quasilinear hyperbolic equation in the case of moving observation point

We consider two inverse coefficient problems for a quasilinear hyperbolic equation, where the additional information used for finding the coefficients is the values of the solution on some curve. (This corresponds to measurements performed at a moving observation point.) The unknown coefficient depends on the space variable in the first inverse problem and on the solution of the equation in the second inverse problem. We prove theorems of uniqueness of solution to the inverse problems.     

On a linear nth-order differential equation with special right-hand side in a Banach space

We show that the classical algorithm for finding a particular solution of a scalar linear differential equation can be applied to linear differential equations with bounded operator coefficients in a Banach space.     

Explicit Solutions for the Wave Equation on Homogeneous Trees

In this paper we consider the discretized version of the wave equation, in which a manifold is replaced by a homogeneous tree and the time line is replaced by the natural numbers. We give two methods for finding a closed form of the solution. One of these methods is found by first solving the Radon transform of the solution, which has a much simpler form. We also find a simple formula for the Radon transformation of the solution to the heat equation on homogeneous trees.