Metaheuristic hybridizations for the regenerator placement and dimensioning problem in sub-wavelength switching optical networks

Physical layer impairments severely limit the reach and capacity of optical systems, thereby hampering the deployment of transparent optical networks (i.e., no electrical signal regenerators are required). Besides, the high cost and power-consumption of regeneration devices makes it unaffordable for network operators to consider the opaque architecture (i.e., regeneration is available at every network node). In this context, translucent architectures (i.e., regeneration is only available at selected nodes) have emerged as the most promising short term solution to decrease costs and energy consumption in optical backbone networks. Concurrently, the coarse granularity and inflexibility of legacy optical technologies have re-fostered great interest in sub-wavelength switching optical networks, which introduce optical switching in the time domain so as to further improve resources utilization. In these networks, the complex regenerator placement and dimensioning problem emerges. In short, this problem aims at minimizing the number of electrical regenerators deployed in the network. To tackle it, in this paper both a greedy randomized adaptive search procedure and a biased random-key genetic algorithm are developed. Further, we enhance their performance by introducing both path-relinking and variable neighborhood descent as effective intensification procedures. The resulting hybridizations are compared among each other as well as against results from optimal and heuristic mixed integer linear programming formulations. Illustrative results over a broad range of network scenarios show that the biased random-key genetic algorithm working in conjunction with these two intensification mechanisms represents a compelling network planning algorithm for the design of future sub-wavelength optical networks.     

ABCs of the bomber problem and its relatives

In a classic Markov decision problem of Derman et al. (Oper. Res. 23(6):1120–1130, 1975) an investor has an initial capital x from which to make investments, the opportunities for which occur randomly over time. An investment of size y results in profit P(y), and the aim is maximize the sum of the profits obtained within a given time t. The problem is similar to a groundwater management problem of Burt (Manag. Sci. 11(1):80–93, 1964), the notorious bomber problem of Klinger and Brown (Stochastic Optimization and Control, pp. 173–209, 1968), and types of fighter problems addressed by Weber (Stochastic Dynamic Optimization and Applications in Scheduling and Related Fields, p. 148, 1985), Shepp et al. (Adv. Appl. Probab. 23:624–641, 1991) and Bartroff et al. (Adv. Appl. Probab. 42(3):795–815, 2010a). In all these problems, one is allocating successive portions of a limited resource, optimally allocating y(x,t), as a function of remaining resource x and remaining time t. For their investment problem, Derman et al. (Oper. Res. 23(6):1120–1130, 1975) proved that an optimal policy has three monotonicity properties: (A) y(x,t) is nonincreasing in t, (B) y(x,t) is nondecreasing in x, and (C) x?y(x,t) is nondecreasing in x. Theirs is the only problem of its type for which all three properties are known to be true. In the bomber problem the status of (B) is unresolved. For the general fighter problem the status of (A) is unresolved. We survey what is known about these exceedingly difficult problems. We show that (A) and (C) remain true in the bomber problem, but that (B) is false if we very slightly relax the assumptions of the usual model. We give other new results, counterexamples and conjectures for these problems.     

A Metaheuristic to Solve a Location-Routing Problem with Non-Linear Costs

The paper deals with a location-routing problem with non-linear cost functions. To the best of our knowledge, a mixed integer linear programming formulation for the addressed problem is proposed here for the first time. Since the problem is NP-hard exact algorithms are able to solve only particular cases, thus to solve more general versions heuristics are needed. The algorithm proposed in this paper is a combination of a p-median approach to find an initial feasible solution and a metaheuristic to improve the solution. It is a hybrid metaheuristic merging Variable Neighborhood Search (VNS) and Tabu Search (TS) principles and exploiting the synergies between the two. Computational results and conclusions close the paper.     

A Hybrid Metaheuristic for the Quadratic Assignment Problem

The quadratic assignment problem (QAP) is known to be NP-hard. We propose a hybrid metaheuristic called ANGEL to solve QAP. ANGEL combines the ant colony optimization (ACO), the genetic algorithm (GA) and a local search method (LS). There are two major phases in ANGEL, namely ACO phase and GA phase. Instead of starting from a population that consists of randomly generated chromosomes, GA has an initial population constructed by ACO in order to provide a good start. Pheromone acts as a feedback mechanism from GA phase to ACO phase. When GA phase reaches the termination criterion, control is transferred back to ACO phase. Then ACO utilizes pheromone updated by GA phase to explore solution space and produces a promising population for the next run of GA phase. The local search method is applied to improve the solutions obtained by ACO and GA. We also propose a new concept called the eugenic strategy intended to guide the genetic algorithm to evolve toward a better direction. We report the results of a comprehensive testing of ANGEL in solving QAP. Over a hundred instances of QAP benchmarks were tested and the results show that ANGEL is able to obtain the optimal solution with a high success rate of 90%. This work was supported in part by the National Science Council, R.O.C., under Contract NSC 91-2213-E-005-017.     

Hybridization of GRASP Metaheuristic with Data Mining Techniques

In this work, we propose a hybridization of GRASP metaheuristic that incorporates a data mining process. We believe that patterns obtained from a set of sub-optimal solutions, by using data mining techniques, can be used to guide the search for better solutions in metaheuristics procedures. In this hybrid GRASP proposal, after executing a significant number of GRASP iterations, the data mining process extracts patterns from an elite set of solutions which will guide the following iterations. To validate this proposal we have worked on the Set Packing Problem as a case study. Computational experiments, comparing traditional GRASP and different hybrid approaches, show that employing frequent patterns mined from an elite set of solutions conducted to better results. Besides, additional performed experiments evidence that data mining strategies accelerate the process of finding good solutions. ^★★Work sponsored by CNPq research grants 300879/00-8 and 475124/03-0. ^†Work sponsored by CNPq research grant 475124/03-0.     

Pareto Ant Colony Optimization: A Metaheuristic Approach to Multiobjective Portfolio Selection

Selecting the “best” project portfolio out of a given set of investment proposals is a common and often critical management issue. Decision-makers must regularly consider multiple objectives and often have little a priori preference information available to them. Given these contraints, they can improve their chances of achieving success by following a two-phase procedure that first determines the solution space of all efficient (i.e., Pareto-optimal) portfolios and then allows them to interactively explore that space. However, the task of determining the solution space is not trivial: brute-force complete enumeration only works for small instances and the underlying NP-hard problem becomes increasingly demanding as the number of projects grows. Meta-heuristics provide a useful compromise between the amount of computation time necessary and the quality of the approximated solution space. This paper introduces Pareto Ant Colony Optimization as an especially effective meta-heuristic for solving the portfolio selection problem and compares its performance to other heuristic approaches (i.e., Pareto Simulated Annealing and the Non-Dominated Sorting Genetic Algorithm) by means of computational experiments with random instances. Furthermore, we provide a numerical example based on real world data.     

Metaheuristic procedures for the lexicographic bottleneck assembly line balancing problem

The goal of this work is to develop an improved procedure for the solution of the lexicographic bottleneck variant of the assembly line balancing problem (LB-ALBP). The objective of the LB-ALBP is to minimize the workload of the most heavily loaded workstation, followed by the workload of the second most heavily loaded workstation and so on. This problem—recently introduced to the literature (Pastor, 2011)—has practical relevance to manufacturing facilities. We design, implement and fine-tune GRASP, tabu search (TS) and scatter search (SS) heuristics for the LB-ALBP and show that our procedures are able to obtain solutions of a quality that outperforms previous approaches. We rely on both semi-greedy and memory-based designs that our experiments show to be effective. Experimental results verify the advantages of embedding such designs to improve the solution existing in the literature of this complex problem. Additionally, the extensive experimentation with 48 variants of GRASP, 12 of TS and 1 of SS establishes the benefits of adding enhanced search strategies to basic procedures.     

A model to optimize placement operations on dual-head placement machines

Dual-head placement machines are important in the assembly of circuit cards because they offer the capability to place large components accurately. This paper presents a novel column-generation approach for optimizing the placement operations of a dual-head placement machine with the ultimate goal of improving the efficiency of assembly operations. Research objectives are a model that reflects relevant, practical considerations; a solution method that can solve instances within reasonable run times; and tests to establish computational benchmarks. Test results demonstrate the efficacy of our optimization approach on problems of realistic size and scope.     

ILP approaches to the blockmodel problem

Blockmodelling is a method for identifying structural similarities or equivalences between elements which has applications in a variety of contexts, including multiattribute performance assessment. One criterion for forming blocks results in a difficult non-linear integer programme. We give several integer linear programming formulations of this problem and provide comparative computational results. We show that methods of reducing symmetry proposed by Sherali and Smith are not effective in this case and propose an iterative approach in which the size of the problem is reduced.     

Novel approaches to the discrimination problem

We consider the problem of determining a hyperplane that separates, as well as possible, two finite sets of points inR ⁿ . We analyze two criteria for judging the quality of a candidate hyperplane (i) the maximal distance of a misclassified point to the hyperplane (ii) the number of misclassified points. In each case, we investigate the computational complexity of the corresponding mathematical programs, give equivalent formulations, suggest solution algorithms and present preliminary numerical results.Research supported by NSERC grants 5789 and 46405, the Academic Research Program of the Department of National Defense (Canada) and FCAR grant 91NC0510. (Québec).     

Parallelization of a Two-Phase Metaheuristic for Routing Problems with Time Windows

This paper describes the parallelization of a two-phase metaheuristic for the vehicle routing problem with time windows and a central depot (VRPTW). The underlying objective function combines the minimization of the number of vehicles in the first search phase of the metaheuristic with the minimization of the total travel distance in the second search phase. The parallelization of the metaheuristic follows a type 3 parallelization strategy (cf. Crainic and Toulouse (2001). In F. Glover and G. Kochenberger (eds.). State-of-the-Art Handbook in Metaheuristics. Norwell, MA: Kluwer Academic Publishers), i.e. several concurrent searches of the solution space are carried out with a differently configured metaheuristic. The concurrently executed processes cooperate through the exchange of solutions. The parallelized two-phase metaheuristic was subjected to a comparative test on the basis of 358 problems from the literature with sizes varying from 100 to 1000 customers. The derived results seem to justify the proposed parallelization concept.     

Some approaches to the theory of information systems

A formal method for performing systems analysis of information systems in business and elsewhere is needed in order to save systems work and programming and to obtain better systems.For organization and handling of information and data a formal procedure based on graph-theoretic concepts is described. It is shown that data transport in the system is determined by file volumes and the systems topology and expressed by the topological transport factor. The quality of the system design can be measured by its transport factor and the relation of this to the topological transport factor.On this basis future development of algorithms for minimal data transport and of standard lists for file contents and typical transport factors are expected. Much of the systems analysis and synthesis work can then be done by computers.It is also shown how the organization of file records is determined by the systems network.     

Integer programming approaches to the travelling salesman problem

The availability of an LP routine where we can add constraints and reoptimize, makes it possible to adopt an integer programming approach to the travelling-salesman problem.Starting with some of the constraints that define the problem we use either a branching process or a cutting planes routine to eliminate fractional solutions. We then test the resulting integer solution against feasibility and if necessary we generate the violated constraints and reoptimize until a genuine feasible solution is achieved.Usually only a small number of the omitted constraints is generated.The generality of the method and the modest solution times achieved leads us to believe that such an LP approach to other combinatorial problems deserves further consideration.     

Metaheuristic algorithms hybridised with variable neighbourhood search for solving the response time variability problem

The response time variability problem (RTVP) is a scheduling problem with a wide range of real-world applications: mixed-model assembly lines, multi-threaded computer systems, network environments, broadcast of commercial videotapes and machine maintenance, among others. The RTVP arises whenever products, clients or jobs need to be sequenced in such a way that the variability in the time between the points at which they receive the necessary resources is minimised. Since the RTVP is NP-hard, several heuristic and metaheuristic techniques are needed to solve non-small instances. The published metaheuristic procedure that obtained the best solutions, on average, for non-small RTVP instances is an algorithm based on a variant of the variable neighbourhood search (VNS), called Reduced VNS (RVNS). We propose hybridising RVNS with three existing algorithms based on tabu search, multi-start and particle swarm optimisation. The aim is to combine the strengths of the metaheuristics. A computational experiment is carried out and it is shown that, on average, all proposed hybrid methods are able to improve the best published solutions.     

Adaptive approaches to stochastic programming

Economists have found a need to model agents who behave in ways that are not consistent with the traditional notions of rational behavior under uncertainty but that are oriented in some looser manner toward achieving good outcomes. Adaptation over time in a myopic manner, rather that forward-looking optimization, has been proposed as one such model of behavior that displays bounded rationality. This paper investigates the relationship between adaptation as a model of behavior and as an algorithmic approach that has been used in computing solutions to optimization problems. It describes a specific adaptive model of behavior in discrete choice problems, one that is closely related to adaptive algorithms for optimization, and shows that this model can be fruitfully applied in studying several economic issues.     

New approaches to multi-objective optimization

A natural way to deal with multiple, partially conflicting objectives is turning all the objectives but one into budget constraints. Many classical optimization problems, such as maximum spanning tree and forest, shortest path, maximum weight (perfect) matching, maximum weight independent set (basis) in a matroid or in the intersection of two matroids, become NP-hard even with one budget constraint. Still, for most of these problems efficient deterministic and randomized approximation schemes are known. Not much is known however about the case of two or more budgets: filling this gap, at least partially, is the main goal of this paper. In more detail, we obtain the following main results: Using iterative rounding for the first time in multi-objective optimization, we obtain multi-criteria PTASs (which slightly violate the budget constraints) for spanning tree, matroid basis, and bipartite matching with \(k=O(1)\) budget constraints. We present a simple mechanism to transform multi-criteria approximation schemes into pure approximation schemes for problems whose feasible solutions define an independence system. This gives improved algorithms for several problems. In particular, this mechanism can be applied to the above bipartite matching algorithm, hence obtaining a pure PTAS. We show that points in low-dimensional faces of any matroid polytope are almost integral, an interesting result on its own. This gives a deterministic approximation scheme for \(k\) -budgeted matroid independent set. We present a deterministic approximation scheme for \(k\) -budgeted matching (in general graphs), where \(k=O(1)\) . Interestingly, to show that our procedure works, we rely on a non-constructive result by Stromquist and Woodall, which is based on the Ham Sandwich Theorem.     

Parametric approaches to fractional programs

The fractional program P is defined by maxf(x)/g(x) subject tox∈X. A class of methods for solving P is based on the auxiliary problem Q(λ) with a parameter λ: maxf(x)?λg(x) subject tox∈X. Starting with two classical methods in this class, the Newton method and the binary search method, a number of variations are introduced and compared. Among the proposed methods. the modified binary search method is theoretically interesting because of its superlinear convergence and the capability to provide an explicit interval containing the optimum parameter value \(\bar \lambda \) . Computational behavior is tested by solving fractional knapsack problems and quadratic fractional programs. The interpolated binary search method seems to be most efficient, while other methods also behave surprisingly well.