Solving optimization problems with linear-fractional objective functions and additional constraints on arrangements

The paper proposes an exact method to solve an optimization problem on arrangements with a linear-fractional objective function and additional linear constraints. The efficiency of the solution algorithm is analyzed by means of numerical experiments. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 79–85, September–October 2006.     

Stability criterion for a lexicographic Boolean optimization problem

A vector Boolean sequential minimization problem for absolute values of linear functions is considered. Necessary and sufficient condition for stability of this type that is a discrete analogue of the upper Hausdorff semicontinuity of a point-to-set mapping is established. This mapping associates a set of lexicographic optima with each set of problem parameters. The study was sponsored by the Fundamental and Applied Research Interuniversity Program of the Republic of Belarus (Grant 492/28). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 127–132, July–August 2007.     

A Nonreducible System of Constraints of a Combinatorial Polyhedron in a Linear-Fractional Optimization Problem on Arrangements

A system of linear constraints is investigated. The system describes the domain of feasible solutions of a linear optimization problem to which a linear-fractional optimization problem on arrangements is reduced. A system of nonreducible constraints of a polyhedrom is established for the linear-fractional optimization problem on arrangements.__________Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 107–116, March–April 2005.     

Metaheuristic downhill simplex method in combinatorial optimization

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 study was supported by INTAS (Project 06-1000017-8909). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 70–79, November–December 2007.     

Analysis of an algorithm for solution of conditional optimization problems with linear-fractional objective functions over permutations

A method is considered to solve a conditional optimization problem with a linear-fractional objective function over permutations. The performance of sub algorithms to solve this problem is evaluated. The practical efficiency of the algorithm is analyzed by conducting numerical experiments. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 133–146, July–August 2007.     

Evolutionary algorithm with a directional local search for multiobjective optimization in combinatorial problems

Evolutionary algorithms (EAs) are often employed to multiobjective optimization, because they process an entire population of solutions which can be used as an approximation of the Pareto front of the tackled problem. It is a common practice to couple local search with evolutionary algorithms, especially in the context of combinatorial optimization. In this paper a new local search method is proposed that utilizes the knowledge concerning promising search directions. The proposed method can be used as a general framework and combined with many methods of iterating over a neighbourhood of an initial solution as well as various decomposition approaches. In the experiments the proposed local search method was used with an EA and tested on 2-, 3- and 4-objective versions of two well-known combinatorial optimization problems: the travelling salesman problem (TSP) and the quadratic assignment problem (QAP). For comparison two well-known local search methods, one based on Pareto dominance and the other based on decomposition, were used with the same EA. The results show that the EA coupled with the directional local search yields better results than the same EA coupled with any of the two reference methods on both the TSP and QAP problems.     

Regularization of a lexicographic vector problem of integer programming

A stability criterion for a vector integer linear problem of lexicographic optimization is obtained. A regularization method is proposed that allows us to reduce a possible unstable output problem to a sequence of perturbed stable equivalent problems. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 125–130, November–December, 1999.     

Solution of a Euclidean Combinatorial Optimization Problem by the Dynamic-Programming Method

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.     

Measuring instance difficulty for combinatorial optimization problems

Discovering the conditions under which an optimization algorithm or search heuristic will succeed or fail is critical for understanding the strengths and weaknesses of different algorithms, and for automated algorithm selection. Large scale experimental studies - studying the performance of a variety of optimization algorithms across a large collection of diverse problem instances - provide the resources to derive these conditions. Data mining techniques can be used to learn the relationships between the critical features of the instances and the performance of algorithms. This paper discusses how we can adequately characterize the features of a problem instance that have impact on difficulty in terms of algorithmic performance, and how such features can be defined and measured for various optimization problems. We provide a comprehensive survey of the research field with a focus on six combinatorial optimization problems: assignment, traveling salesman, and knapsack problems, bin-packing, graph coloring, and timetabling. For these problems - which are important abstractions of many real-world problems - we review hardness-revealing features as developed over decades of research, and we discuss the suitability of more problem-independent landscape metrics. We discuss how the features developed for one problem may be transferred to study related problems exhibiting similar structures.     

Algorithmic soluyion of two parametric optimization problems on a set of complete combinations

Algorithmic solutions of parametric problems of two types with a parameter in the objective function and with a parameter in the system of constraints are considered in a Euclidean combinatorial set of combinations with repetitions. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 160–165, November–December, 1999.     

Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems

Parallel memetic algorithms (PMAs) are a class of modern parallel meta-heuristics that combine evolutionary algorithms, local search, parallel and distributed computing technologies for global optimization. Recent studies on PMAs for large-scale complex combinatorial optimization problems have shown that they converge to high quality solutions significantly faster than canonical GAs and MAs. However, the use of local learning for every individual throughout the PMA search can be a very computationally intensive and inefficient process. This paper presents a study on two diversity-adaptive strategies, i.e., (1) diversity-based static adaptive strategy (PMA-SLS) and (2) diversity-based dynamic adaptive strategy (PMA-DLS) for controlling the local search frequency in the PMA search. Empirical study on a class of NP-hard combinatorial optimization problem, particularly large-scale quadratic assignment problems (QAPs) shows that the diversity-adaptive PMA converges to competitive solutions at significantly lower computational cost when compared to the canonical MA and PMA. Furthermore, it is found that the diversity-based dynamic adaptation strategy displays better robustness in terms of solution quality across the class of QAP problems considered. Static adaptation strategy on the other hand requires extra effort in selecting suitable parameters to suit the problems in hand.     

Multi-center variable-scale search algorithm for combinatorial optimization problems with the multimodal property

Combinatorial optimization problems (COPs) are discrete problems arising from aerospace, bioinformatics, manufacturing, and other fields. One of the classic COPs is the scheduling problem. Moreover, these problems are usually multimodal optimization problems with a quantity of global and local optima. As a result, many search algorithms can easily become trapped into local optima. In this article, we propose a multi-center variable-scale search algorithm for solving both single-objective and multi-objective COPs. The algorithm consists of two distinct points. First, the multi-center strategy chooses several individuals with better performance as the only parents of the next generation, which means that there are a number of separate searching areas around the searching center. Second, the next generation of the population is produced by a variable-scale strategy with an exponential equation based on the searching center. The equation is designed to control the neighborhood scale, and adaptively realize the large-scale and small-scale searches at different search stages to balance the maintenance of diversity and convergence speed. In addition, an approach of adjusting centers is proposed concerning the number and distribution of centers for solving multi-objective COPs. Finally, the proposed algorithm is applied to three COPs, including the well-known flexible job shop scheduling problem, the unrelated parallel machine scheduling problem, and the test task scheduling problem. Both the single-objective optimization algorithm and the multi-objective optimization algorithm demonstrate competitive performance compared with existing methods.     

Stability and regularization of the lexicographic vector problem of quadratic discrete programming

The paper studies the bounds of variation of input parameters for a vector quadratic discrete optimization problem, which do not expand the set of lexicographic optima. A stability criterion is described and a regularization method is presented, which makes it possible to pass from a possibly unstable problem to a series of perturbed stable problems with a previous set of lexicographic optima. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 54–62, March–April, 2000.     

求解复杂耦合问题的多系统优化方法

由于复杂耦合问题具有多系统、多目标、多约束、多尺度和不确定等特点,急需一种求解此类问题的高效智能优化方法.为此,借鉴多种群进化算法的智能平行特征,利用种群间进化信息的继承和交互作用,提出一种多系统优化方法.首先以子种群来代表子系统的优化环境,通过子系统内的进化操作求解各自的优化子问题;然后通过子系统间的迁移操作,即利用变量共享、目标函数和约束条件的相似程度来实现子系统间的信息迁移与反馈,加速整个问题的全局优化;最后将该方法应用到基准函数和具有多系统优化特征的三级供应链网络,仿真实验表明所提出的方法可行且有效.     

基于局部并行搜索的分布式约束优化算法框架

针对当前局部搜索算法在求解大规模、高密度的分布式约束优化问题（DCOP）时,求解困难且难以跳出局部最优取得进一步优化等问题,提出一种基于局部并行搜索的分布式约束优化算法框架（LPOS）,算法中agent通过自身的取值并行地搜索局部所有邻居取值来进一步扩大对解空间的搜索,从而避免算法过早陷入局部最优。为了保证算法的收敛性与稳定性,设计了一种自适应平衡因子K来平衡算法对解的开发和继承能力,并在理论层面证明了并行搜索优化算法可以扩大对解空间的搜索,自适应平衡因子K可以实现平衡目的。综合实验结果表明,基于该算法框架的算法在求解低密度和高密度DCOP时性能都优于目前最新的算法。特别是在求解高密度DCOP中有显著的提升。     

Solving constrained combinatorial optimization problems via importance sampling in the grand canonical ensemble

Combinatorial optimization problems are usually NP-hard. These problems are generally tackled by heuristic or branch-and-bound methods. The aim of this paper is to tackle constrained combinatorial optimization problems by importance Monte Carlo sampling. For this, we show that every constrained combinatorial optimization problem can be represented by a thermodynamical system in a suitable grand canonical ensemble given by the quantities of temperature, volume, and chemical potential. In order to find optimum solutions of the optimization problem, the grand canonical Monte Carlo method can be applied to the corresponding thermodynamical system. This method will amount to importance sampling, i.e. good feasible solutions of the optimization problem will be preferably sampled, provided that the intensive quantities of temperature and chemical potential are appropriately chosen. Our approach extends the standard importance sampling approach in the canonical ensemble to tackle unconstrained combinatorial optimization problems. The knapsack problem is considered as a prototype example.     

求解约束优化问题的改进果蝇优化算法及其工程应用

针对基本果蝇优化算法收敛速度慢、求解精度低、易于陷入局部极值以及算法候选解不能取负值等不足,提出一种用于解决约束优化问题的改进果蝇优化算法.该算法利用果蝇个体历史最佳记忆信息和种群全局历史最佳记忆信息构建多策略混合协同进化的搜索机制,以达到有效平衡算法的全局探索与局部开发的目的,同时也能够较好地避免算法的早熟收敛问题;...     

The spherical search algorithm for bound-constrained global optimization problems

In this paper, a new optimization algorithm called Spherical Search (SS) is proposed to solve the bound-constrained non-linear global optimization problems. The main operations of SS are the calculation of spherical boundary and generation of new trial solution on the surface of the spherical boundary. These operations are mathematically modeled with some more basic level operators: Initialization of solution, greedy selection and parameter adaptation, and are employed on the 30 black-box bound constrained global optimization problems. This study also analyzes the applicability of the proposed algorithm on a set of real-life optimization problems. Meanwhile, to show the robustness and proficiency of SS, the obtained results of the proposed algorithm are compared with the results of other well-known optimization algorithms and their advanced variants: Particle Swarm Optimization (PSO), Differential Evolution (DE), and Covariance Matrix Adapted Evolution Strategy (CMA-ES). The comparative analysis reveals that the performance of SS is quite competitive with respect to the other peer algorithms.     

Analysis of mathematical models and methods of solving combinatorial optimization problems on game-type permutations

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. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 103–114, November–December 2007.