An approach to estimating the complexity of probabilistic procedures for the postoptimality analysis of discrete optimization problems

It is shown that ZPP- and RP-probabilistic polynomial postoptimality analysis procedures for finding an optimal solution of a set cover problem that differs from the original problem in one position of the constraints matrix do not exist if an optimal solution of the original problem is known and if ZPP ?? NP (RP ?? NP). A similar result holds for the knapsack problem.     

On estimates of the complexity of numerical characteristics of postoptimality analysis for discrete optimization problems

A function is introduced that characterizes the complexity of postoptimality analysis of discrete optimization problems. For this function, the upper O(2^poly(n)) and lower \( \Omega \left( {\frac{{{2^n}}}{{\sqrt {{n + 1}} }}} \right) \) 2 bounds are obtained in the class of branch and bound methods for the knapsack problem. A class of set covering problems with a polynomial estimate of this function is observed     

Multiheuristic approach to discrete optimization problems

In this paper, some heuristic decision-making techniques (methods) are considered that are used in various discrete optimization problems. The objective of each of these problems is the construction of anytime algorithms. The considered methods for solving these problems are constructed on the basis of a combination of some heuristics that belong to different areas of the theory of artificial intelligence. A brief variant of the present article is presented in [1]. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 32–42, May–June 2006.     

An approach to solving discrete vector optimization problems over a combinatorial set of permutations

Complex discrete multicriteria problems over a combinatorial set of permutations are analyzed. Some properties of an admissible domain for a combinatorial multicriteria problem embedded into an arithmetic Euclidian space are considered. Optimality conditions are obtained for different types of effective solutions. A new approach to solving the problems formulated is constructed and substantiated. This work was supported by the Fundamental Research Fund of Ukraine (project Φ251/094). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 158–172, May–June 2008.     

A hybrid continuous-discrete approach to large discrete structural optimization problems

Many optimum structural designs are based on searching for the best of all combinations, arising from the number of structural members, and parameters of listed rolled profiles. Even, in a relatively simple design, the number of such combinations is of an order higher than ten. All known methods of finding discrete minimum of structural weight require very large number of analyses often of an order of four. In this study, a relatively simple method of solving such problems is presented. It is based on a tree graph, representing discrete values of the structural volume. The structure can be subjected to multi static loadings with constraints imposed on displacements and stresses. The number of analyses, in the proposed algorithm, is limited to the order of two. The knowledge needed to apply the method is limited to FEM and graph representation. The paper is illustrated with two examples with numbers of combinations up to 42³⁸.     

An approach to the formal analysis of user complexity

A formal approach to analysing the user complexity of interactive systems or devices is described, based on theoretical results from cognitive psychology. The user's knowledge of how to use a system to accomplish the various tasks is represented in a procedural notation that permits quantification of the amount and complexity of the knowledge required and the cognitive processing load involved in using a system. Making a system more usable can be accomplished by altering its design until the knowledge is adequately simplified. By representing the device behaviour formally as well, it is possible to simulate the user-device interaction to obtain rigorous measures of user complexity.     

An approach to the solution of nonlinear unconstrained optimization problems

An approach to reducing a constrained convex programming problem to an unconstrained optimization problem is considered. An initial internal feasible point is supposed to be specified. An equivalent unconstrained optimization problem is formulated in such a way that the calculated values of gradients (subgradients) of original functions do not violate the initial constraints. Properties of introduced functions are investigated. Convexity conditions are formulated for the unconstrained optimization problem. The results may by useful for the development of algorithms for solving constrained optimization problems.     

An approach to multicriterion optimization problems for engineering design

Optimization problems in mechanical engineering design are often modelled as nonlinear programming problems. A multicriterion optimization approach to this problem is developed in this work. The problem formulation is given, and the min-max principle for this problem is discussed. Next, an algorithm is provided for comparing solutions using this principle.The solution which is defined by the min-max principle of optimality may be called the best compromise considering all the criteria simultaneously and on equal terms of importance. This principle is fully formalized mathematically and used to obtain the optimal solution automatically. The algorithm for comparing solutions gives us, from any set of solutions, the one which is optimal in the min-max sense.Seeking the optimal solution in the min-max sense can be carried out in many different ways. Some methods based upon the Monte Carlo method and trade-off studies are proposed.The approach as discussed here is applied to the design of machine tool gearboxes. The problem is formulated as finding the basic constructional parameters (modules, numbers of teeth etc.) of a gearbox which minimizes simultaneously four objective functions: volume of elements, peripheral velocity between gears, width of gearbox and distance between axes of input and output shafts. A detailed example considering a lathe gearbox optimization problem is also presented. This example indicates that for some mechanical engineering optimization problems, using this approach, we can automatically obtain a solution which is optimal and acceptable to the designer.     

Stability of discrete optimization problems

The study was financed by the State Fund for Basic Research of the State Committee of the Science of Technology of Ukraine.     

Firefly-inspired algorithm for discrete optimization problems: An application to manufacturing cell formation

The canonical firefly algorithm is basically developed for continuous optimization problems. However, lots of practical problems are formulated as discrete optimization problems. The main purpose of this paper is to present the discrete firefly algorithm (DFA) to solve discrete optimization problems. In the DFA, we define a firefly's position in terms of changes of probabilities that will be in one state or the other. Then by using this metaheuristic algorithm, the manufacturing cell formation problem is solved. To illustrate the behavior of the proposed model and verify the performance of the algorithm, we introduce a number of numerical examples to illustrate the use of the foregoing algorithm. The performance evaluation shows the effectiveness of the DFA. The proposed metaheuristic algorithm should thus be useful to both researchers and practitioners.     

Penalty function approach for the mixed discrete nonlinear problems by particle swarm optimization

In this paper, the basic characteristics of particle swarm optimization (PSO) for the global search are discussed at first, and then the PSO for the mixed discrete nonlinear problems (MDNLP) is suggested. The penalty function approach to handle the discrete design variables is employed, in which the discrete design variables are handled as the continuous ones by penalizing at the intervals. As a result, a useful method to determine the penalty parameter of penalty term for the discrete design variables is proposed. Through typical mathematical and structural optimization problems, the validity of the proposed approach for the MDNLP is examined.     

Completeness of vector discrete optimization problems

Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 75–83, September–October, 1994.     

On the parameterized complexity of some optimization problems related to multiple-interval graphs

We show that for any constant t≥2, k-Independent Set and k-Dominating Set in t-track interval graphs are W[1]-hard. This settles an open question recently raised by Fellows, Hermelin, Rosamond, and Vialette. We also give an FPT algorithm for k-Clique in t-interval graphs, parameterized by both k and t, with running time , where n is the number of vertices in the graph. This slightly improves the previous FPT algorithm by Fellows, Hermelin, Rosamond, and Vialette. Finally, we use the W[1]-hardness of k-Independent Set in t-track interval graphs to obtain the first parameterized intractability result for a recent bioinformatics problem called Maximal Strip Recovery (MSR). We show that MSR-d is W[1]-hard for any constant d≥4 when the parameter is either the total length of the strips, or the total number of adjacencies in the strips, or the number of strips in the solution.     

Disnel: An application package for solving discrete and nonlinear optimization problems

The paper describes the features of the DISNEL package for interactive solution of a wide range of discrete and nonlinear optimization problems of ES computers.Translated from Kibernetika, No. 3, pp. 36–45, May–June, 1991.