On solving the second basic three-element boundary-value Carleman-type problem in classes of bianalytic functions in a disk

In this paper, we investigate one of the basic Carleman-type boundary-value problems for bianalytic functions. We obtain a constructive method for solving the problem in the case of circular domain. We establish that solving the problem can be reduced to a sequential solving two generalized Carleman-type problems for analytic functions in a disk. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 46, No. 3, pp. 413–426, July–September, 2006.     

Continuous Reformulations for Zero–One Programming Problems

In this work, we study continuous reformulations of zero–one programming problems. We prove that, under suitable conditions, the optimal solutions of a zero–one programming problem can be obtained by solving a specific continuous problem.     

A comparison of two methods for solving 0–1 integer programs using a general purpose simulated annealing algorithm

0–1 problems are often difficult to solve. Although special purpose algorithms (exact as well as heuristic) exist for solving particular problem classes or problem instances, there are few general purpose algorithms for solving practical-sized instances of 0–1 problems. This paper deals with a general purpose heuristic algorithm for 0–1 problems. In this paper, we compare two methods based on simulated annealing for solving general 0–1 integer programming problems. The two methods differe in the scheme used for neighbourhood transitions in the simulated annealing framework. We compare the performance of the two methods on the set partitioning problem.     

An extended Gauss–Seidel method for a class of multi-valued complementarity problems

The complementarity problem is one of the basic topics in nonlinear analysis; however, the methods for solving complementarity problems are usually developed for problems with single-valued mappings. In this paper we examine a class of complementarity problems with multi-valued mappings and propose an extension of the Gauss–Seidel algorithm for finding its solution. Its convergence is proved under off-diagonal antitonicity assumptions. Applications to Walrasian type equilibrium problems and to nonlinear input–output problems are also given. In this work, the authors were supported by Brescia University grant PRIN - 2006: “Oligopolistic models and order monotonicity properties”, the third author was also supported by the joint RFBR–NNSF grant, project No. 07-01-92101.     

Solving ODEs arising from non‐selfadjoint Hamiltonian eigenproblems

We consider three numerical methods – one based on power series, one on the Magnus series and matrix exponentials, and one a library initial value code – for solving a linear system arising in non‐selfadjoint ODE eigenproblems. We show that in general, none of these methods has a cost or an accuracy which is uniform in the eigenparameter, but that for certain special types of problem, the Magnus method does yield eigenparameter‐uniform accuracy. This property of the Magnus method is explained by a trajectory‐shadowing result which, unfortunately, does not generalize to higher order Magnus type methods such as those in [11,12]. This revised version was published online in June 2006 with corrections to the Cover Date.     

Comparative studies on dynamic programming and integer programming approaches for concave cost production/inventory control problems

This paper is concerned with classical concave cost multi-echelon production/inventory control problems studied by W. Zangwill and others. It is well known that the problem with m production steps and n time periods can be solved by a dynamic programming algorithm in O(n ⁴ m) steps, which is considered as the fastest algorithm for solving this class of problems. In this paper, we will show that an alternative 0–1 integer programming approach can solve the same problem much faster particularly when n is large and the number of 0–1 integer variables is relatively few. This class of problems include, among others problem with set-up cost function and piecewise linear cost function with fewer linear pieces. The new approach can solve problems with mixed concave/convex cost functions, which cannot be solved by dynamic programming algorithms.     

A Particle Swarm Optimization Algorithm with Path Relinking for the Location Routing Problem

This paper introduces a new hybrid algorithmic nature inspired approach based on particle swarm optimization, for solving successfully one of the most popular logistics management problems, the location routing problem (LRP). The proposed algorithm for the solution of the location routing problem, the hybrid particle swarm optimization (HybPSO-LRP), combines a particle swarm optimization (PSO) algorithm, the multiple phase neighborhood search – greedy randomized adaptive search procedure (MPNS-GRASP) algorithm, the expanding neighborhood search (ENS) strategy and a path relinking (PR) strategy. The algorithm is tested on a set of benchmark instances. The results of the algorithm are very satisfactory for these instances and for six of them a new best solution has been found.      

The Diffie–Hellman problem and generalization of Verheul’s theorem

Bilinear pairings on elliptic curves have been of much interest in cryptography recently. Most of the protocols involving pairings rely on the hardness of the bilinear Diffie–Hellman problem. In contrast to the discrete log (or Diffie–Hellman) problem in a finite field, the difficulty of this problem has not yet been much studied. In 2001, Verheul (Advances in Cryptology—EUROCRYPT 2001, LNCS 2045, pp. 195–210, 2001) proved that on a certain class of curves, the discrete log and Diffie–Hellman problems are unlikely to be provably equivalent to the same problems in a corresponding finite field unless both Diffie–Hellman problems are easy. In this paper we generalize Verheul’s theorem and discuss the implications on the security of pairing based systems.      

A projected–gradient interior–point algorithm for complementarity problems

Interior–point algorithms are among the most efficient techniques for solving complementarity problems. In this paper, a procedure for globalizing interior–point algorithms by using the maximum stepsize is introduced. The algorithm combines exact or inexact interior–point and projected–gradient search techniques and employs a line–search procedure for the natural merit function associated with the complementarity problem. For linear problems, the maximum stepsize is shown to be acceptable if the Newton interior–point search direction is employed. Complementarity and optimization problems are discussed, for which the algorithm is able to process by either finding a solution or showing that no solution exists. A modification of the algorithm for dealing with infeasible linear complementarity problems is introduced which, in practice, employs only interior–point search directions. Computational experiments on the solution of complementarity problems and convex programming problems by the new algorithm are included.     

On the Computational Complexity of the Minimum Committee Problem

Two special cases of the Minimum Committee Problem are studied, the Minimum Committee Problem of Finite Sets (MCFS) and the Minimum Committee Problem of a System of Linear Inequalities(MCLE). It is known that the first of these problems is NP-hard (see (Mazurov et al., Proc. Steklov Inst. Math., 1:67–101, 2002)). In this paper we show the NP-hardness of two integer optimization problems connected with it. In addition, we analyze the hardness of approximation to the MCFS problem. In particular, we show that, unless NP⊂TIME(n ^O(loglogn )), for every ε>0 there are no approximation algorithms for this problem with approximation ratio (1–ε)ln (m–1), where m is the number of inclusions in the MCFS problem. To prove this bound we use the SET COVER problem, for which a similar result is known (Feige, J. ACM, 45:634–652, 1998). We also show that the Minimum Committee of Linear Inequalities System (MCLE) problem is NP-hard as well and consider an approximation algorithm for this problem.      

Expanding neighborhood search–GRASP for the probabilistic traveling salesman problem

The Probabilistic Traveling Salesman Problem is a variation of the classic traveling salesman problem and one of the most significant stochastic routing problems. In probabilistic traveling salesman problem only a subset of potential customers need to be visited on any given instance of the problem. The number of customers to be visited each time is a random variable. In this paper, a variant of the well-known Greedy Randomized Adaptive Search Procedure (GRASP), the Expanding Neighborhood Search–GRASP, is proposed for the solution of the probabilistic traveling salesman problem. expanding neighborhood search–GRASP has been proved to be a very efficient algorithm for the solution of the traveling salesman problem. The proposed algorithm is tested on a numerous benchmark problems from TSPLIB with very satisfactory results. Comparisons with the classic GRASP algorithm and with a Tabu Search algorithm are also presented. Also, a comparison is performed with the results of a number of implementations of the Ant Colony Optimization algorithm from the literature and in six out of ten cases the proposed algorithm gives a new best solution.     

Scatter Search for the 0–1 Multidimensional Knapsack Problem

The evolutionary metaheuristic called scatter search has been applied successfully to optimization problems for several years. In this paper, we apply the scatter search technique to the well-known 0–1 multidimensional knapsack problem. We propose a new relaxation-based diversification generator, which produces an initial population with elite solutions. The computational results obtained for a set of classic and correlated instances clearly show that (1) this generator can also be used as a heuristic for solving the multidimensional knapsack problem; (2) using the population produced by our generator as a starting point for the scatter search algorithm leads to better performance. We also enhance the scatter search algorithm by integrating memory and by using adapted intensification phases. Overall, the results are interesting and competitive compared to other population-based algorithms, such as genetic algorithms.      

A quadratically constrained minimization problem arising from PDE of Monge–Ampère type

This note develops theory and a solution technique for a quadratically constrained eigenvalue minimization problem. This class of problems arises in the numerical solution of fully-nonlinear boundary value problems of Monge–Ampère type. Though it is most important in the three dimensional case, the solution method is directly applicable to systems of arbitrary dimension. The focus here is on solving the minimization subproblem which is part of a method to numerically solve a Monge–Ampère type equation. These subproblems must be evaluated many times in this numerical solution technique and thus efficiency is of utmost importance. A novelty of this minimization algorithm is that it is finite, of complexity O(n³)\mathcal{O}(n^3), with the exception of solving a very simple rational function of one variable. This function is essentially the same for any dimension. This result is quite surprising given the nature of the constrained minimization problem.     

Problem of quality for a certain linear differential game with critical properties

A solution to the pursuit problem for one linear differential game, critical in the sense that it lies on the boundary of solvability of the approach and evasion problems, is given. The result thus obtained is used to answer two question connected with Pontryagin’s methods. Translated fromMatematicheskie Zametki, Vol. 67, No. 4, pp. 484–488, April, 2000.     

To solving problems of algebra for two-parameter matrices. III

The paper continues the series of papers devoted to surveying and developing methods for solving algebraic problems for two-parameter polynomial and rational matrices of general form. It considers linearization methods, which allow one to reduce the problem of solving an equation F(λ, μ)x = 0 with a polynomial two-parameter matrix F(λ, μ) to solving an equation of the form D(λ, μ)y = 0, where D(λ, μ) = A(μ)-λB(μ) is a pencil of polynomial matrices. Consistent pencils and their application to solving spectral problems for the matrix F(λ, μ) are discussed. The notion of reducing subspace is generalized to the case of a pencil of polynomial matrices. An algorithm for transforming a general pencil of polynomial matrices to a quasitriangular pencil is suggested. For a pencil with multiple eigenvalues, algorithms for computing the Jordan chains of vectors are developed. Bibliography: 8 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 359, 2008, pp. 166–207.     

An alternating method for Cauchy problems for Helmholtz-type operators in non-homogeneous medium

Kozlov & Maz'ya (1989, Algebra Anal., 1, 144–170)proposed an alternating iterative method for solving Cauchyproblems for general strongly elliptic and formally self-adjointsystems. However, in many applied problems, operators appearthat do not satisfy these requirements, e.g. Helmholtz-typeoperators. Therefore, in this study, an alternating procedurefor solving Cauchy problems for self-adjoint non-coercive ellipticoperators of second order is presented. A convergence proofof this procedure is given.     

The Gibbs Cloner for Combinatorial Optimization, Counting and Sampling

We present a randomized algorithm, called the cloning algorithm, for approximating the solutions of quite general NP-hard combinatorial optimization problems, counting, rare-event estimation and uniform sampling on complex regions. Similar to the algorithms of Diaconis–Holmes–Ross and Botev–Kroese the cloning algorithm is based on the MCMC (Gibbs) sampler equipped with an importance sampling pdf and, as usual for randomized algorithms, it uses a sequential sampling plan to decompose a “difficult” problem into a sequence of “easy” ones. The cloning algorithm combines the best features of the Diaconis–Holmes–Ross and the Botev–Kroese. In addition to some other enhancements, it has a special mechanism, called the “cloning” device, which makes the cloning algorithm, also called the Gibbs cloner fast and accurate. We believe that it is the fastest and the most accurate randomized algorithm for counting known so far. In addition it is well suited for solving problems associated with the Boltzmann distribution, like estimating the partition functions in an Ising model. We also present a combined version of the cloning and cross-entropy (CE) algorithms. We prove the polynomial complexity of a particular version of the Gibbs cloner for counting. We finally present efficient numerical results with the Gibbs cloner and the combined version, while solving quite general integer and combinatorial optimization problems as well as counting ones, like SAT.     

How does imposing a step-by-step solution method impact students’ approach to mathematical word problem solving?

This paper presents the second phase of a larger research program with the purpose of exploring the possible consequences of a gap between what is done in the classroom regarding mathematical word problem solving and what research shows to be effective in this particular field of study. Data from the first phase of our study on teachers’ self-proclaimed practices showed that one-third of elementary teachers from the region of Quebec require their students to follow a specific sequential problem-solving method, known as the ‘what I know, what I look for’ method. These results led us to hypothesize that the observed gap may have an impact on students’ comprehension of mathematical word problems. The use of this particular method was the foundation for us to study, in the second phase, the effect of the imposition of this sequential method on students’ literal and inferential understanding of word problems. A total of 278 fourth graders (9–10 years old) solved mathematical word problems followed by a test to assess their understanding of the word problems they had just solved. The results suggest that the use of this problem solving method does not seem to improve or impair students’ understanding. From a more fundamental point of view, our study led us to the conclusion that the way word problem solving is addressed in the mathematics classroom, through sequential and inflexible methods, does not help students develop their word problem solving competence.     

Inverse complementarity in a resource deficit model

The concept of inverse complementarity for a parametric family of optimization problems is introduced. This concept is an effective tool for solving complicated applied problems arising in socioeconomic systems. As an example, a nonlinear resource deficit model is constructed in which the equilibrium is characterized by an external market value of resources coinciding with internal objectively determined resource estimates. An extraproximal method is proposed for computing an equilibrium solution. The convergence of the method is proved. Original Russian Text. A.V. Zykina, 2008, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2008, Vol. 48, No. 11, pp. 1968–1978.     

The Method of Singular Equations in Boundary Value Problems in Kinetic Theory

We develop a new effective method for solving boundary value problems in kinetic theory. The method permits solving boundary value problems for mirror and diffusive boundary conditions with an arbitrary accuracy and is based on the idea of reducing the original problem to two problems of which one has a diffusion boundary condition for the reflection of molecules from the wall and the other has a mirror boundary condition. We illustrate this method with two classical problems in kinetic theory: the Kramers problem (isothermal slip) and the thermal slip problem. We use the Bhatnagar-Gross-Krook equation (with a constant collision frequency) and the Williams equation (with a collision frequency proportional to the molecular velocity).__________Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 143, No. 3, pp. 437–454, June, 2005.