Manuel Laguna

A Genetic Algorithm for the Minimum Generating Set Problem

Lozano, M., M. Laguna, R. Martí, F. J. Rodríguez, and C. García-Martínez

​In this paper, we propose a genetic algorithm to solve the minimum generating set problem. Given a set of positive integers S, this hard optimization problem consists of finding a set of positive integers T with minimum cardinality such that every element of S can be expressed as the sum of a subset of elements in T. It constitutes a natural problem in combinatorial number theory and is related to some real-world problems, such as planning radiation therapies. We present a new formulation to this problem (based on the terminology for the multiple

knapsack problem) that is used to design an evolutionary approach whose performance is driven by three search strategies; a random greedy heuristic scheme that is employed to construct initial solutions, a specialized crossover operator inspired by realparameter

crossovers and a restart mechanism that is incorporated to avoid premature convergence. Computational results for problem instances involving up to 100 000 elements show that our innovative genetic algorithm is a very attractive alternative to the existing approaches.

A Simulation-Optimization Approach to Estimate Workforce Requirements

​Zais, M. and M. Laguna

​This article examines the capabilities and limitations of Monte Carlo simulation and optimization methods within the context of workforce demand forecasting, modeling and planning. Specifically, we focus on these methods as a viable improvement for aligning strategic goals with workforce requirements. A general model is presented for estimating workforce requirements given uncertain demand. Using a real-world data

example, we assess the benefits of this methodology to determine an optimal mix of workforce skills while providing the flexibility and robustness to incorporate uncertainty, assess risk and improve effectiveness of the holistic workforce planning process.

Heuristic Solution Approaches for the Maximum MinSum Dispersion Problem

Martínez-Gavara, A., V. Campos, M. Laguna, and R. Martí 

The Maximum Minsum Dispersion Problem (Max-Minsum DP) is a strongly NP-Hard problem that belongs to the family of equitable dispersion problems. When dealing with dispersion, the operations research literature has focused on optimizing efficiency-based objectives while neglecting, for the most part, measures of equity. The most common efficiency-based functions are the sum of the inter-element distances or the minimum inter-element distance. Equitable dispersion problems, on the other hand, attempt to address the balance between efficiency and equity when selecting a subset of elements from a larger set. The objective of the Max-Minsum DP is to maximize the minimum aggregate dispersion among the chosen elements. We develop tabu search and GRASP solution procedures for this problem and compare them against the best in the literature. We also apply LocalSolver, a commercially available black-box optimizer, to compare our results. Our computational experiments show that we are able to establish new benchmarks in the solution of the Max-Minsum DP.

Scatter Search for the Bandpass Problem

Oro-Sánchez, J., M. Laguna, A. Duarte, and R. Martí 

The bandpass problem arises in the area of telecommunications. The problem consists of creating blocks of data packets that need to be transmitted through a telecommunications network. The goal of the blocks is to reduce the number of devices needed for the transmission of the packets, resulting in a decrease of both installation and maintenance costs. The telecommunication network is modeled as a m × n binary matrix, where m is the number of data packets (rows) and n is the number of destination points (columns). The binary values indicate whether or not a packet must be delivered to a destination. We describe and tackle several versions of the bandpass problem that are derived from a basic framework in which a single bandpass number B is assumed to be known. For a given B, a bandpass consists of a block of B packets that are delivered to the same destination and that are arranged consecutively in the corresponding column. Packets that appear in consecutive rows in the matrix can be assigned to a single wavelength resulting in a reduction of equipment cost. The optimization problem is to order the rows (i.e., the packets) of the matrix in such a way that the number of bandpasses of size B is maximized. The problem is approached with a scatter search procedure that employs path relinking as the combination method.