To date, most methods for direct blockmodeling of social network data have focused on the optimization of a single objective function. However, there are a variety of social network applications where it is advantageous to consider two or more objectives simultaneously. These applications can broadly be placed into two categories: (1) simultaneous optimization of multiple criteria for fitting a blockmodel based on a single network matrix and (2) simultaneous optimization of multiple criteria for fitting a blockmodel based on two or more network matrices, where the matrices being fit can take the form of multiple indicators for an underlying relationship, or multiple matrices for a set of objects measured at two or more different points in time. A multiobjective tabu search procedure is proposed for estimating the set of Pareto efficient blockmodels. This procedure is used in three examples that demonstrate possible applications of the multiobjective blockmodeling paradigm.

Two-mode binary data matrices arise in a variety of social network contexts, such as the attendance or non-attendance of individuals at events, the participation or lack of participation of groups in projects, and the votes of judges on cases. A popular method for analyzing such data is two-mode blockmodeling based on structural equivalence, where the goal is to identify partitions for the row and column objects such that the clusters of the row and column objects form blocks that are either complete (all 1s) or null (all 0s) to the greatest extent possible. Multiple restarts of an object relocation heuristic that seeks to minimize the number of inconsistencies (i.e., 1s in null blocks and 0s in complete blocks) with ideal block structure is the predominant approach for tackling this problem. As an alternative, we propose a fast and effective implementation of tabu search. Computational comparisons across a set of 48 large network matrices revealed that the new tabu-search heuristic always provided objective function values that were better than those of the relocation heuristic when the two methods were constrained to the same amount of computation time.

The selection of a subset of variables from a pool of candidates is an important problem in several areas of multivariate statistics. Within the context of principal component analysis (PCA), a number of authors have argued that subset selection is crucial for identifying those variables that are required for correct interpretation of the components. In this paper, we adapt the variable neighborhood search (VNS) paradigm to develop two heuristics for variable selection in PCA. The performances of these heuristics were compared to those obtained by a branch-and-bound algorithm, as well as forward stepwise, backward stepwise, and tabu search heuristics. In the first experiment, which considered candidate pools of 18 to 30 variables, the VNS heuristics matched the optimal subset obtained by the branch-and-bound algorithm more frequently than their competitors. In the second experiment, which considered candidate pools of 54 to 90 variables, the VNS heuristics provided better solutions than their competitors for a large percentage of the test problems. An application to a real-world data set is provided to demonstrate the importance of variable selection in the context of PCA.

The clique partitioning problem (CPP) requires the establishment of an equivalence relation for the vertices of a graph such that the sum of the edge costs associated with the relation is minimized. The CPP has important applications for the social sciences because it provides a framework for clustering objects measured on a collection of nominal or ordinal attributes. In such instances, the CPP incorporates edge costs obtained from an aggregation of binary equivalence relations among the attributes. We review existing theory and methods for the CPP and propose two versions of a new neighborhood search algorithm for efficient solution. The first version (NS-R) uses a relocation algorithm in the search for improved solutions, whereas the second (NS-TS) uses an embedded tabu search routine. The new algorithms are compared to simulated annealing (SA) and tabu search (TS) algorithms from the CPP literature. Although the heuristics yielded comparable results for some test problems, the neighborhood search algorithms generally yielded the best performances for large and difficult instances of the CPP.

Discrete-continuous project scheduling problems with positive discounted cash flows andthe maximization of the NPV are considered. We deal with a class of theseproblems with an arbitrary number of discrete resources and one continuous, renewableresource. Activities are nonpreemptable, and the processing rate of an activity is acontinuous, increasing function of the amount of the continuous resource allotted to theactivity at a time. Three common payment models – Lump Sum Payment, Payments at ActivityCompletion times, and payments in Equal Time Intervals are analyzed. Formulations ofmathematical programming problems for an optimal continuous resource allocation for eachpayment model are presented. Applications of two local search metaheuristics – Tabu Searchand Simulated Annealing are proposed. The algorithms are compared on a basis ofcomputational experiments. Some conclusions and directions for future research are pointedout.

This paper addresses a Three-Dimensional Loading Capacitated Vehicle Routing Problem(3L-CVRP) which combines a three-dimensional loading problem and vehicle routing problemin distribution logistics. The problem requires the combinatorial optimization of afeasible loading solution and a successive routing of vehicles to satisfy client demands,where all vehicles must start and terminate at a central depot. In spite of its clearpractical significance in the real world of distribution management, 3L-CVRP in literatureis very limited for its high combinatorial complexity. We solve this problem by a hybridapproach which combines Genetic Algorithm and Tabu Search (GATS). Genetic algorithm isdeveloped for vehicle routing and tabu search for three-dimensional loading, while thesetwo algorithms are integrated for the combinatorial problem. We computationally evaluatethis hybrid genetic algorithm on all publicly available test instances, and obtain newbest solutions for several instances.

We present in this paper a new multiobjective memetic algorithm scheme called MEMOX. In current multiobjective memetic algorithms, the parents used for recombination are randomly selected. We improve this approach by using a dynamic hypergrid which allows to select a parent located in a region of minimal density. The second parent selected is a solution close, in the objective space, to the first parent. A local search is then applied to the offspring. We experiment this scheme with a new multiobjective tabu search called PRTS, which leads to the memetic algorithm MEMOTS. We show on the multidimensional multiobjective knapsack problem that if the number of objectives increase, it is preferable to have a diversified research rather using an advanced local search. We compare the memetic algorithm MEMOTS to other multiobjective memetic algorithms by using different quality indicators and show that the performances of the method are very interesting.

This paper deals with the problem of scheduling n tasks on m identical processors in the presence of communication delays. A new approach of modelisation by a decision graph and a resolution by a tabu search method is proposed. Initial solutions are constructed by list algorithms, and then improved by a tabu algorithm operating in two phases. The experiments carried on arbitrary graphs show the efficiency of our method and that it outperformed the principle existent heuristics.