Optimization Methods and Applications

Using network approach, we propose a new method of identifying key food exporters based on the long-range (LRIC) and short-range interaction indices (SRIC). These indices allow to detect several groups of economies with direct as well as indirect influence on the routes of different levels in the food network.

Fundamental relations and symmetry rules of the genetic information organization in DNA were studied. DNA symmetry was used to construct an optimal symmetric code with respect to amino acid polarity, with noise immunity much higher than that of a standard genetic code. It is well known that various diseases are associated with pointwise mutations of nucleotides in genes. Bayesian procedures allow for use of the standard and symmetric codes for genetic diseases diagnosis. Markov model of higher orders with hidden states was used to build simple algorithms for gene fragment prediction.

The capacitated clustering problem requires finding a partition of a given set of elements with associated positive weights into a specified number of groups (or clusters) so that the sum of diversities of the individual clusters is maximized and the sum of weights of the elements in each cluster is within some capacity limits. We examine here various neighborhood structures for conducting local search for this type of problem and then describe a powerful variable neighborhood descent (VND) that employs three of these neighborhoods in a deterministic fashion and has appeared recently in the literature as a stand-alone heuristic. We then examine some recently developed heuristics for solving the problem that are based on variable neighborhood search (VNS), including a new one that applies a recently proposed variant of VNS known as nested VNS. These heuristics all use the prescribed VND in their local improvement step. A summary is given of extensive computational tests that demonstrate the effectiveness of these VNS-based heuristics over the state of the art.

In this paper, a decision-making problem where alternatives are estimated with interval parameters and the feasible set is defined using interval constraints is considered. Based on the assumption that the objective function and constraints are linear, a linear optimization problem with interval coefficients in the objective function and constraints was specified. For solving this problem, the approach of its reduction to optimization problem with a scalar objective function and scalar constraints was proposed. This approach consists of two steps. At the first step, we reduce the problem with interval coefficients to a lexicographical optimization problem with lexicographical constraints. At the second step, we reduce this lexicographic optimization problem to a problem with a single scalar objective function and scalar constraints. This makes it possible to use well-known classical methods of real-valued optimization theory for solving this problem.

Practical problems of optimization have always demanded effective algorithms for search of their solutions. Nowadays, due to the considerable development of computer aids and various technologies, in particular technologies of parallel calculations, there is a need for development of new algorithms and methods that would allow to receive optimal or close to them solutions within an acceptable time. It is especially urgent in connection with the significant increase in dimension of modern applied tasks. In this work such methods and algorithms are being constructed for the purpose of increase in efficiency of the algorithm of lexicographic search of the solution of Boolean optimization problems.

Network robustness issues are crucial in a variety of application areas, such as energy, defense, communications, and so on. Unpredictable failures of network components (nodes and/or edges) can be caused by a variety of factors, including man-made and natural disruptions, which may significantly affect or inhibit network’s functionality. In many situations, one of the key robustness requirements is that every pair of nodes is connected, with the number of intermediate links between them being as small as possible. Additionally, if nodes in a cluster are connected by several different paths, such a cluster will be more robust with respect to potential network component disruptions. In this work, we study the problem of identifying error- and attack-resilient clusters in graphs, particularly power grids. It is assumed that the cluster represents a R-robust 2-club, which is defined as a subgraph with at least R node/edge disjoint paths connecting each pair of nodes, where each path consists of at most two edges. Uncertain information manifests itself in the form of stochastic number of errors/attacks that could happen in different nodes. If one can reinforce the network components against future threats, the goal is to determine optimal reinforcements that would yield a cluster with minimum risk of disruptions. A combinatorial branch-and-bound algorithm is developed and compared with an equivalent mathematical programming approach on simulated and real-world networks.

Wildfires are a naturally occurring phenomenon in many places of the world. While they perform a number of important ecological functions, the proximity of human activities to forest landscapes requires a measure of control/preparedness to address safety concerns and mitigate damage. An important technique utilized by forest managers is that of wildfire fuel management, in which a portion of the available combustible material in the forest is disposed of through a variety of fuel treatment activities. A number of operations research approaches have been applied to locate and schedule these fuel treatment activities, and herein we review and discuss the various models and approaches in the literature.

In this chapter, a comprehensive review of niching genetic algorithms designed to solve multimodal optimization problems is given. First, an introduction to multimodal optimization problem and to niching is provided. After that, a number of niching algorithms are discussed. These algorithms are presented according to their spatial-temporal classification, although other classifications are also mentioned.

Methods analyzed in detail among others include sequential niching, fitness sharing, clearing, multinational genetic algorithm, clustering, species conserving genetic algorithm, crowding (standard, deterministic, probabilistic, multi-niche), restricted tournament selection, and others. Most methods are followed by their numerous modifications. The efficiency of hybridization of different algorithms is discussed, and examples of such hybridization are provided. Experimental approach to analyze performance of niching algorithms is described. To estimate the ability of the algorithms in finding and maintaining multiple optima, most popular test criteria and benchmark problems are given.

Given an edge-weighted graph, the maximum edge weight clique (MEWC) problem is to find a clique that maximizes the sum of edge weights within the corresponding complete subgraph. This problem generalizes the classical maximum clique problem and finds many real-world applications in molecular biology, broadband network design, pattern recognition and robotics, information retrieval, marketing, and bioinformatics among other areas. The main goal of this chapter is to provide an up-to-date review of mathematical optimization formulations and solution approaches for the MEWC problem. Information on standard benchmark instances and state-of-the-art computational results is also included.

Original approach to determination of the concepts “combinatorial object” and “fuzzy combinatorial object” is offered, which allows to strictly formalize both the known and new classes of problems of combinatorial optimization. The offered approach to such formalization which is concept-based a local finiteness of the discrete spaces relies only on properties of the discrete spaces therefore has quite general character and allows to develop the constructive approach to creation of special objects in combinatorial spaces. The obtained results are important both in the theoretical plan and for development of methods of solving the combinatorial optimization problems.

The multidimensional assignment problem is an extension of the linear assignment problem to higher dimensions. This NP-hard problem in combinatorial optimization has applications in scheduling, multiple target tracking, and healthcare. In combinatorial optimization, algorithms utilizing very large-scale neighborhood search are proven to be particularly effective for some computationally difficult problems. In this chapter, we present two such algorithms, which are some of the first proposed for this problem in the literature. The two algorithms are distinct. One uses theory of cyclic transfers to construct and exploit the improvement graph. Another relies on polynomial schemes for finding optimal permutation. Because both methods depend on multiple restarts for effective exploration of search space, we propose and discuss some new multi-start strategies motivated by the design of experiments.

In this paper we consider the large deviation problem for the method of empirical means in stochastic optimization with continuous time observations. For discrete time models this problem was studied in Knopov and Kasitskaya (Cybern Syst Anal 4:52–61, 2004; Cybern Syst Anal 5:40–45, 2010).

A network consisting of highly reliable repairable edges and varying random external load is being considered. Distribution functions of failure-free operation and repair time of edges are supposed to be of general type. The capacity of the network is determined by the states of its edges. A required capacity is a function of the semi-Markov process state. A fast simulation method enabling to evaluate the probability of functional failure of the network when its real capacity is less than the required one is being proposed.

It is proved that under some weak conditions, the estimate has a bounded relative error as the reliability of the network edges increases. Numerical examples demonstrate high efficiency of the method proposed.

For the case of Poisson input flow in queueing system with infinitely many servers, the steady-state distribution of the number of customers can be evaluated due to the explicit formula (Poisson distribution). Five models of much more complicated input flows are considered. The combination of Poisson distribution (analytical part) with statistical simulation (statistical part) enables to evaluate the steady-state probabilities with the fast simulation method. Numerical examples demonstrate that the application of explicit analytical formula to the evaluation of small probabilities enables to reduce essentially the variance of the estimate while simulating the queueing system behavior in heavy traffic.

The objective of postoptimality analysis and reoptimization using approximation methods is applying knowledge of the solution of the initial instance I of the problem (problem with the set values of input parameters) in order to either achieve a better quality of approximation (approximation ratio) of I′ (revised instance) or create a more efficient algorithm for determining an optimal or close to optimal solution of I′. This paper offers theoretical foundations for the acquisition, exploration, and use of bounds in the postoptimality analysis, as well as further development and improvement of approximation algorithms of reoptimization for discrete optimization problems. In particular, the upper and lower bounds on approximation ratio of approximate reoptimization algorithms for the constraint satisfaction problems (CSPs) are obtained using linear and semidefinite relaxations of the initial problem. In addition, sufficient conditions for the existence of polynomial approximation or threshold reoptimization algorithms for CSPs are obtained.

The paper extends stochastic branch and bound (SB&B) method, primarily developed for solving stochastic global and integer stochastic programming problems, to stochastic multicriteria problems. The specific feature and difficulty of the stochastic optimization problems consists in that they contain random parameters and thus mathematical expectations and other probabilistic integral operators. The scalar stochastic branch and bound method has found various applications for optimization of stochastic workflow models, stochastic schedules, project management, water quality, pollution control, service allocation, reliability optimization, financial portfolio selection, and others. Multicriteria versions of such problems allow more explicit investigation of a trade-off between utility, risk, and other criteria in the problem. In the new SB&B method, upper and lower bounds become vectorial. For example, for a maximization problem, as an upper bound, the value of the vector objective function at the ideal point can be used; as a lower bound, the value of the vector objective function at any feasible point is usually taken. For stochastic optimization problems, such bounds can be calculated exactly only in special cases, for example, when the distribution of random parameters is known and discrete. In the latter case, the estimation problems are reduced to mixed-integer programming. In a general case to get upper bounds, the so-called interchange relaxation is applied, i.e., interchange of optimization and integration operators. Another bounding technique involves the use of multiple independent observations of random parameters and stochastic tangent majorants. Since the bounds are vectorial and may be inexact, the convergence results state finite step convergence to a set of approximate solutions.

In this chapter, we provide an overview of the electricity market structure and discuss its characteristics. We also survey the regulation policies on electricity prices and the existing price forecasting techniques in a market-driven electricity industry. The complex nature of electricity markets makes it difficult to design optimal policies for the policy makers. It also makes it challenging for market participants to conduct price forecasting. Additionally, the dynamic nature of the electricity markets creates strong demand for researchers to come up with a more accurate prediction.

In this chapter, the approaches to the solution of various problems of artificial intelligence methods are proposed. All methods base on the ideas of inductive mathematics. To investigate the reliability of these methods the elements of the theory of probability of fuzzy events are used.

In this paper, a Multiobjective Route-based Fuel Consumption Vehicle Routing problem (MRFCVRPs) is solved using a new variant of a Multiobjective Particle Swarm Optimization algorithm, the Parallel Multi-Start Non-dominated Sorting Particle Swarm Optimization algorithm (PMS-NSPSO). Three different versions of this algorithm are used and their results are compared with a Parallel Multi-Start NSGA II algorithm and a Parallel Multi-Start NSDE algorithm. All these algorithms use more than one initial populations of solutions. The Variable Neighborhood Search algorithm is used in all algorithm for the improvement of each solution separately. The Multiobjective Symmetric and Asymmetric Delivery Route-based Fuel Consumption Vehicle Routing Problem and the Multiobjective Symmetric and Asymmetric Pick-up Route-based Fuel Consumption Vehicle Routing Problem are the problems that are solved. The objective functions correspond to the optimization of the time needed for the vehicle to travel between two customers or between the customer and the depot and to the Route based Fuel Consumption of the vehicle considering the traveled distance, the load of the vehicle, the slope of the road, the speed and the direction of the wind, and the driver’sbehavior when the decision maker plans delivery or pick-up routes. A number of modified Vehicle Routing Problem instances are used in order to measure the quality of the proposed algorithms.

The paper considers a vector (multiobjective) optimization problem with linear partial criteria and unbounded convex feasible set. Solving this problem means finding a Pareto set. The properties of two cones, the recession cone of feasible set and the cone, which partially orders this set with respect to the objective functions, are used to formulate the sufficient conditions of existence of Pareto-optimal solutions. In the case, when the perturbations of input data are possible, the sufficient conditions for stable (unstable) preservation of solvability (unsolvability) are obtained.

We propose a method to increase the efficiency of secure radio networks with data transfer packet due to minimization of duration and number of packets with high information capacity. The formation and transmission of the compact, interference and crypto stable packages is offered using protection of compressed information by crypto code with one time keys, making additional interconnections between neighboring bits of the crypto stable data arrays, mixing data between packets, forming highly informative, packet code-signal sequences whose type and base are selected according to noise level in the channel.

Parallel computing systems are readily available to optimization experts in industry and academia, providing tools for solving optimization models of unprecedented scale. Unfortunately, there is no simple way to adapt existing optimization theory and algorithms to fully realize the distributed power of these systems, preventing their widespread usage. At the same time, optimization models that fully capture the essence of industrial scale problems, such as stochastic conditions and outcomes, multi-stage structure, and multi-objective criteria, require capacities only afforded by parallel computing. Without efficient and scalable parallel methods we are unable to utilize these computational resources. This chapter outlines these challenges and illustrates theoretical extensions to deal with such limitations.

Properties of three computational forms of r-algorithms differentiated by their complexities (number of calculations per iteration) are considered. The results on convergence of the limit variants of r-algorithms for smooth functions and r _μ (α)-algorithm for nondifferentiable functions are presented. A variant of r(α)-algorithms with a constant coefficient of space dilation α and adaptive step adjustment along the normalized anti-subgradient in the transformed space of variables is discussed. Octave-functions ralgb5 and ralgb4 of r(α)-algorithms with adaptive step adjustment are described. The results of computational experiments for substantially ravine piecewise quadratic function and ravine quadratic and piecewise linear functions are presented.

Our solution strategy is based on combination of discrete and continuous optimization methods. We employ two approaches to solve IRPP problem: a branching scheme algorithm and an efficient optimization algorithm, which involves a feasible starting point and local optimization procedures. To show the benefits of our methodology we present computational results for a number of new challenger and the best known benchmark instances.

In 1982, Wolsey (Combinatorica 2:385–393, 1982) gave a well-known theorem about greedy approximation algorithm for the submodular set cover problem. The theorem requires the submodular function involved in the problem has integer-value. In this note, we present a similar theorem without integer-value requirement by improving a result in Du et al. (Design and analysis of approximation algorithms. Springer, Berlin, 2012).

This research focuses on problems of combinatorial optimization necessary for mapping combinatorial sets into arithmetic Euclidean space. The analysis shows that there is a class of vertex-located sets that coincide with the set of vertices within their convex hull. The author has proved the theorems on the existence of convex, strongly convex, and differentiable extensions for functions defined on vertex-located sets. An equivalent problem of mathematical programming with convex objective function and functional constraints has been formulated. The author has studied the properties of convex function extremes on vertex-located sets. The research contains the examples of vertex-located combinatorial sets and algorithms for constructing convex, strongly convex, and differentiable extensions for functions defined on these sets. The conditions have been formulated that are sufficient for a minimum value of functions, as well as lower bounds of functions have been defined on the permutation set. The results obtained can be well used for developing new methods of combinatorial optimization.

In this paper we establish the artificial control method for nonlinear distributed systems. We investigate the regularity properties of each weak solution for “problem in hands.” As a result, the long-time dynamics, the convergence of approximations in strongest topologies, and the structure properties of limit sets for all weak solutions for the number of nonlinear systems like a feedback control problem, a model of combustion in porous media, a model of conduction of electrical impulses in nerve axons, a climate energy balance model, and the 3D Navier-Stokes system can be examined.

The primary motivation of this research is to find ways to reduce time and cost associated with the development and selection of new metallic alloys having highly variable mechanical properties. Particularly, the fracture toughness response as measured by Charpy V-Notch (CVN) values exhibits substantial variability and cannot be modeled via standard regression with its focus on the mean. We use the latest achievements in generalized regression techniques for building linear regression models for right and left tails of the ln(CVN) distribution. We demonstrate how these regression models can be used to search for combinations of chemical compositions and processing parameters that result in steels with optimal tensile yield strength and CVN characteristics. According to our approach, information from prior experimental data is incorporated into mathematical models, the models are used for optimization, and results of optimization are subsequently used in refining the fabrication process. The simulations can be used successively at various stages of the experimental program.