A hybrid Lagrangean heuristic with GRASP and path-relinking for set k-covering

The set multicovering or set k-covering problem is an extension of the classical set covering problem, in which each object is required to be covered at least k times. The problem finds applications in the design of communication networks and in computational biology. We describe a GRASP with path-relinking heuristic for the set k-covering problem, as well as the template of a family of Lagrangean heuristics. The hybrid GRASP Lagrangean heuristic employs the GRASP with path-relinking heuristic using modified costs to obtain approximate solutions for the original problem. Computational experiments carried out on 135 test instances show experimentally that the Lagrangean heuristics performed consistently better than GRASP as well as GRASP with path-relinking. By properly tuning the parameters of the GRASP Lagrangean heuristic, it is possible to obtain a good trade-off between solution quality and running times. Furthermore, the GRASP Lagrangean heuristic makes better use of the dual information provided by subgradient optimization and is able to discover better solutions and to escape from locally optimal solutions even after the stabilization of the lower bounds, when other Lagrangean strategies fail to find new improving solutions.     

Interconnection of Local Computer Networks: Modeling and Optimization Problems

We study problems of optimization of the topology of interconnected local computer networks using random access to a single channel. An approach to modeling of the system by a queueing network is proposed: the analytical solution of the model allows us to obtain global performance measures, which may be used as evaluation criteria in network topology optimization problems. A heuristic is proposed for the latter aspect for one class of problems. We also derive from the model the time needed, for a new user which joins the network, to transmit its number of messages.     

Decision models for designing and planning private communication networks

We consider the recently developed reconfigurable digital data networks consisting of T1/T3 circuits and Digital Crossconnect Systems (DCSs). A DCS is a device to patch base channels electronically from one T1/T3 circuit to another with a negligible queuing delay at the connecting node. We present new decision models for the design and circuit leasing policies of such digital backbone networks. Our model takes advantage of the special capabilities of the DCS technology and is likely to result in remarkable economic gains for the private network users. The formulation and analyses presented here simultaneously address the following problems: physical link and capacity selection, logical network configuration and channel assignment, and traffic routing on the logical network. The problem formulation results in a large-scale non-linear mixed integer program, and we propose an efficient solution methodology employing Lagrangean relaxation and subgradient optimization. Several numerical results illustrate the utility of our approach for these complex problems. We show that the economies of scale built into the tariff structure of these digital networks can be successfully exploited, and that the inherent flexibility of DCSs leads to logical networks that are dramatically different from their underlying physical topologies.     

基于核心化技术的点覆盖改进算法

点覆盖是一个著名的NP难解问题，在通信网络和生物信息学等领域具有重要应用。针对点覆盖的研究主要集中在启发式或近似算法，其主要不足是无法实现全局最优。核心化是处理难解问题的一种新方法。提出融合启发式操作和核心化操作的算法框架，利用核心化技术进行点覆盖启发式算法优化。核心化操作挖掘出全局最优的顶点集，而启发式操作改变网络拓扑，使下一轮核心化操作能够继续，两者交叉执行实现解精度优化。实验结果表明，提出的算法在不同网络中均能实现不同程度的优化，在几乎所有稀疏网络实例中获得了最优解。     

Unidirectional loop network layout by a LP heuristic and design of telecommunications networks

In this paper, we present a new linear programming-based heuristic procedure for optimal design of the unidirectional loop network layout problem. The heuristic procedure employs a linear programming formulation and solves the problem using the flow matrix of the unidirectional loop problem. To find an optimal solution, one can either generate all possible solutions or use a branch-and-bound procedure. But, both above methods require very high computational time and computer memory for larger problems. The heuristic developed in this paper is quite fast and obtains near optimal solutions. The heuristic procedure was tested on 16 different problems selected from the literature. The results showed that in most cases optimal—and in a few cases near optimal—solutions were obtained with very little computational time. Several examples are discussed. We also demonstrate that the above problem formulation and approach can be used to solve a special class of telecommunication networks where a set of computers (or processors) are attached by unidirectional point-to-point links around a loop.     

Integrating heuristic knowledge and optimization models forcommunication network design

A method is developed for integrating heuristic design knowledge with optimization models to create a tool for the topological design of computer communication networks. Design choices are based on suggestions from optimization models, as well as heuristic knowledge, which interact through a blackboard. A truth maintenance system (TMS) records justification for current design choices, as well as promising alternatives. A dependency-directed backtracking mechanism works with the TMS to choose other alternatives as warranted. This hybrid tool can consider a wider range of design requirements than is possible using one type of knowledge alone, is flexible in handling variations in these requirements, and has a modular structure which facilitates incremental refinement. Computational results on separate networks show it is effective in identifying good low-cost solutions     

Assigning cells to switches in cellular mobile networks using taboosearch

The design of wireless telecommunications networks is a complex process, which requires solving simultaneously many difficult combinatorial optimization problems. We propose a taboo-search approach dedicated to one of the aforementioned design optimization problems, namely the cell assignment problem. Our approach defines a series of moves applicable to an initial solution in order to improve the cost and establish the feasibility of the solution. For this purpose, we identify a gain structure with update procedures to efficiently choose the best solution in the current neighborhood. The results are generally good in comparison with those obtained through other heuristic methods.     

An evolutionary approach for configuring economical packet switched computer networks

The topological design of computer networks essentially consists in finding a network topology which minimizes the communication costs, taking into account some constraints such as performance and quality of service. This optimization problem is well known as difficult to solve, such that only heuristic methods are usually recommended and used. These methods are incremental in the sense that they take a starting topology as input solution and perturb it in order to produce a better solution. In this paper, we propose an evolutionary approach, based on the genetic algorithm paradigm, for solving this problem. Simulation results confirm the appropriateness and efficiency of this approach which yields solutions of very good quality for moderate size networks.     

The multi-period incremental service facility location problem

In this paper we introduce the multi-period incremental service facility location problem where the goal is to set a number of new facilities over a finite time horizon so as to cover dynamically the demand of a given set of customers. We prove that the coefficient matrix of the allocation subproblem that results when fixing the set of facilities to open is totally unimodular. This allows to solve efficiently the Lagrangean problem that relaxes constraints requiring customers to be assigned to open facilities. We propose a solution approach that provides both lower and upper bounds by combining subgradient optimization to solve a Lagrangean dual with an ad hoc heuristic that uses information from the Lagrangean subproblem to generate feasible solutions. Numerical results obtained in the computational experiments show that the obtained solutions are very good. In general, we get very small percent gaps between upper and lower bounds with little computation effort.     

计算机网络服务质量优化方法研究综述

优化方法为设计更好的计算机网络服务质量保证机制提供了有力的理论支持.相较于传统启发式的网络设计方法,优化方法可以从理论上找到问题的最优解,从而从根本上克服了启发式方法不能证明方案优劣程度的缺陷.因此,基于优化方法的机制设计与性能评价成为了当前网络服务质量领域中的一个前沿研究领域.大量的研究着眼于从优化理论的角度重新建立...     

Stochastic resource allocation using a predictor-based heuristic for optimization via simulation

Some combinatorial stochastic resource allocation problems lack algebraically defined objective functions and hence require optimization via simulation as a mechanism for obtaining good solutions. For this class of problems, we propose a new predictor-based heuristic that uses a distance criterion to perform the solution search. To demonstrate our solution approach, we apply this heuristic to the problem of selecting the proper design configuration of an unmanned aerial system (UAS) fleet so as to maximize mission effectiveness. We compare our approach to black box optimization via simulation approaches (two tabu search-based procedures and a greedy heuristic) and glean both methodological and practical insights.     

Inferring new design rules by machine learning: a case study oftopological optimization

This paper presents a machine learning approach to the topological optimization of computer networks. Traditionally formulated as an integer program, this problem is well known to be a very difficult one, only solvable by means of heuristic methods. This paper addresses the specific problem of inferring new design rules that can reduce the cost of the network, or reduce the message delay below some acceptable threshold. More specifically, it extends a recent approach using a rule-based system in order to prevent the risk of combinatorial explosion and to reduce the search space of feasible network topologies. This extension essentially implements an efficient inductive learning algorithm leading to the refinement of existing rules and to the discovery of new rules from examples, defined as network topologies satisfying a given reliability constraint. The contribution of this paper is the integration of learning capabilities into topological optimization of computer networks. Computational results confirm the efficiency of the discovered rules     

A steady-state genetic algorithm for multi-product supply chain network design

Supply chain network (SCN) design is to provide an optimal platform for efficient and effective supply chain management (SCM). The problem is often an important and strategic operations management problem in SCM. The design task involves the choice of facilities (plants and distribution centers (DCs)) to be opened and the distribution network design to satisfy the customer demand with minimum cost. This paper presents a solution procedure based on steady-state genetic algorithms (ssGA) with a new encoding structure for the design of a single-source, multi-product, multi-stage SCN. The effectiveness of the ssGA has been investigated by comparing its results with those obtained by CPLEX, Lagrangean heuristic, hyrid GA and simulated annealing on a set of SCN design problems with different sizes.     

Core-Edge design of storage area networks—A Single-edge formulation with problem-specific cuts

Optimization and heuristic methods for the design of medium to large storage area networks (SANs) are in the early stages of development, but are required if large clustered storage systems are to become a viable alternative to expensive monolithic storage. We present here a new mixed-integer formulation for optimal design of a storage area network. Our formulation models the Single-edge Core-Edge topology. Using a testbed of medium to large problems, we compare the solution times for our new formulation to the current benchmark in the literature—our formulation solves in significantly less time with an off-the-shelf optimization software package. We also generate problem-specific cuts to further reduce the solution time for our formulation. An algorithm, which includes an integer programming subproblem, is described for generating some of these cuts. For all test problems, the cuts yield a further reduction in the solution time.     

Practical approach to the optimization of large-scale switching networks

There are a number of techniques that enable networks to be optimized. Neither search techniques nor heuristic methods are entirely satisfactory in solving practical problems. The authors describe an approach to network optimization that utilizes an algorithm that reduces the number of nodes and consequently the time taken to find a solution. The approach is based on two basic stages: a preparation stage and an optimization stage.     

求解仿真优化问题的知识型启发式搜索方法

仿真优化研究基于仿真的目标优化问题,已经成为系统仿真和运筹学等领域共同关注的热点和前沿课题.针对离散事件动态系统仿真优化中的难点问题,提出了一种全新的知识型启发式搜索方法.采用知识模型和启发式搜索模型相结合的集成建模思路,以启发式搜索模型为基础,同时突出知识模型的作用,将启发式搜索模型和知识模型进行优化组合、优势互补,以提高启发式搜索技术的效率.基于期望值模型的数值仿真,验证了方法的可行性和有效性.仿真结果表明,无论是求解质量还是求解速度,都优于其它几种现有方法.研究结果表明,将知识模型合理地嵌入到现有启发式搜索方法中,可以有效地解决复杂的仿真优化问题.     

Design of efficient hybrid neural networks for flexible flow shop scheduling

Abstract: Although neural networks have been successfully used in performing pattern recognition, their application for solving optimization problems has been limited. In this paper we design a neural network to solve a well‐known combinatorial problem, namely the flexible flow shop problem. A key feature of our neural network design is the integration of problem structure and heuristic information in the network structure and solution. We compare the performance of our neural network with well‐known current heuristics with respect to solution quality. The results indicate that our approach outperforms the heuristics.     

Binary integer programming formulation and heuristics for differentiated coverage in heterogeneous sensor networks

Coverage is a fundamental task in sensor networks. We consider the minimum cost point coverage problem and formulate a binary integer linear programming model for effective sensor placement on a grid-structured sensor field when there are multiple types of sensors with varying sensing quality and price. The formulation is general and can be adapted to handle situations where sensing is perfect, imperfect or uncertain, and the coverage requirements are differentiated. Unfortunately, the new model suffers from the intractability of the binary integer programming formulations. We therefore suggest approximation algorithms and heuristics. Computational results indicate that the heuristic based on Lagrangean relaxation outperforms the others in terms of solution quality.     

Penalty guided genetic search for reliability design optimization

Reliability optimization has been studied in the literature for decades, usually using a mathematical programming approach. Because of these solution methodologies, restrictions on the type of allowable design have been made, however heuristic optimization approaches are free of such binding restrictions. One difficulty in applying heuristic approaches to reliability design is the highly constrained nature of the problems, both in terms of number of constraints and the difficulty of satisfying constraints. This paper presents a penalty guided genetic algorithm which efficiently and effectively searches over promising feasible and infeasible regions to identify a final, feasible optimal, or near optimal, solution. The penalty function is adaptive and responds to the search history. Results obtained on 33 test problems from the literature dominate previous solution techniques.     

Fractional-Neuro-Optimizer: A Neural-Network-Based Optimization Method

Up to now, there have been many attempts in the use of artificial neural networks (ANNs) for solving optimization problems and some types of ANNs, such as Hopfield network and Boltzmann machine, have been applied for combinatorial optimization problems. However, there are some restrictions in the use of ANNs as optimizers. For example: (1) ANNs cannot optimize continuous variable problems; (2) discrete problems should be mapped into the neural networks’ architecture; and (3) most of the existing neural networks are applicable only for a class of smooth optimization problems and global convexity conditions on the objective functions and constraints are required. In this paper, we introduce a new procedure for stochastic optimization by a recurrent ANN. The concept of fractional calculus is adopted to propose a novel weight updating rule. The introduced method is called fractional-neuro-optimizer (FNO). This method starts with an initial solution and adjusts the network’s weights by a new heuristic and unsupervised rule to reach a good solution. The efficiency of FNO is compared to the genetic algorithm and particle swarm optimization techniques. Finally, the proposed FNO is used for determining the parameters of a proportional–integral–derivative controller for an automatic voltage regulator power system and is applied for designing the water distribution networks.