A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems

This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.     

Nonconvex piecewise linear knapsack problems

This paper considers the minimization version of a class of nonconvex knapsack problems with piecewise linear cost structure. The items to be included in the knapsack have a divisible quantity and a cost function. An item can be included partially in the given quantity range and the cost is a nonconvex piecewise linear function of quantity. Given a demand, the optimization problem is to choose an optimal quantity for each item such that the demand is satisfied and the total cost is minimized. This problem and its close variants are encountered in manufacturing planning, supply chain design, volume discount procurement auctions, and many other contemporary applications. Two separate mixed integer linear programming formulations of this problem are proposed and are compared with existing formulations. Motivated by different scenarios in which the problem is useful, the following algorithms are developed: (1) a fast polynomial time, near-optimal heuristic using convex envelopes; (2) exact pseudo-polynomial time dynamic programming algorithms; (3) a 2-approximation algorithm; and (4) a fully polynomial time approximation scheme. A comprehensive test suite is developed to generate representative problem instances with different characteristics. Extensive computational experiments show that the proposed formulations and algorithms are faster than the existing techniques.     

A Branch-and-price Algorithm for the Multi-Vehicle Covering Tour Problem

In this paper, we propose a Branch-and-price (BP) algorithm and a Column Generation Heuristic (CGH) for the Multi-Vehicle Covering Tour Problem (m-CTP). Specific dominance and extension pruning rules are introduced to accelerate the resolution of the pricing problems. To the best of our knowledge, this is the first work dedicated to the exact resolution of m-CTP. The algorithm managed to solve about 30% of the instances in our test bed, within a 4 hour CPU time limit. Our preliminary computational experiments suggest that both the lower bounds provided by the formulation behind BP and the CGH upper bounds are of good quality.     

A unified framework for approximation of general telecommunication networks

In this paper, we develop a unified framework for approximation of the performance of general telecommunication networks based on a decomposition strategy. The method is an extension of the work presented in [15]. The algorithms assume finite buffer space at each switch, state-dependent arrival rates of data packets, and general service time distribution at the switches. Two methods of buffer space allocation at the switches, and two congestion control mechanisms are modeled. The proposed algorithms have been extensively tested against simulation values. The results show that the proposed framework yields robust, reliable and accurate estimates of network performance measures, such as throughput, number of packets in the system, and switch and link utilization. The computation time required is minimal. The unified framework presents a useful set of tools for telecommunication network designers in evaluating numerous network designs.     

A branch-and-bound approach for maximum quasi-cliques

Detecting quasi-cliques in graphs is a useful tool for detecting dense clusters in graph-based data mining. Particularly in large-scale data sets that are error-prone, cliques are overly restrictive and impractical. Quasi-clique detection has been accomplished using heuristic approaches in various applications of graph-based data mining in protein interaction networks, gene co-expression networks, and telecommunication networks. Quasi-cliques are not hereditary, in the sense that every subset of a quasi-clique need not be a quasi-clique. This lack of heredity introduces interesting challenges in the development of exact algorithms to detect maximum cardinality quasi-cliques. The only exact approaches for this problem are limited to two mixed integer programming formulations that were recently proposed in the literature. The main contribution of this article is a new combinatorial branch-and-bound algorithm for the maximum quasi-clique problem.     

Nonanticipative duality,relaxations, and formulations for chance-constrained stochastic programs

We propose two new Lagrangian dual problems for chance-constrained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer programming (MIP) formulation. For a given dual solution, the associated Lagrangian relaxation bounds can be calculated by solving a set of single scenario subproblems and then solving a single knapsack problem. We also derive two new primal MIP formulations and demonstrate that for chance-constrained linear programs, the continuous relaxations of these formulations yield bounds equal to the proposed dual bounds. We propose a new heuristic method and two new exact algorithms based on these duals and formulations. The first exact algorithm applies to chance-constrained binary programs, and uses either of the proposed dual bounds in concert with cuts that eliminate solutions found by the subproblems. The second exact method is a branch-and-cut algorithm for solving either of the primal formulations. Our computational results indicate that the proposed dual bounds and heuristic solutions can be obtained efficiently, and the gaps between the best dual bounds and the heuristic solutions are small.     

A Note on Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problems

One algorithm proposed in Branch-and-price algorithms for the one-dimensional cutting stock problems (COAP, vol. 9, pp. 211–228, 1998) may not find an optimal solution to the cutting stock problem, as it is stated.     

Subspace correction multi‐level methods for elliptic eigenvalue problems

In this work, we apply the ideas of domain decomposition and multi‐grid methods to PDE‐based eigenvalue problems represented in two equivalent variational formulations. To find the lowest eigenpair, we use a “subspace correction” framework for deriving the multiplicative algorithm for minimizing the Rayleigh quotient of the current iteration. By considering an equivalent minimization formulation proposed by Mathew and Reddy, we can use the theory of multiplicative Schwarz algorithms for non‐linear optimization developed by Tai and Espedal to analyse the convergence properties of the proposed algorithm. We discuss the application of the multiplicative algorithm to the problem of simultaneous computation of several eigenfunctions also formulated in a variational form. Numerical results are presented. Copyright © 2001 John Wiley & Sons, Ltd.     

Tabu search and GRASP for the maximum diversity problem

In this paper, we develop new heuristic procedures for the maximum diversity problem (MDP). This NP-hard problem has a significant number of practical applications such as environmental balance, telecommunication services or genetic engineering. The proposed algorithm is based on the tabu search methodology and incorporates memory structures for both construction and improvement. Although proposed in seminal tabu search papers, memory-based constructions have often been implemented in naïve ways that disregard important elements of the fundamental tabu search proposals. We will compare our tabu search construction with a memory-less design and with previous algorithms recently developed for this problem. The constructive method can be coupled with a local search procedure or a short-term tabu search for improved outcomes. Extensive computational experiments with medium and large instances show that the proposed procedure outperforms the best heuristics reported in the literature within short computational times.     

An efficient grouping genetic algorithm for U-shaped assembly line balancing problems with maximizing production rate

U-type assembly line is one of the important tools that may increase companies’ production efficiency. In this study, two different modeling approaches proposed for the assembly line balancing problems have been used in modeling type-II U-line balancing problems, and the performances of these models have been compared with each other. It has been shown that using mathematical formulations to solve medium and large size problem instances is impractical since the problem is NP-hard. Therefore, a grouping genetic and simulated annealing algorithms have been developed, and a particle swarm optimization algorithm is adapted to compare with the proposed methods. A special crossover operator that always obtains feasible offspring has been suggested for the proposed grouping genetic algorithm. Furthermore, a local search procedure based on problem-specific knowledge was applied to increase the intensification of the algorithm. A set of well-known benchmark instances was solved to evaluate the effectiveness of the proposed and existing methods. Results showed that while the mathematical formulations can only be used to solve small size instances, metaheuristics can obtain high quality solutions for all size problem instances within acceptable CPU times. Moreover, grouping genetic algorithm has been found to be superior to the other methods according to the number of optimal solutions, or deviations from the lower bound values.     

Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing

This paper describes new models and exact solution algorithms for the fixed destination multidepot salesmen problem defined on a graph with n nodes where the number of nodes each salesman is to visit is restricted to be in a predefined range. Such problems arise when the time to visit a node takes considerably longer as compared to the time of travel between nodes, in which case the number of nodes visited in a salesman’s tour is the determinant of their ‘load’. The new models are novel multicommodity flow formulations with O(n²) binary variables, which is contrary to the existing formulations for the same (and similar) problems that typically include O(n³) binary variables. The paper also describes Benders decomposition algorithms based on the new formulations for solving the problem exactly. Results of the computational experiments on instances derived from TSPLIB show that some of the proposed algorithms perform remarkably well in cases where formulations solved by a state-of-the-art optimization code fail to yield optimal solutions within reasonable computation time.     

Frequency assignment in a SDMA satellite communication system with beam decentring feature

In satellite communication, Spatial Division Multiple Access (SDMA) has become one of the most promising techniques that can accommodate continuing increase in the number of users and traffic demands. The technology is based on radio resource sharing that separates communication channels in space. It relies on adaptive and dynamic beam-forming technology and well-designed algorithms for resource allocation among which frequency assignment is considered. This paper studies static Frequency Assignment Problem (FAP) in a satellite communication system involving a satellite and a number of users located in a service area. The objective is to maximize the number of users that the system can serve while maintaining the signal to interference plus noise ratio of each user under a predefined threshold. Traditionally, interference is treated as fixed (binary interferences or fixed minimal required separation between frequencies) . In this paper, the interference is cumulative and variable. To solve the problem, we work on both discrete and continuous optimizations. Integer linear programming formulations and greedy algorithms are proposed for solving the discrete frequency assignment problem. The solution is further improved by beam decentring algorithm which involves continuous adjustment of satellite beams and deals with non-linear change of interference.     

Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows

In this paper, we develop a simultaneous column-and-row generation algorithm that could be applied to a general class of large-scale linear programming problems. These problems typically arise in the context of linear programming formulations with exponentially many variables. The defining property for these formulations is a set of linking constraints, which are either too many to be included in the formulation directly, or the full set of linking constraints can only be identified, if all variables are generated explicitly. Due to this dependence between columns and rows, we refer to this class of linear programs as problems with column-dependent-rows. To solve these problems, we need to be able to generate both columns and rows on-the-fly within an efficient solution approach. We emphasize that the generated rows are structural constraints and distinguish our work from the branch-and-cut-and-price framework. We first characterize the underlying assumptions for the proposed column-and-row generation algorithm. These assumptions are general enough and cover all problems with column-dependent-rows studied in the literature up until now to the best of our knowledge. We then introduce in detail a set of pricing subproblems, which are used within the proposed column-and-row generation algorithm. This is followed by a formal discussion on the optimality of the algorithm. To illustrate our approach, the paper is concluded by applying the proposed framework to the multi-stage cutting stock and the quadratic set covering problems.     

A Branch-and-price algorithm for a Vehicle Routing Problem with Cross-Docking

n this paper, we propose a reformulation and a Branch-and-price (BP) algorithm for the Vehicle Routing Problem with Cross-Docking (VRPCD). Our computational results indicate that the reformulation provides bounds much stronger than network flow bounds from previous studies. As a consequence, when BP and a Linear Programming based Branch-and-bound (LPBB) method (that relies on the network flow formulation) are run for the same restricted time limit, BP clearly dominates LPBB in terms of the quality of lower and upper bounds found during the search.     

Wavelet-Galerkin method for solving parabolic equations in finite domains

A novel wavelet-Galerkin method tailored to solve parabolic equations in finite domains is presented. The emphasis of the paper is on the development of the discretization formulations that are specific to finite domain parabolic equations with arbitrary boundary conditions based on weak form functionals. The proposed method also deals with the development of algorithms for computing the associated connection coefficients at arbitrary points. Here the Lagrange multiplier method is used to enforce the essential boundary conditions. The numerical results on a two-dimensional transient heat conducting problem are used to validate the proposed wavelet-Galerkin algorithm as an effective numerical method to solve finite domain parabolic equations.     

A new perspective on the normalization of invariant measures for loss networks and other product form systems

Loss networks have proved to be a vital tool in the study of telecommunication networks, computer performance, and resource allocation problems. For a large subset of these models, the invariant measure is of a product form. The existence of efficient procedures to normalize a product-form invariant measure is essential for analysis of the underlying system.Choudhury et al. [1—4] have recently presented a number of algorithms based upon Fourier analysis for the normalization of product-form invariant measures for specific systems. Bean and Stewart [5] discussed related work for the normalization of product-form invariant measures for closed queueing networks. In this paper, we present a simple unifying framework within which to study these algorithms. This framework is significant as it suggests a number of extensions to these algorithms and simplifies their derivation.     

Scale factor local search in differential evolution

This paper proposes the scale factor local search differential evolution (SFLSDE). The SFLSDE is a differential evolution (DE) based memetic algorithm which employs, within a self-adaptive scheme, two local search algorithms. These local search algorithms aim at detecting a value of the scale factor corresponding to an offspring with a high performance, while the generation is executed. The local search algorithms thus assist in the global search and generate offspring with high performance which are subsequently supposed to promote the generation of enhanced solutions within the evolutionary framework. Despite its simplicity, the proposed algorithm seems to have very good performance on various test problems. Numerical results are shown in order to justify the use of a double local search instead of a single search. In addition, the SFLSDE has been compared with a standard DE and three other modern DE based metaheuristic for a large and varied set of test problems. Numerical results are given for relatively low and high dimensional cases. A statistical analysis of the optimization results has been included in order to compare the results in terms of final solution detected and convergence speed. The efficiency of the proposed algorithm seems to be very high especially for large scale problems and complex fitness landscapes.     

Spectral methods for graph clustering - A survey

Graph clustering is an area in cluster analysis that looks for groups of related vertices in a graph. Due to its large applicability, several graph clustering algorithms have been proposed in the last years. A particular class of graph clustering algorithms is known as spectral clustering algorithms. These algorithms are mostly based on the eigen-decomposition of Laplacian matrices of either weighted or unweighted graphs. This survey presents different graph clustering formulations, most of which based on graph cut and partitioning problems, and describes the main spectral clustering algorithms found in literature that solve these problems.     

A branch-and-price approach for harvest scheduling subject to maximum area restrictions

Recently, research on exact methods has been undertaken to solve forest management problems subject to constraints on the maximum clearcut area by using the area restriction model approach. Three main basic integer programming models for these problems have been discussed in the literature: the so-called cluster, path and bucket formulations. Solving these models via branch-and-bound, where all variables and constraints are used a priori, is adequately suited for real problems of a small to medium size, but is not appropriate for larger problems. In this paper, we describe a branch-and-price approach for the cluster model, and we show that this formulation dominates the bucket model, by completing the results of the dominance relationships between the bounds of the three models. Branch-and-price was tested on real and hypothetical forests ranging from 45 to 2945 stands and temporal horizons ranging from three to twelve periods were employed. Results show that the solutions obtained by the proposed approach stood within 1% of the optimal solution and were achieved in a short computation time. It was found that branch-and-bound was unable to produce solutions for most forests from 850 stands with either eleven or an average number of stands per clearcut greater or equal than eight.     

A self-organising model for the travelling salesman problem

This work describes a new algorithm, based on a self-organising neural network approach, to solve the Travelling Salesman Problem (TSP). Firstly, various features of the available adaptive neural network algorithms for TSP are reviewed and a new algorithm is proposed. In order to investigate the performance of the algorithms, a comprehensive empirical study has been provided. The simulations, which are conducted on a series of standard data, evaluate the overall performance of this approach by comparing the results with the best known or the optimal solutions of the problems. The proposed algorithm shows significant advances in both the quality of the solution and computational effort for most of the experimental data. The deviation from the optimal solution of this algorithm was, in the worst case, around 2%. This fact indicates that the self-organising neural network may be regarded as a promising heuristic approach for optimisation problems.