Implementation of scatter search for multi-objective optimization: a comparative study

Interest in the design of efficient meta-heuristics for the application to combinatorial optimization problems is growing rapidly. The optimal design of water distribution networks is an important optimization problem which consists of finding the best way of conveying water from the sources to the users, thus satisfying their requirements. The efficient design of looped networks is a much more complex problem than the design of branched ones, but their greater reliability can compensate for the increase in cost when closing some loops. Mathematically, this is a non-linear optimization problem, constrained to a combinatorial space, since the diameters are discrete and it has a very large number of local solutions. Many works have dealt with the minimization of the cost of the network but few have considered their cost and reliability simultaneously. The aim of this paper is to evaluate the performance of an implementation of Scatter Search in a multi-objective formulation of this problem. Results obtained in three benchmark networks show that the method here proposed performs accurately well in comparison with other multi-objective approaches also implemented.     

Lexicographic optimisation in generalised network flow problems

In this paper the lexicographic optimisation of the multiobjective generalised network flow problem is considered. Optimality conditions are proved on the basis of the equivalence of this problem and a weighted generalised network flow problem. These conditions are used to develop a network-based algorithm which properly modifies primal-dual algorithms for minimum cost generalised network flow problems. Computational results indicate that this algorithm is faster than general-purpose algorithms for linear lexicographic optimisation. Besides, this model is used for approaching a water resource system design problem.     

Network design problem with relays: A genetic algorithm with a path-based crossover and a set covering formulation

The network design problem with relays arises in telecommunications and distribution systems where the payload must be reprocessed at intermediate stations called relays on the route from its origin to its destination. In fiber-optic networks, for example, optical signals may be regenerated several times to overcome signal degradation because of attenuation and other factors. Given a network and a set of commodities, the network design problem with relays involves selecting network edges, determining a route for each commodity, and locating relays to minimize the network design cost. This paper presents a new formulation to the problem based on set covering constraints. The new formulation is used to design a genetic algorithm with a specialized crossover/mutation operator which generates a feasible path for each commodity, and the locations of relays on these paths are determined by solving the corresponding set covering problem. Computational experiments show that the proposed approach can outperform other approaches, particularly on large size problems.     

Heuristics for Distribution Network Design in Telecommunication

A distribution network problem arises in a lower level of an hierarchical modeling approach for telecommunication network planning. This paper describes a model and proposes a lagrangian heuristic for designing a distribution network. Our model is a complex extension of a capacitated single commodity network design problem. We are given a network containing a set of sources with maximum available supply, a set of sinks with required demands, and a set of transshipment points. We need to install adequate capacities on the arcs to route the required flow to each sink, that may be an intermediate or a terminal node of an arborescence. Capacity can only be installed in discrete levels, i.e., cables are available only in certain standard capacities. Economies of scale induce the use of a unique higher capacity cable instead of an equivalent set of lower capacity cables to cover the flow requirements of any link. A path from a source to a terminal node requires a lower flow in the measure that we are closer to the terminal node, since many nodes in the path may be intermediate sinks. On the other hand, the reduction of cable capacity levels across any path is inhibited by splicing costs. The objective is to minimize the total cost of the network, given by the sum of the arc capacity (cables) costs plus the splicing costs along the nodes. In addition to the limited supply and the node demand requirements, the model incorporates constraints on the number of cables installed on each edge and the maximum number of splices at each node. The model is a NP-hard combinatorial optimization problem because it is an extension of the Steiner problem in graphs. Moreover, the discrete levels of cable capacity and the need to consider splicing costs increase the complexity of the problem. We include some computational results of the lagrangian heuristics that works well in the practice of computer aided distribution network design.     

Network synthesis under survivability constraints

Telecommunication networks are subject to link and equipment failures. Since failures cannot be entirely avoided, networks have to be designed so as to survive failure situations. In this paper, we are interested in designing low cost survivable networks. Given point-to-point traffic demands and a cost/capacity function for each link, we aim at finding the minimum cost capacities satisfying the given demands and survivability requirements. A survivability model that reroutes interrupted traffic using all the available capacities on the network is presented and studied. In the proposed model, capacity and flow assignments for each network operating state are jointly optimized. We prove the -hardness of the optimisation problem defined by dual constraints. Then, we propose a polynomial relaxation along with a fast heuristic to compute a feasible solution of the problem from its relaxed optimal solution. Our solution approaches are tested on a set of problem instances.Received: September 2002, Revised: July 2003, AMS classification: 90C05     

The mixed capacitated general routing problem under uncertainty

We study the General Routing Problem defined on a mixed graph and with stochastic demands. The problem under investigation is aimed at finding the minimum cost set of routes to satisfy a set of clients whose demand is not deterministically known. Since each vehicle has a limited capacity, the demand uncertainty occurring at some clients affects the satisfaction of the capacity constraints, that, hence, become stochastic. The contribution of this paper is twofold: firstly we present a chance-constrained integer programming formulation of the problem for which a deterministic equivalent is derived. The introduction of uncertainty into the problem poses severe computational challenges addressed by the design of a branch-and-cut algorithm, for the exact solution of limited size instances, and of a heuristic solution approach exploring promising parts of the search space. The effectiveness of the solution approaches is shown on a probabilistically constrained version of the benchmark instances proposed in the literature for the mixed capacitated general routing problem.     

Real-time optimisation of access control lists for efficient Internet packet filtering

This paper considers an optimisation problem encountered in the implementation of traffic policies on network routers, namely the ordering of rules in an access control list to minimise or reduce processing time and hence packet latency. The problem is formulated as an objective function with constraints and shown to be NP-complete by translation to a known problem. Exact and heuristic solution methods are introduced, discussed and compared and computational results given. The emphasis throughout is on practical implementation of the optimisation process, that is within the tight constraints of a production network router seeking to reduce latency, on-line, in real-time but without the overhead of significant extra computation.     

Traditional heuristic versus Hopfield neural network approaches to a car sequencing problem

This paper considers the problem of optimally sequencing different car models along an assembly line according to some contiguity constraints, while ensuring that the demands for each of the models are satisfied. This car sequencing problem (CSP) is a practical NP-hard combinatorial optimisation problem. The CSP is formulated as a nonlinear integer programming problem and it is shown that exact solutions to the problem are difficult to obtain due to the indefinite quadratic form of the CSP objective function. Two traditional heuristics (steepest descent and simulated annealing) are employed to solve the CSP approximately. Several Hopfield neural network (HNN) approaches are also presented. The process of mapping an optimisation problem onto a HNN is demonstrated explicitly, and modifications to the existing neural approaches are presented which guarantee feasibility of solutions. Further modifications are proposed to improve the solution quality by permitting escape from local minima in an attempt to locate the global optimum. Results from all solutions techniques are compared on a set of instances of the CSP, and conclusions drawn.     

Network cost minimization using threshold-based discounting

A network design problem in which every pair of nodes can communicate directly is discussed. However, there is an incentive to combine flow from different sources, namely, if the total flow through a link exceeds the prescribed threshold, then the cost of this flow is discounted by a factor α. Alternative mixed integer linear formulations for this problem are presented. Computational results comparing the models on a set of benchmark problems are also presented. The results show the effectiveness of the formulations: for discounts of 5–10%, the gaps between linear and integer solutions are within few percent. Such a model offers economic incentives in building and utilizing communication networks.     

Solving a Network Design Problem

Industrial optimization applications must be “robust” i.e., they must provide good solutions to problem instances of different size and numerical characteristics, and continue to work well when side constraints are added. This paper presents a case study that addresses this requirement and its consequences on the applicability of different optimization techniques. An extensive benchmark suite, built on real network design data, is used to test multiple algorithms for robustness against variations in problem size, numerical characteristics, and side constraints. The experimental results illustrate the performance discrepancies that have occurred and how some have been corrected. In the end, the results suggest that we shall remain very humble when assessing the adequacy of a given algorithm for a given problem, and that a new generation of public optimization benchmark suites is needed for the academic community to attack the issue of algorithm robustness as it is encountered in industrial settings.     

Multistate components assignment problem with optimal network reliability subject to assignment budget

The typical assignment problem for finding the optimal assignment of a set of components to a set of locations in a system has been widely studied in practical applications. However, this problem mainly focuses on maximizing the total profit or minimizing the total cost without considering component’s failure. In practice, each component should be multistate due to failure, partially failure, or maintenance. That is, each component has several capacities with a probability distribution and may fail. When a set of multistate components is assigned to a system, the system can be treated as a stochastic-flow network. The network reliability is the probability that d units of homogenous commodity can be transmitted through the network successfully. The multistate components assignment problem to maximize the network reliability is never discussed. Therefore, this paper focuses on solving this problem under an assignment budget constraint, in which each component has an assignment cost. The network reliability under a components assignment can be evaluated in terms of minimal paths and state-space decomposition. Subsequently an optimization method based on genetic algorithm is proposed. The experimental results show that the proposed algorithm can be executed in a reasonable time.     

Optimal Design of Reliable Computer Networks: A Comparison of Metaheuristics

In many computer communications network design problems, such as those faced by hospitals, universities, research centers, and water distribution systems, the topology is fixed because of geographical and physical constraints or the existence of an existing system. When the topology is known, a reasonable approach to design is to select components among discrete alternatives for links and nodes to maximize reliability subject to cost. This problem is NP-hard with the added complication of a very computationally intensive objective function. This paper compares the performance of three classic metaheuristic procedures for solving large and realistic versions of the problem: hillclimbing, simulated annealing and genetic algorithms. Three alterations that use local search to seed the search or improve solutions during each iteration are also compared. It is shown that employing local search during evolution of the genetic algorithm, a memetic algorithm, yields the best network designs and does so at a reasonable computational cost. Hillclimbing performs well as a quick search for good designs, but cannot identify the most superior designs even when computational effort is equal to the metaheuristics.     

Design of electricity supply networks

The problem of designing a secure electricity supply network at minimal cost is formulated as a mathematical program. It is also shown how computationally convenient new constraints may be derived and these are added to the original set. The problem is dualized and solved approximately. It is indicated how this approach can be built into a Branch-and-Bound scheme for solving the original design problem, and an illustrative example is given.     

A parameter-free self-adapting boundary genetic search for pipe network optimization

Commercial application of genetic algorithms (GAs) to engineering design problems, including optimal design of pipe networks, could be facilitated by the development of algorithms that require the least number of parameter tuning. This paper presents an attempt to eliminate the need for defining a priori the proper penalty parameter in GA search for pipe networks optimal designs. The method is based on the assumption that the optimal solution of a pipe network design problem lies somewhere on, or near, the boundary of the feasible region. The proposed method uses the ratio of the best feasible and infeasible designs at each generation to guide the direction of the search towards the boundary of the feasible domain by automatically adjusting the value of the penalty parameter. The value of the ratio greater than unity is interpreted as the search being performed in the feasible region and vice versa. The new adapted value of the penalty parameter at each generation is therefore calculated as the product of its current value and the aforementioned ratio. The genetic search so constructed is shown to converge to the boundary of the feasible region irrespective of the starting value of the constraint violation penalty parameter. The proposed method is described here in the context of pipe network optimisation problems but is equally applicable to any other constrained optimisation problem. The effectiveness of the method is illustrated with a benchmark pipe network optimization example from the literature.     

New formulations of the Hop-Constrained Minimum Spanning Tree problem via Miller-Tucker-Zemlin constraints

Given an undirected network with positive edge costs and a natural number p, the Hop-Constrained Minimum Spanning Tree problem (HMST) is the problem of finding a spanning tree with minimum total cost such that each path starting from a specified root node has no more than p hops (edges). In this paper, we develop new formulations for HMST. The formulations are based on Miller-Tucker-Zemlin (MTZ) subtour elimination constraints, MTZ-based liftings in the literature offered for HMST, and a new set of topology-enforcing constraints. We also compare the proposed models with the MTZ-based models in the literature with respect to linear programming relaxation bounds and solution times. The results indicate that the new models give considerably better bounds and solution times than their counterparts in the literature and that the new set of constraints is competitive with liftings to MTZ constraints, some of which are based on well-known, strong liftings of Desrochers and Laporte (1991).     

An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles

The vehicle routing problem with multiple use of vehicles is a variant of the classical vehicle routing problem. It arises when each vehicle performs several routes during the workday due to strict time limits on route duration (e.g., when perishable goods are transported). The routes are defined over customers with a revenue, a demand and a time window. Given a fixed-size fleet of vehicles, it might not be possible to serve all customers. Thus, the customers must be chosen based on their associated revenue minus the traveling cost to reach them. We introduce a branch-and-price approach to address this problem where lower bounds are computed by solving the linear programming relaxation of a set packing formulation, using column generation. The pricing subproblems are elementary shortest path problems with resource constraints. Computational results are reported on euclidean problems derived from well-known benchmark instances for the vehicle routing problem with time windows.     

Optimal design of a hoist structure frame

In an attempt to find the most cost effective design of a multipurpose hoisting device that can be easily mounted on and removed from a regular farm vehicle, cost optimisation including both material and manufacturing expenditure, is performed on the main frame supporting the device. The optimisation is constrained by local and global buckling and fatigue conditions. Implementation of Snyman’s gradient-based LFOPC optimisation algorithm to the continuous optimisation problem, results in the economic determination of an unambiguous continuous solution, which is then utilised as the starting point for a neighbourhood search within the discrete set of profiles available, to attain the discrete optimum.

This optimum is further investigated for a different steel grade and for the manufacturing and material cost pertaining to different countries. The effect of variations in the formulation of the objective function for optimisation is also investigated. The results indicate that considerable cost benefits can be obtained by optimisation, that costing in different countries do not necessarily result in the same most cost effective design, and that accurate formulation of the objective function, i.e. realistic mathematical modelling, is of utmost importance in obtaining the intended design optimum.     

Proprietor and customer costs in the incomplete hub location-routing network topology

The hub location problem finds the location of hubs and allocates the other nodes to them. It is widely supposed the network created with the hub nodes is complete in the extensive literature. Relaxation of this basic supposition forms the present work. The model minimizes the cost of the proprietor, including the fixed costs of hubs, hub links and spoke links. Costs of hub and spoke links are contemplated as fixed cost or maintenance cost. Moreover, the model considers routing costs of customers who want to travel from origins to destinations. In this study, we offer a model to the multiple allocations of the hub location problems, under the incomplete hub location-routing network design. This model is easily transformed to other hub location problems using one or more constraints. No network format is dictated on the hub network. We suggest a set of valid inequalities for the formulation. Some lower bounds are developed using a Lagrangian relaxation approach and the valid inequalities. Computational analyses evaluate the performances of the lower bounding implementations and valid inequalities. Furthermore, we explore the effects of several factors on the design and solution time of the problem formulation.     

Lamination Design Optimization for Continuous Fiber Reinforced Composites of Variable Thicknesses北大核心CSCD

由于具备高的比强度、比刚度,利用连续纤维增强复合材料代替传统金属材料以实现结构轻量化正受到设计者们的广泛关注。然而,结构的复杂性给复合材料的铺层设计与优化带来了很大的挑战。针对航空用复合材料铺层设计约束多的问题,通过逐步构建设计变量准确表达结构的铺层信息。基于经典遗传算法框架,结合各设计变量特点,定义了铺层优化算法中的遗传算子,通过引入“修复”策略保证了每一代解都能满足设计约束,分布在可行域区间内。最后利用精英保留策略提高了算法的局部寻优能力,可以降低复杂复合材料结构铺层设计的计算成本。通过解决经典benchmark问题并与已有优化结果的比较,验证了前述铺层优化算法的全局、局部寻优能力,为工程实际中的复合材料铺层设计优化提供了理论支撑。     

A partitioning algorithm for the multicommodity network flow problem

A partitioning algorithm for solving the general minimum cost multicommodity flow problem for directed graphs is presented in the framework of a network flow method and the dual simplex method. A working basis which is considerably smaller than the number of capacitated arcs in the given network is employed and a set of simple secondary constraints is periodically examined. Some computational aspects and preliminary experimental results are discussed.