Search

Two modifications of the repeated iterated tabu algorithm for solving the quadratic assignment problem (with and without kernel allocation technology) are proposed. These modifications are analyzed and compared with the best modern algorithms for solving this problem. The efficiency of the developed algorithms is shown, in particular, for large-scale problems for which new records were found with their help.

The kernel technology is proposed to solve discrete optimization problems. It forms solution kernel and allows efficient stochastic perturbations of this solution in iterative schemes. Comparative analysis of the two versions of the new algorithm for the quadratic assignment problem (with and without kernel allocation technology) and modern algorithms demonstrated the efficiency of this technology in terms of speed and solution quality. The kernel technology can be easily incorporated into the available algorithms.

A new repeated iterated tabu search for the quadratic assignment problem is developed. A comparative study of this algorithm and the best existing algorithms for solving this problem has shown its competitiveness with respect to both its performance and quality of solutions.

Linear unconstrained problem of combinatorial optimization on arrangements under stochastic uncertainty is being solved. The minimum is defined as the result of sequential comparison of numerical characteristics of random variables. The properties of the solution of the optimization problem under study are obtained. These properties use the properties of special constructed deterministic problems. The authors also propose the reduction method to solve linear unconstrained problem of combinatorial stochastic optimization, which is based on obtained solution's properties.

The paper establishes the necessary condition for the solution of a linear unconditional problem of combinatorial optimization on arrangements where coefficients of objective function are positive. These results are used to establish the properties of the solution of linear unconditional optimization problem on arrangements for the case where probabilistic uncertainty takes place in the definition of the feasible domain and the minimum is defined according to the linear order introduced on the set of discrete random variables: we formulate and prove the condition that can underlie the search for solution and the ways of constructing the solution in some special cases.

The paper proposes a new method to solve the assignment problem based on recursive derivation of the optimal solution. The assignment problem is formulated in the rearrangement matrix form that allows the use of the matrix approach to optimal solution. The algorithm is to find the minimum total weight matching in the bipartite graph with 2n vertices. The computational scheme of the recurrence method for solving the assignment problem is presented in the form adapted for implementation on a computer.

A class of polynomially solvable problems of combinatorial optimization is illustrated by the example of the traveling salesman problem. It is proved that this class includes problems for which the structure of initial data is specially modeled.

A direct cut-off method to solve combinatorial optimization problems on polyarrangements with additional constraints is proposed and justified. The method allows obtaining a feasible solution at each stage without constructing the linear hull of the set of polyarrangements.

The paper proposes a methodology to construct cooperative metaheuristic methods for solving combinatorial optimization problems using model-based algorithms. Its distinctive feature is that the original problem is solved by a search (optimization) in the space of models. Such a search is performed on the basis of models formed by basic algorithms. Cooperative metaheuristics underlain by ant colony optimization and MH-method algorithms are developed, and the efficiency of the proposed methodology is evaluated by means of a computational experiment.

A modification of the combinatorial truncation method for optimization over vertex-located sets is considered. The modification allows dealing with degenerate solutions of auxiliary problems. The form of the truncating inequality is substantiated. An example is given to illustrate the application of the method.

Multicriterion discrete optimization problems over feasible combinatorial sets of polyarrangements are considered. Structural properties of feasible domains and different types of efficient solutions are investigated. Based on the ideas of Euclidean combinatorial optimization and the major criterion method, a polyhedral approach to the solution of the problems is developed and substantiated.

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.

Decision-making criterions are applied to the determination of optimal player's strategies in combinatory game-type optimization problems in which combinatory constraints that are imposed on the strategies of one player are determined by permutations and nature acts as the second player.

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.

The concept of combinatorial objects is formalized. It allows strict definition of a combinatorial optimization problem (COP). An efficient metaheuristic method to solve COPs (H-method) is considered. It includes stochastic local search algorithms as a built-in procedure. A parallel implementation of the H-method is set forth and analyzed. The results from a numerical experiment and solution of some well-known COPs on personal computers and on the SKIT cluster supercomputer are presented.

The paper is concerned with an optimization problem on game-type permutations, where one or both players have combinatorial constraints on their strategies. A mathematical model of such problems is constructed and analyzed. A modified graphical method is proposed to solve (2xn)-and (mx2)-dimensional problems. High-dimensional problems are reduced to linear programming and combinatorial optimization problems.

The statement of a problem of Euclidean combinatorial optimization with a fractional-linear objective function on a common set of permutations and with additional linear constraints is formulated. A problem with a fractional-linear objective function is transformed into that with a linear objective function. An approach is proposed to the solution of such problems, and a method of combinatorial truncation of solutions of problems of combinatorial type with fractional-linear objective functions on permutations is developed.

An exact combinatorial truncation method is proposed for solving Euclidean combinatorial optimization problems on arrangements with a linear objective function and linear additional constraints. An algorithm for this method is developed and justified.

A class of Euclidean combinatorial optimization problems is selected that can be solved by the dynamic programming method. The problem of allocation of servicing enterprises is solved as an example.

Combinatorial configurations of different types are studied. A new point of view is proposed for their classification. Three recurrent combinatorial operators are introduced, and used to form different types of combinatorial configurations.

A new formulation of the quadratic assignment problem is given. Based on the properties of this formulation, new bounds of an objective function are obtained.

In general, the dual solutions are applied in the branch and bound scheme to solve the optimization problem. Of special interest, however, are problems that can be reduced to a quadratic problem with {Omega}-property. In this paper, we consider one such problem, namely the problem of solving a system of polynomial equations in complex variables.