A variable neighborhood search for the network design problem with relays

Given a set of commodities to be routed over a network, the network design problem with relays involves selecting a route for each commodity and determining the location of relays where the commodities must be reprocessed at certain distance intervals. We propose a hybrid approach based on variable neighborhood search. The variable neighborhood algorithm searches for the route for each commodity and the optimal relay locations for a given set of routes are determined by an implicit enumeration algorithm. We show that dynamic programming can be used to determine the optimal relay locations for a single commodity. Dynamic programming is embedded into the implicit enumeration algorithm to solve the relay location problem optimally for multiple commodities. The special structure of the problem is leveraged for computational efficiency. In the variable neighborhood search algorithm, the routes of the current solution are perturbed and reconstructed to generate neighbor solutions using random and greedy construction heuristics. Computational experiments on three sets of problems (80 instances) show that the variable neighborhood search algorithm with optimal relay allocations outperforms all existing algorithms in the literature.     

An interactive dynamic approach based on hybrid swarm optimization for solving multiobjective programming problem with fuzzy parameters

Real engineering design problems are generally characterized by the presence of many often conflicting and incommensurable objectives. Naturally, these objectives involve many parameters whose possible values may be assigned by the experts. The aim of this paper is to introduce a hybrid approach combining three optimization techniques, dynamic programming (DP), genetic algorithms and particle swarm optimization (PSO). Our approach integrates the merits of both DP and artificial optimization techniques and it has two characteristic features. Firstly, the proposed algorithm converts fuzzy multiobjective optimization problem to a sequence of a crisp nonlinear programming problems. Secondly, the proposed algorithm uses H-SOA for solving nonlinear programming problem. In which, any complex problem under certain structure can be solved and there is no need for the existence of some properties rather than traditional methods that need some features of the problem such as differentiability and continuity. Finally, with different degree of α we get different α-Pareto optimal solution of the problem. A numerical example is given to illustrate the results developed in this paper.     

Efficient MIP formulation for optimal 1-for-N diversity coding

In the paper we consider a communication network that uses diversity coding in order to achieve reliability. Having a set of demands and a network topology we face a problem of optimal routing of the demands and backup trees, and associations between the demands and the backup trees. We present a compact mixed integer programming (MIP) formulation for the optimization problem, which proves to be more efficient than other approaches that can be found in the literature.     

校车站点及线路的优化设计

以高校新校区教师校车站点及线路安排为对象,首先针对乘车站点建立了双目标非线性规划模型,其中目标函数包括乘客到达站点的距离偏差最小与所有乘客到达站点的总的距离最小两个方面;站点确定后针对车辆数最少、车辆行驶的总距离最短、各辆车的运行距离均衡及各辆车的负荷均衡这4个目标建立针对线路优化的多目标非线性规划模型,并给出了解决这类问题的启发式优化算法.与目前国内外研究相比较,该模型与算法更实际,更具体的给出了问题的解答.     

Multi-server machine repair problems under a (V, R) synchronous single vacation policy

This paper considers a machine repair problem with M operating machines and S standbys, in which R repairmen are responsible for supervising these machines and operate a (V, R) vacation policy. With such policy, if the number of the failed machines is reduced to R − V (R > V) (there exists V idle repairmen) at a service completion, these V idle servers will together take a synchronous vacation (or leave for other secondary job). Upon returning from the vacation, they do not take a vacation again and remain idle until the first arriving failed machine arrives. The steady-state probabilities are solved in terms of matrix forms and the system performance measures are obtained. Algorithmic procedures are provided to deal with the optimization problem of discrete/continuous decision variables while maintaining a minimum specified level of system availability.     

Best proximity point theorems: exposition of a significant non-linear programming problem

The primary goal of this work is to address the non-linear programming problem of globally minimizing the real valued function x → d(x, Tx) where T is presumed to be a non-self mapping that is a generalized proximal contraction in the setting of a metric space. Indeed, an iterative algorithm is presented to determine a solution of the preceding non-linear programming problem that focuses on global optimization. As a sequel, one can compute optimal approximate solutions to some fixed point equations and optimal solutions to some unconstrained non-linear programming problems.     

Quantifying exponential growth: Three conceptual shifts in coordinating multiplicative and additive growth

This article presents the results of a teaching experiment with middle school students who explored exponential growth by reasoning with the quantities height (y) and time (x) as they explored the growth of a plant. Three major conceptual shifts occurred during the course of the teaching experiment: (1) from repeated multiplication to initial coordination of multiplicative growth in y with additive growth in x; (2) from coordinating growth in y with growth in x to coordinated constant ratios (determining the ratio of f(x₂) to f(x₁) for corresponding intervals of time for (x₂ − x₁) ≥ 1), and (3) from coordinated constant ratios to within-units coordination for corresponding intervals of time for (x₂ − x₁) < 1. Each of the three shifts is explored along with a discussion of the ways in which students’ mathematical activity supported movement from one stage of understanding to the next. These findings suggest that emphasizing a coordination of multiplicative and additive growth for exponentiation may support students’ abilities to flexibly move between the covariation and correspondence views of function.     

Global optimality conditions and optimization methods for quadratic assignment problems

In this paper some global optimality conditions for general quadratic {0, 1} programming problems with linear equality constraints are discussed and then some global optimality conditions for quadratic assignment problems (QAP) are presented. A local optimization method for (QAP) is derived according to the necessary global optimality conditions. A global optimization method for (QAP) is presented by combining the sufficient global optimality conditions, the local optimization method and some auxiliary functions. Some numerical examples are given to illustrate the efficiency of the given optimization methods.     

Incremental versus non-incremental dynamic programming

Many dynamic programming algorithms for discrete optimization problems are pure in that they only use min/max and addition operations in their recursions. Some of them, in particular those for various shortest path problems, are even incremental in that one of the inputs to the addition operations is a variable. We present an explicit optimization problem such that it can be solved by a pure DP algorithm using a polynomial number of operations, but any incremental DP algorithm for this problem requires a super-polynomial number of operations.     

Bus driver duty optimization using an integer programming and evolutionary hybrid algorithm

This paper describes the details of a successful application where an integer programming and evolutionary hybrid algorithm was used to solve a bus driver duty optimization problem. The task is NP-hard, therefore theoretically optimal solutions can only be calculated for very small problem instances. Our aim is to obtain solutions of good quality within reasonable time limits. We first applied an integer programming approach to a set partitioning problem. The model was solved with a column generation algorithm in a branch and bound scheme. In order to solve larger real-life problems, we have combined the integer programming method with a greedy 1+1 steady state evolutionary algorithm. The resulting hybrid algorithm was capable of providing near-optimal solutions within reasonable timescales to larger instances of the bus driver scheduling problem. We present the results and running times of our algorithm in detail, as well as possible directions of future improvements.     

A heuristic approach for combined equipment-planning and routing in multi-layer SDH/WDM networks

The paper deals with a multi-layer network design problem for a high-speed telecommunication network based on Synchronous Digital Hierarchy (SDH) and Wavelength Division Multiplex (WDM) technology. The network has to carry a certain set of demands with the objective of minimizing the investment in the equipment. The different layers are the fiber-layer, 2.5 Gbit/s-, 10 Gbit/s- and WDM-systems. Several variations of the problem including path-protected demands and specific types of cross-connect equipment are considered. The problem is described as a mixed integer linear programming model and some results for small networks are presented. Two greedy heuristics, a random start heuristic and a GRASP-like approach are implemented to solve large real world problems.     

On the positive definite solutions of nonlinear matrix equation X + A⋆ X−δA = Q

In this paper we consider the positive definite solutions of nonlinear matrix equation X + A^⋆X^−δA = Q, where δ ∈ (0, 1], which appears for the first time in [S.M. El-Sayed, A.C.M. Ran, On an iteration methods for solving a class of nonlinear matrix equations, SIAM J. Matrix Anal. Appl. 23 (2001) 632–645]. The necessary and sufficient conditions for the existence of a solution are derived. An iterative algorithm for obtaining the positive definite solutions of the equation is discussed. The error estimations are found.     

A modified Physarum-inspired model for the user equilibrium traffic assignment problem

The user equilibrium traffic assignment principle is very important in the traffic assignment problem. Mathematical programming models are designed to solve the user equilibrium problem in traditional algorithms. Recently, the Physarum shows the ability to address the user equilibrium and system optimization traffic assignment problems. However, the Physarum model are not efficient in real traffic networks with two-way traffic characteristics and multiple origin–destination pairs. In this article, a modified Physarum-inspired model for the user equilibrium problem is proposed. By decomposing traffic flux based on origin nodes, the traffic flux from different origin–destination pairs can be distinguished in the proposed model. The Physarum can obtain the equilibrium traffic flux when no shorter path can be discovered between each origin–destination pair. Finally, numerical examples demonstrate the rationality and convergence properties of the proposed model.     

Global optimization algorithm for sum of generalized polynomial ratios problem

In this paper, a global optimization algorithm is proposed for solving sum of generalized polynomial ratios problem (P) which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solve the problem (P). For such problems, we present a branch and bound algorithm. In this method, by utilizing exponent transformation and new three-level linear relaxation method, a sequence of linear relaxation programming of the initial nonconvex programming problem (P) are derived which are embedded in a branch and bound algorithm. The proposed method need not introduce new variables and constraints and it is convergent to the global minimum of prime problem by means of the subsequent solutions of a series of linear programming problems. Several numerical examples in the literatures are tested to demonstrate that the proposed algorithm can systematically solve these examples to find the approximate ?-global optimum.     

A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems

Most real-life decision-making activities require more than one objective to be considered. Therefore, several studies have been presented in the literature that use multiple objectives in decision models. In a mathematical programming context, the majority of these studies deal with two objective functions known as bicriteria optimization, while few of them consider more than two objective functions. In this study, a new algorithm is proposed to generate all nondominated solutions for multiobjective discrete optimization problems with any number of objective functions. In this algorithm, the search is managed over (p − 1)-dimensional rectangles where p represents the number of objectives in the problem and for each rectangle two-stage optimization problems are solved. The algorithm is motivated by the well-known ε-constraint scalarization and its contribution lies in the way rectangles are defined and tracked. The algorithm is compared with former studies on multiobjective knapsack and multiobjective assignment problem instances. The method is highly competitive in terms of solution time and the number of optimization models solved.     

The Lie-group shooting method for solving the Bratu equation

For the Bratu problem, we transform it into a non-linear second order boundary value problem, and then solve it by the Lie-group shooting method (LGSM). LGSM allows us to search a missing initial slope and moreover, the initial slope can be expressed as a function of r ∈ [0, 1], where the best r is determined by matching the right-end boundary condition. The calculated results as compared with those calculated by other methods, illuminate the efficiency and precision of Lie-group shooting method (LGSM) for this problem.     

Consensus of partitions : a constructive approach

Given a profile (family) ?? of partitions of a set of objects or items X, we try to establish a consensus partition containing a maximum number of joined or separated pairs in X that are also joined or separated in the profile. To do so, we define a score function, S _?? associated to any partition on X. Consensus partitions for ?? are those maximizing this function. Therefore, these consensus partitions have the median property for the profile and the symmetric difference distance. This optimization problem can be solved, in certain cases, by integer linear programming. We define a polynomial heuristic which can be applied to partitions on a large set of items. In cases where an optimal solution can be computed, we show that the partitions built by this algorithm are very close to the optimum which is reached in practically all the cases, except for some sets of bipartitions.     

A spatio-temporal Gaussian-Conical wavelet with high aperture selectivity for motion and speed analysis

The construction of a spatio-temporal wavelet and its tuning to speed was first realized in the 90s on the Morlet wavelet by Duval-Destin (1991, 1993) [14], [15]. This enabled to demonstrate the capacities of the speed-tuned Morlet for psychovisual analysis. This construction was also used very efficiently in a powerful aerial target tracking algorithm by Mujica et al. (1999, 2000) [20], [21]. In the last decade, this tool was proposed as an elegant and efficient alternative framework to the Optical Flow (OF), the Block Matching (BM) or the phase difference, for the study of motion estimation in image sequences. Nevertheless, the aperture selectivity of the 2D + T Morlet wavelet presents some difficulties. Here we propose to replace the 2D Morlet wavelet by a Gaussian-Conical (GC) wavelet for the spatial part of the spatio-temporal wavelet, since the GC wavelet has a better aperture selectivity and allows a very simple adjustment of the aperture. Therefore we build a new, highly directional, speed-tuned wavelet called Gaussian-Conical–Morlet (GCM) wavelet. Like the speed-tuned 2D + T Morlet, the new wavelet presents very good characteristics in motion estimation and tracking, namely long temporal dependence, robustness to noise and to occlusions, and supersedes the OF (Optical Flow) and BM (Block Matching) techniques. However, for aperture selectivity, directional speed-capture and spectral recognition and tracking, GCM easily outperforms Morlet. This paper describes the GCM construction, utilization and aperture performances.     

Relay placement for fault tolerance in wireless networks in higher dimensions

In this paper we consider the problem of adding the smallest number of additional (relay) nodes to a network of static nodes with limited communication range so that the induced communication graph is 2-connected (we consider both edge and vertex connectivity). The problem is NP-hard. We develop algorithms that find close to optimal solutions for both edge and vertex connectivity. We prove the algorithms have an approximation ratio of 2M for nodes distributed in a d-dimensional Euclidean space, where M is the maximum node degree of a Minimum Spanning Tree in d dimensions using Euclidean metrics. In addition, our methods extend with the same approximation guarantees to a generalization when the locations of relays are required to avoid certain polygonal regions (obstacles).     

Integer programming formulation of combinatorial optimization problems

This paper considers in a somewhat general setting when a combinatorial optimization problem can be formulated as an (all-integer) integer programming (IP) problem. The main result is that any combinatorial optimization problem can be formulated as an IP problem if its feasible region S is finite but there are many rather sample problems that have no IP formulation if their S is infinite. The approach used for finite S usually gives a formulation with a relatively small number of additional variables for example, an integer polynomial of n 0?1 variables requires at most n + 1 additional variables by our approach, whereas 2ⁿ - (n + 1) additional variables at maximum are required by other existing methods. Finally, the decision problem of deciding whether an arbitrarily given combinatorial optimization problem has an IP formulation is considered and it is shown by an argument closely related to Hilbert's tenth problem (drophantine equations) that no such algorithm exists.