Remarks on stability of solutions of the property domination problem

A class of combinatorial problems is considered whose investigation and solution require the notions of the theory of fuzzy sets. The necessary and sufficient conditions of stability are given. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 36–40, July–August, 1999.     

Logical problems of systems analysis of organization-and-engineering systems and main ways to solve them

Logical problems of systems analysis of organization-and-engineering systems in the modern industry are discussed. The logical foundations of the systems analysis are analyzed. A methodological function of objective structures in a systems analysis of organization-and-engineering systems is found, and a relationship of these structures as results of analysis and synthesis of objectives is established. The main ways to solve logical problems for systems analysis of organization-and-engineering systems that allow solving logical problems are identified. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 140–147, May–June 2006.     

Multicriteria combinatorial optimization problems on a set of polypermutations

The studies on multicriteria combinatorial optimization are continued. A possible approach to solving multicriterion problems is developed and substantiated. An algorithm is developed and implemented. Some peculiarities of efficient solutions to multicriterion problems are described. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 152–160, March–April 2008.     

Solution of integrated inverse problems for multicomponent hyperbolic distributed systems

The paper presents a technique for developing computational algorithms to solve inverse problems for multicomponent hyperbolic systems with principal and natural heterogeneous conjugation conditions. Explicit expressions for the Frechet derivatives of quadratic residual functionals are obtained to generate gradient computational algorithms. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 55–80, March–April 2008.     

Models of Greedy Algorithms for Graph Problems

Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2]. S. Davis’ research supported by NSF grants CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. R. Impagliazzo’s research supported by NSF grant CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. Some work done while at the Institute for Advanced Study, supported by the State of New Jersey.     

Solving combined inverse problems for multicomponent parabolic distributed systems

The paper outlines a technique to construct computational algorithms for solving combined inverse problems for multicomponent parabolic systems with main and natural inhomogeneous interface conditions. Frechet derivatives are obtained in explicit form for quadratic residual functionals to construct gradient computational algorithms. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 48–71, September–October 2007.     

Subclasses of solvable problems from classes of combinatorial optimization problems

Well-known subclasses of solvable problems from classes of combinatorial optimization are reviewed. For solvable problems such as the traveling salesman problem, location problem, assignment problem, and clustering problem, the changes in the objective function on a given ordering of combinatorial configurations are analyzed. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 97–105, March–April 2009.     

Interval-parameter optimization problems on graphs

Well-known optimization problems on graphs are considered under uncertainty when parameter domains are specified in the form of intervals. Exponential estimates of computational complexity of problems being studied and also problems that are polynomial in the classical formulation are substantiated. Polynomially solvable subclasses are found, and sufficient conditions of statistical efficiency of a proposed approximate algorithm are constructively substantiated. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 3–14, March–April 2009.     

A nonlinear compromise scheme in multicriteria evaluation and optimization problems

The concept of a nonlinear compromise scheme in multicriteria problems of evaluation and optimization is presented. It is shown that the problem is to approximate correctly the utility function and construct a substantial mathematical model (scalar convolution) adequate to the given situation to solve various multicriteria problems. In analysis problems, this convolution is an objective function. Its extremization results in a compromise-optimal vector of arguments. An illustrative example is given. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 106–114, July–August 2009.     

Globally optimal benchmark solutions to some small-scale discretized continuum topology optimization problems

In this note, globally optimal solutions to three sets of small-scale discretized continuum topology optimization problems are presented. All the problems were discretized by the use of nine-node isoparametric finite elements. The idea is that these solutions can be used as benchmark problems when testing new algorithms for finding pure 0–1 solutions to topology optimization problems defined on discretized ground structures.     

Equivalence of deterministic pushdown automata revisited

This paper briefly analyzes main ideas underlying the comparison algorithm that made it possible to prove the equivalence of deterministic pushdown automata. An example of using this algorithm is presented. The relationship of this algorithm with other results in this area is shown. Moreover, the decidability of problems associated with some classes of formal grammars is established. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 24–39, March–April 2007.     

Expansion of weighted pseudoinverse matrices with positive definite weights into matrix power products. Iterative methods

Weighted pseudoinverse matrices with positive definite weights are expanded into matrix power products with negative exponents and arbitrary positive parameters. These expansions are used to develop and analyze iterative methods for evaluating weighted pseudoinverse matrices and weighted normal pseudosolutions and solving constrained least-squares problems. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 45–64, January–February 2007.     

When Ants Attack: Ant Algorithms for Constraint Satisfaction Problems

We describe an ant algorithm for solving constraint problems (Solnon 2002, IEEE Transactions on Evolutionary Computation 6(4): 347–357). We devise a number of variants and carry out experiments. Our preliminary results suggest that the best way to deposit pheromone and the best heuristics for state transitions may differ from current practice     

Representations and expansions of weighted pseudoinverse matrices, iterative methods, and problem regularization. I. Positive definite weights

The paper reviews studies on the representations and expansions of weighted pseudoinverse matrices with positive definite weights and on iterative methods and regularized problems for calculation of weighted pseudoinverse matrices and weighted normal pseudosolutions. The use of these methods to solve constrained least-squares problems is examined. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 47–73, January–February 2008.     

Recognition of fractal graphs

Definitions of prefractal and fractal graphs are introduced, and they are used to formulate mathematical models in different fields of knowledge. The topicality of fractal-graph recognition from the point of view of fundamental improvement in the efficiency of the solution of algorithmic problems is emphasized. The class of polynomial algorithms for recognition of the prefractality of those graphs is proposed and rigorously substantiated. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 72–89, July–August, 1999.     

Series expansion of weighted pseudoinverse matrices and iterative methods for calculating weighted pseudoinverse matrices and weighted normal pseudosolutions

Weighted pseudoinverse matrices are expanded into matrix power series with negative exponents and arbitrary positive parameters. Based on this expansion, iterative methods for evaluating weighted pseudoinverse matrices and weighted normal pseudosolutions are designed and analyzed. The iterative methods for weighted normal pseudosolutions are extended to solving constrained least-squares problems. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 32–62, January–February 2006.     

Representations and expansions of weighted pseudoinverse matrices, iterative methods, and problem regularization. II. Singular weights

The paper reviews studies on the representations and expansions of weighted pseudoinverse matrices with positive semidefinite weights and on the construction of iterative methods and regularized problems for the calculation of weighted pseudoinverses and weighted normal pseudosolutions based on these representations and expansions. The use of these methods to solve constrained least squares problems is examined. Continued from Cybernetics and Systems Analysis, 44, No. 1, 36–55 (2008). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 75–102, May–June 2008.     

An augmented Lagrangian decomposition method for quasi-separable problems in MDO

Several decomposition methods have been proposed for the distributed optimal design of quasi-separable problems encountered in Multidisciplinary Design Optimization (MDO). Some of these methods are known to have numerical convergence difficulties that can be explained theoretically. We propose a new decomposition algorithm for quasi-separable MDO problems. In particular, we propose a decomposed problem formulation based on the augmented Lagrangian penalty function and the block coordinate descent algorithm. The proposed solution algorithm consists of inner and outer loops. In the outer loop, the augmented Lagrangian penalty parameters are updated. In the inner loop, our method alternates between solving an optimization master problem and solving disciplinary optimization subproblems. The coordinating master problem can be solved analytically; the disciplinary subproblems can be solved using commonly available gradient-based optimization algorithms. The augmented Lagrangian decomposition method is derived such that existing proofs can be used to show convergence of the decomposition algorithm to Karush–Kuhn–Tucker points of the original problem under mild assumptions. We investigate the numerical performance of the proposed method on two example problems.     

Enhanced Coercivity for Pure Advection and Advection–Diffusion Problems

We present a common framework in which to set advection problems or advection–diffusion problems in the advection dominated regime, prior to any discretization. It allows one to obtain, in an easy way via enhanced coercivity, a bound on the advection derivative of the solution in a fractional norm of order −1/2. The same bound trivially applies to any Galerkin approximate solution, yielding a stability estimate which is uniform with respect to the diffusion parameter. The proposed formulation is discussed within Fourier methods and multilevel (wavelet) methods, for both steady and unsteady problems.Dedicated to David Gottlieb on the occasion of his 60th Birthday.