A three-phased local search approach for the clique partitioning problem

This paper presents a three-phased local search heuristic CPP-P\(^{3}\) for solving the Clique Partitioning Problem (CPP). CPP-P\(^{3}\) iterates a descent search, an exploration search and a directed perturbation. We also define the Top Move of a vertex, in order to build a restricted and focused neighborhood. The exploration search is ensured by a tabu procedure, while the directed perturbation uses a GRASP-like method. To assess the performance of the proposed approach, we carry out extensive experiments on benchmark instances of the literature as well as newly generated instances. We demonstrate the effectiveness of our approach with respect to the current best performing algorithms both in terms of solution quality and computation efficiency. We present improved best solutions for a number of benchmark instances. Additional analyses are shown to highlight the critical role of the Top Move-based neighborhood for the performance of our algorithm and the relation between instance hardness and algorithm behavior.     

An adaptive multistart tabu search approach to solve the maximum clique problem

Given an undirected graph G=(V,E) with vertex set V={1,…,n} and edge set E?V×V. The maximum clique problem is to determine in G a clique (i.e., a complete subgraph) of maximum cardinality. This paper presents an effective algorithm for the maximum clique problem. The proposed multistart tabu search algorithm integrates a constrained neighborhood, a dynamic tabu tenure mechanism and a long term memory based restart strategy. Our proposed algorithm is evaluated on the whole set of 80 DIMACS challenge benchmarks and compared with five state-of-the-art algorithms. Computational results show that our proposed algorithm attains the largest known clique for 79 benchmarks.     

Improvements to MCS algorithm for the maximum clique problem

In this paper we present improvements to one of the most recent and fastest branch-and-bound algorithm for the maximum clique problem—MCS algorithm by Tomita et al. (Proceedings of the 4th international conference on Algorithms and Computation, WALCOM’10, pp. 191–203, 2010). The suggested improvements include: incorporating of an efficient heuristic returning a high-quality initial solution, fast detection of clique vertices in a set of candidates, better initial colouring, and avoiding dynamic memory allocation. Our computational study shows some impressive results, mainly we have solved p_hat1000-3 benchmark instance which is intractable for MCS algorithm and got speedups of 7, 3000, and 13000 times for gen400_p0.9_55, gen400_p0.9_65, and gen400_p0.9_75 instances correspondingly.     

An exact algorithm for the maximum probabilistic clique problem

The maximum clique problem is a classical problem in combinatorial optimization that has a broad range of applications in graph-based data mining, social and biological network analysis and a variety of other fields. This article investigates the problem when the edges fail independently with known probabilities. This leads to the maximum probabilistic clique problem, which is to find a subset of vertices of maximum cardinality that forms a clique with probability at least \(\theta \in [0,1]\) , which is a user-specified probability threshold. We show that the probabilistic clique property is hereditary and extend a well-known exact combinatorial algorithm for the maximum clique problem to a sampling-free exact algorithm for the maximum probabilistic clique problem. The performance of the algorithm is benchmarked on a test-bed of DIMACS clique instances and on a randomly generated test-bed.     

On the number of local minima for the multidimensional assignment problem

The Multidimensional Assignment Problem (MAP) is an NP-hard combinatorial optimization problem occurring in many applications, such as data association, target tracking, and resource planning. As many solution approaches to this problem rely, at least partly, on local neighborhood search algorithms, the number of local minima affects solution difficulty for these algorithms. This paper investigates the expected number of local minima in randomly generated instances of the MAP. Lower and upper bounds are developed for the expected number of local minima, E[M], in an MAP with iid standard normal coefficients. In a special case of the MAP, a closed-form expression for E[M] is obtained when costs are iid continuous random variables. These results imply that the expected number of local minima is exponential in the number of dimensions of the MAP. Our numerical experiments indicate that larger numbers of local minima have a statistically significant negative effect on the quality of solutions produced by several heuristic algorithms that involve local neighborhood search.Partially supported by the NSF grant DMI-0457473.     

Solving the maximum vertex weight clique problem via binary quadratic programming

In recent years, the general binary quadratic programming (BQP) model has been widely applied to solve a number of combinatorial optimization problems. In this paper, we recast the maximum vertex weight clique problem (MVWCP) into this model which is then solved by a probabilistic tabu search algorithm designed for the BQP. Experimental results on 80 challenging DIMACS-W and 40 BHOSLIB-W benchmark instances demonstrate that this general approach is viable for solving the MVWCP problem.     

Two new robust genetic algorithms for the flowshop scheduling problem

The flowshop scheduling problem (FSP) has been widely studied in the literature and many techniques for its solution have been proposed. Some authors have concluded that genetic algorithms are not suitable for this hard, combinatorial problem unless hybridization is used. This work proposes new genetic algorithms for solving the permutation FSP that prove to be competitive when compared to many other well known algorithms. The optimization criterion considered is the minimization of the total completion time or makespan (_Cmax$C_{\max }$). We show a robust genetic algorithm and a fast hybrid implementation. These algorithms use new genetic operators, advanced techniques like hybridization with local search and an efficient population initialization as well as a new generational scheme. A complete evaluation of the different parameters and operators of the algorithms by means of a Design of Experiments approach is also given. The algorithm's effectiveness is compared against 11 other methods, including genetic algorithms, tabu search, simulated annealing and other advanced and recent techniques. For the evaluations we use Taillard's well known standard benchmark. The results show that the proposed algorithms are very effective and at the same time are easy to implement.     

An iterated local search with multiple perturbation operators and time varying perturbation strength for the aircraft landing problem

Landing aircraft safely is an important operation that air traffic controllers have to deal with on a daily basis. For each arriving aircraft a runway and a landing time must be allocated. If these allocations can be done in an efficient way, it could give the airport a competitive advantage. The Aircraft Landing Problem (ALP) aims to minimize the deviation from a preferred target time of each aircraft. It is an NP-hard problem, meaning that we may have to resort to heuristic methods as exact methods may not be suitable, especially as the problem size increases. This paper proposes an iterated local search (ILS) algorithm for the ALP. ILS is a single solution based search methodology that successively invokes a local search procedure to find a local optimum solution. A perturbation operator is used to modify the current solution in order to escape from the local optimum and to provide a new solution for the local search procedure. As different problems and/or instances have different characteristics, the success of the ILS is highly dependent on the local search, the perturbation operator(s) and the perturbation strength. To address these issues, we utilize four perturbation operators and a time varying perturbation strength which changes as the algorithm progresses. A variable neighborhood descent algorithm is used as our local search. The proposed ILS generates high quality solutions for the ALP benchmark instances taken from the scientific literature, demonstrating its efficiency in terms of both solution quality and computational time. Moreover, the proposed ILS produces new best results for some instances.     

The triggers of local and distant search: Relative magnitude and persistence in explaining acquisition relatedness

Research on problemistic search has assumed negative attainment discrepancy to be the trigger of both local and distant search. Extending this research, we present and compare two additional triggers: (1) relative attainment discrepancy, which reflects how much a firm's attainment discrepancy deviates from its past negative attainment discrepancies; and (2) persistent attainment discrepancy, which reflects how often the firm experiences below-aspirations performance. Our triggers for distant search model a behavioral explanation for the timing and relatedness of acquisitions. We find support for baseline arguments of problemistic search whereby firms increase both industry- and skill-related acquisitions when they perform below aspirations. When they persistently perform below aspirations, however, this likelihood is reduced and firms engage in acquisitions that are more unrelated, thereby providing support for the notion of expanding search boundaries from local to distant search. Of the two triggers of distant search proposed, relative attainment discrepancy does not induce firms to expand search boundaries. Our results indicate that persistent attainment discrepancy is a key construct to consider when studying the expansion of search boundaries.     

An exponential (matching based) neighborhood for the vehicle routing problem

We introduce an exponential neighborhood for the Vehicle Routing Problem (vrp) with unit customers’ demands, and we show that it can be explored efficiently in polynomial time by reducing its exploration to a particular case of the Restricted Complete Matching (rcm) problem that we prove to be polynomial time solvable using flow techniques. Furthermore, we show that in the general case with non-unit customers’ demands the exploration of the neighborhood becomes an -hard problem.     

An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem

In the no-idle flowshop, machines cannot be idle after finishing one job and before starting the next one. Therefore, start times of jobs must be delayed to guarantee this constraint. In practice machines show this behavior as it might be technically unfeasible or uneconomical to stop a machine in between jobs. This has important ramifications in the modern industry including fiber glass processing, foundries, production of integrated circuits and the steel making industry, among others. However, to assume that all machines in the shop have this no-idle constraint is not realistic. To the best of our knowledge, this is the first paper to study the mixed no-idle extension where only some machines have the no-idle constraint. We present a mixed integer programming model for this new problem and the equations to calculate the makespan. We also propose a set of formulas to accelerate the calculation of insertions that is used both in heuristics as well as in the local search procedures. An effective iterated greedy (IG) algorithm is proposed. We use an NEH-based heuristic to construct a high quality initial solution. A local search using the proposed accelerations is employed to emphasize intensification and exploration in the IG. A new destruction and construction procedure is also shown. To evaluate the proposed algorithm, we present several adaptations of other well-known and recent metaheuristics for the problem and conduct a comprehensive set of computational and statistical experiments with a total of 1750 instances. The results show that the proposed IG algorithm outperforms existing methods in the no-idle and in the mixed no-idle scenarios by a significant margin.     

Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logistics

This paper addresses a periodic vehicle routing problem encountered in home health care (HHC) logistics. It extends the classical Periodic Vehicle Routing Problem with Time Windows (PVRPTW) to three types of demands of patients at home. Demands include transportation of drugs/medical devices between the HHC depot and patients׳ homes, delivery of special drugs from the hospital to patients, and delivery of blood samples from patients to the lab. Each patient requires a certain number of visits within a planning horizon and has a set of possible combinations of visit days. Daily routing should meet time window constraints associated with patients, the hospital and the lab. The problem consists in determining the visit days of each patient and vehicle routes for each day in order to minimize the maximal routing costs among all routes over the horizon. We propose a Tabu Search method combined with different local search schemes including both feasible and infeasible local searches. The proposed approaches are tested on a range of instances derived from existing Vehicle Routing Problem with Time Window (VRPTW) benchmarks and benchmarks on special cases of our problem. Numerical results show that local search scheme starting with an infeasible local search with a small probability followed by a feasible local search with high probability is an interesting hybridization. Experiments with field data from a HHC company show that the proposed approach reduces the total cost and better balances the workloads of vehicles.     

A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries

The vehicle routing problem with pickups and deliveries (VRPPD) extends the vehicle routing problem (VRP) by allowing customers to both send and receive goods. The main difficulty of the problem is that the load of vehicles is fluctuating rather than decreasing as in the VRP. We design a reactive tabu search metaheuristic that can check feasibility of proposed moves quickly and reacts to repetitions to guide the search. Several new best solutions are found for benchmark problems.     

Benders decomposition for a strategic network design problem under NAFTA local content requirements

Global production and sourcing strategies of multinational corporations are strongly influenced by the increasing number of Free Trade Agreements (FTAs). Based on the special local content requirements of the North American Free Trade Agreement (NAFTA) for automotive goods, the impact on strategic network design decisions is investigated. The presented model explicitly integrates the different NAFTA legal options to calculate the local content for automotive goods. Furthermore, it considers the possibility to underachieve the local content requirement and to pay penalty duties for NAFTA cross-border deliveries instead. Plant fixed costs have a significant impact on the local content fulfillment and have to be allocated in accordance with the actual plant utilization and the different local content calculation options. Due to the resulting non-linearity of the mixed-integer program, a solution algorithm based on Benders decomposition is presented. In addition, we introduce multiple Benders cuts to improve the efficiency and applicability to real-world planning problems. Compared to piecewise linearization approaches, the run-time can be improved significantly. In a numerical study, the impact of local content requirements on the strategic network design is shown and the different NAFTA options to calculate the local content for automotive goods are compared with each other. Furthermore, computational experiments are performed to evaluate the applicability and efficiency of Benders decomposition.     

大规模邻域搜索算法求解时变车辆调度问题

对时变网络车辆调度问题提出一种满足先入先出准则的时变处理方法,并建立相应的数学模型,提出一种基于大规模邻域搜索技术的智能优化算法进行求解,算法顶层采用动态规划算法搜索环状交换邻域以得到每辆车的最佳服务顾客集合;底层设计动态搜索算法用以安排每辆车的最佳服务路线.在此基础上提出顶层加入虚拟顾客和底层嵌入insert两类改进策略.通过实验仿真比较,验证了所提算法的有效性.     

Combinatorial algorithms for the maximum k-plex problem

The maximum clique problem provides a classic framework for detecting cohesive subgraphs. However, this approach can fail to detect much of the cohesive structure in a graph. To address this issue, Seidman and Foster introduced k-plexes as a degree-based clique relaxation. More recently, Balasundaram et al. formulated the maximum k-plex problem as an integer program and designed a branch-and-cut algorithm. This paper derives a new upper bound on the cardinality of k-plexes and adapts combinatorial clique algorithms to find maximum k-plexes.     

The permutation flow shop problem with blocking. A tabu search approach

This paper develops a fast tabu search algorithm to minimize makespan in a flow shop problem with blocking. Some properties of the problem associated with the blocks of jobs have been presented and discussed. These properties allow us to propose a specific neighbourhood of algorithms. Also, the multimoves are used that consist in performing several moves simultaneously in a single iteration and guide the search process to more promising areas of the solutions space, where good solutions can be found. It allow us to accelerate the convergence of the algorithm. Besides, a dynamic tabu list is proposed that assists additionally to avoid being trapped at a local optimum. The proposed algorithms are empirically evaluated and found to be relatively more effective in finding better solutions than attained by the leading approaches in a much shorter time. The presented ideas can be applied in many local search procedures.     

Simulation optimization through direct search for multi-objective manufacturing systems

Simulation modelling has been one of the most widely used techniques for analysing complex manufacturing systems. In this paper, we propose a direct search algorithm expanded from the Hooke-Jecves pattern search to systematically and efficiently locate satisfactory solutions for multi-objective simulation models. The user-specified goals can be precise and/or fuzzy. Heuristic rules stemming from the simulation result of resource statistics are incorporated into the Hooke-Jeeves pattern search. The proposed heuristic rules make the search procedure effective regardless of different initial points and various bounded ranges of decision variables. Experimental results show that the proposed approach is suitable for analysing complex manufacturing systems, in which multiple objectives and multiple decision variables are encountered.     

Tabu search for the real-world carpooling problem

Carpooling is a flexible shared transportation system which can effectively reduce the vehicle numbers and fuel consumption. Although many carpooling systems have been proposed, most of them lack practicality, veracity, and efficiency. In this paper, we propose a new useful variant model of the long-term carpooling problem which involves multiple origins and one destination. Such problems commonly occur in a wide number of carpooling situations in real-world scenarios. Our work is motivated by the practical needs to solve environmental pollution, parking problems, traffic jams and low utilization of resources. A Tabu search algorithm is proposed in this paper to solve the carpooling problem. The proposed algorithm aims at a wide range of passenger distribution and routing problems. The computational results based on real world user data show the effectiveness of the proposed algorithm. Moreover, we developed a mobile application based on our carpooling model.     

Algorithms for the maximum k-club problem in graphs

Given a simple undirected graph G, a k-club is a subset of vertices inducing a subgraph of diameter at most k. The maximum k-club problem (MkCP) is to find a k-club of maximum cardinality in G. These structures, originally introduced to model cohesive subgroups in social network analysis, are of interest in network-based data mining and clustering applications. The maximum k-club problem is NP-hard, moreover, determining whether a given k-club is maximal (by inclusion) is NP-hard as well. This paper first provides a sufficient condition for testing maximality of a given k-club. Then it proceeds to develop a variable neighborhood search (VNS) heuristic and an exact algorithm for MkCP that uses the VNS solution as a lower bound. Computational experiments with test instances available in the literature show that the proposed algorithms are very effective on sparse instances and outperform the existing methods on most dense graphs from the testbed.