A computational study of constraint satisfaction for multiple capacitated job shop scheduling

We introduce the multiple capacitated job shop scheduling problem as a generalization of the job shop scheduling problem. In this problem machines may process several operations simultaneously. We present an algorithm based on constraint satisfaction techniques to handle the problem effectively. The most important novel feature of our algorithm is the consistency checking. An empirical performance analysis is performed using a well-known set of instances of the job shop scheduling problem and a newly constructed set of instances of the multiple capacitated job shop scheduling problem. We show that our algorithm performs well for both sets of instances.     

Model-hierarchical column generation and heuristic for the routing and wavelength assignment problem

The routing and wavelength assignment (RWA) problem typically occurs in wavelength division multiplexing optical networks. Given a number of available wavelengths, we consider here the problem of maximising the number of accepted connections with respect to the clash and continuity constraints. We first propose a new strategy which combines two existing models. This leads to an improved column generation scheme. We also present two heuristics to compute feasible solutions: a hybrid heuristic and the integer solution at the root node of the column generation. Our approaches are compared with the best existing results on a set of classic RWA instances.     

An Ant Colony Optimization Algorithm for Shop Scheduling Problems

We deal with the application of ant colony optimization to group shop scheduling, which is a general shop scheduling problem that includes, among others, the open shop scheduling problem and the job shop scheduling problem as special cases. The contributions of this paper are twofold. First, we propose a neighborhood structure for this problem by extending the well-known neighborhood structure derived by Nowicki and Smutnicki for the job shop scheduling problem. Then, we develop an ant colony optimization approach, which uses a strong non-delay guidance for constructing solutions and which employs black-box local search procedures to improve the constructed solutions. We compare this algorithm to an adaptation of the tabu search by Nowicki and Smutnicki to group shop scheduling. Despite its general nature, our algorithm works particularly well when applied to open shop scheduling instances, where it improves the best known solutions for 15 of the 28 tested instances. Moreover, our algorithm is the first competitive ant colony optimization approach for job shop scheduling instances.     

An efficient genetic algorithm for single row facility layout

The single row facility layout is the NP-Hard problem of arranging facilities with given lengths on a line, so as to minimize the weighted sum of the distances between all pairs of facilities. Owing to its computational complexity, researchers have developed several heuristics to obtain good quality solutions. In this paper, we present a genetic algorithm called GENALGO to solve large single row facility layout problem instances. Our algorithm uses standard genetic operators and periodically improves the fitness of all individuals. Our computational experiments show that our genetic algorithm yields high quality solutions in spite of starting with an initial population that is randomly generated. Our algorithm improves the previously best known solutions for the 19 instances of 58 benchmark instances and is competitive for most of the remaining ones.     

A Multilevel Search Algorithm for the Maximization of Submodular Functions Applied to the Quadratic Cost Partition Problem

Maximization of submodular functions on a ground set is a NP-hard combinatorial optimization problem. Data correcting algorithms are among the several algorithms suggested for solving this problem exactly and approximately. From the point of view of Hasse diagrams data correcting algorithms use information belonging to only one level in the Hasse diagram adjacent to the level of the solution at hand. In this paper, we propose a data correcting algorithm that looks at multiple levels of the Hasse diagram and hence makes the data correcting algorithm more efficient. Our computations with quadratic cost partition problems show that this multilevel search effects a 8- to 10-fold reduction in computation times, so that some of the dense quadratic partition problem instances of size 500, currently considered as some of the most difficult problems and far beyond the capabilities of current exact methods, are solvable on a personal computer working at 300 MHz within 10 min.     

Arc-based integer programming formulations for three variants of proportional symbol maps

Proportional symbol maps are a cartographic tool that employs scaled symbols to represent data associated with specific locations. The symbols we consider are opaque disks, which may be partially covered by other overlapping disks. We address the problem of creating a suitable drawing of the disks that maximizes one of two quality metrics: the total and the minimum visible length of disk boundaries. We study three variants of this problem, two of which are known to be NP-hard and another whose complexity is open. We propose novel integer programming formulations for each problem variant and test them on real-world instances with a branch-and-cut algorithm. When compared with state-of-the-art models from the literature, our models significantly reduce computation times for most instances.     

A hybrid multistart heuristic for the uncapacitated facility location problem

We present a multistart heuristic for the uncapacitated facility location problem, based on a very successful method we originally developed for the p-median problem. We show extensive empirical evidence to the effectiveness of our algorithm in practice. For most benchmarks instances in the literature, we obtain solutions that are either optimal or a fraction of a percentage point away from it. Even for pathological instances (created with the sole purpose of being hard to tackle), our algorithm can get very close to optimality if given enough time. It consistently outperforms other heuristics in the literature.     

Upper and lower bounding procedures for the multiple knapsack assignment problem

We formulate the multiple knapsack assignment problem (MKAP) as an extension of the multiple knapsack problem (MKP), as well as of the assignment problem. Except for small instances, MKAP is hard to solve to optimality. We present a heuristic algorithm to solve this problem approximately but very quickly. We first discuss three approaches to evaluate its upper bound, and prove that these methods compute an identical upper bound. In this process, reference capacities are derived, which enables us to decompose the problem into mutually independent MKPs. These MKPs are solved euristically, and in total give an approximate solution to MKAP. Through numerical experiments, we evaluate the performance of our algorithm. Although the algorithm is weak for small instances, we find it prospective for large instances. Indeed, for instances with more than a few thousand items we usually obtain solutions with relative errors less than 0.1% within one CPU second.     

A Tabu Search Algorithm for the Quadratic Assignment Problem

Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). One of the most important features of our tabu search implementation is an efficient use of mutations applied to the best solutions found so far. We tested this approach on a number of instances from the library of the QAP instances—QAPLIB. The results obtained from the experiments show that the proposed algorithm belongs to the most efficient heuristics for the QAP. The high efficiency of this algorithm is also demonstrated by the fact that the new best known solutions were found for several QAP instances.     

A hybrid heuristic for the maximum clique problem

In this paper we present a heuristic based steady-state genetic algorithm for the maximum clique problem. The steady-state genetic algorithm generates cliques, which are then extended into maximal cliques by the heuristic. We compare our algorithm with three best evolutionary approaches and the overall best approach, which is non-evolutionary, for the maximum clique problem and find that our algorithm outperforms all the three evolutionary approaches in terms of best and average clique sizes found on majority of DIMACS benchmark instances. However, the obtained results are much inferior to those obtained with the best approach for the maximum clique problem.     

Classical and new heuristics for the open-shop problem: A computational evaluation

We study the problem of constructing minimum makespan schedules for the Open-Shop problem. This paper presents two new heuristics: the first one is a list scheduling algorithm with two priorities. The second is based on the construction of matchings in a bipartite graph. We develop several versions of these two heuristics. A computational evaluation shows that around 90% of randomly generated instances are solvable optimally, whereas classical (list scheduling) heuristics achieve less than 20% on average. Therefore, our algorithms make most Open-Shop instances easy to solve in practice, and this raises the problem of generating hard instances. We extend the evaluation to two kinds of such instances: the results are not so good, but remain better than classical heuristics.     

Lot sizing with inventory gains

The lot sizing problem with inventory gains generalizes the classical lot sizing problem to one in which stock is not conserved. Instances of this problem can be polynomially transformed into instances of the classical problem. The implications for problems involving different production capacity limitations, backlogging and multilevel production are discussed.     

A two-phase tabu search based evolutionary algorithm for the maximum diversity problem

In this paper, we study the maximum diversity problem (MDP) which is equivalent to the quadratic unconstrained binary optimization (QUBO) problem with cardinality constraint. The MDP aims to select a subset of elements with given cardinality such that the sum of pairwise distances between any two elements in the selected subset is maximized. For solving this computationally challenging problem, we propose a two-phase tabu search based evolutionary algorithm (TPTS/EA), which integrates several distinguishing features to ensure the diversity and the quality of the evolution, such as a two-phase tabu search algorithm which consists of a dynamic candidate list (DCL) strategy-based traditional tabu search in the first phase and a solution-based tabu search procedure to refine the search in the second phase, and two path-relinking based recombination operators to generate new offspring solutions. Tested on three sets of totally 140 public instances in the literature, the study demonstrates the efficacy of the proposed TPTS/EA algorithm in terms of both solution quality and computational efficiency. Specifically, our proposed TPTS/EA algorithm is able to improve the previous best known results for 2 instances, while matching the previous best-known solutions for 130 instances. We also provide experimental evidences to highlight the beneficial effect of several important components in our TPTS/EA algorithm.     

AN ADAPTIVE MEMBRANE ALGORITHM FOR SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS

Membrane algorithms （MAs）, which inherit from P systems, constitute a new parallel and distribute framework for approximate computation. In the paper, a membrane algorithm is proposed with the improvement that the involved parameters can be adaptively chosen. In the algorithm, some membranes can evolve dynamically during the computing process to specify the values of the requested parameters. The new algorithm is tested on a well-known combinatorial optimization problem, the travelling salesman problem. The em-pirical evidence suggests that the proposed approach is efficient and reliable when dealing with 11 benchmark instances, particularly obtaining the best of the known solutions in eight instances. Compared with the genetic algorithm, simulated annealing algorithm, neural net-work and a fine-tuned non-adaptive membrane algorithm, our algorithm performs better than them. In practice, to design the airline network that minimize the total routing cost on the CAB data with twenty-five US cities, we can quickly obtain high quality solutions using our algorithm.     

An adaptive membrane algorithm for solving combinatorial optimization problems

Membrane algorithms (MAs), which inherit from P systems, constitute a new parallel and distribute framework for approximate computation. In the paper, a membrane algorithm is proposed with the improvement that the involved parameters can be adaptively chosen. In the algorithm, some membranes can evolve dynamically during the computing process to specify the values of the requested parameters. The new algorithm is tested on a well-known combinatorial optimization problem, the travelling salesman problem. The empirical evidence suggests that the proposed approach is efficient and reliable when dealing with 11 benchmark instances, particularly obtaining the best of the known solutions in eight instances. Compared with the genetic algorithm, simulated annealing algorithm, neural network and a fine-tuned non-adaptive membrane algorithm, our algorithm performs better than them. In practice, to design the airline network that minimize the total routing cost on the CAB data with twenty-five US cities, we can quickly obtain high quality solutions using our algorithm.     

A brain storm optimization approach for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem (CCVRP) is a combinatorial optimization problem which aims to minimize the sum of arrival times at customers. This paper presents a brain storm optimization algorithm to solve the CCVRP. Based on the characteristics of the CCVRP, we design new convergent and divergent operations. The convergent operation picks up and perturbs the best-so-far solution. It decomposes the resulting solution into a set of independent partial solutions and then determines a set of subproblems which are smaller CCVRPs. Instead of directly generating solutions for the original problem, the divergent operation selects one of three operators to generate new solutions for subproblems and then assembles a solution to the original problem by using those new solutions to the subproblems. The proposed algorithm was tested on benchmark instances, some of which have more than 560 nodes. The results show that our algorithm is very effective in contrast to the existing algorithms. Most notably, the proposed algorithm can find new best solutions for 8 medium instances and 7 large instances within short time.     

Heuristic solutions for the vehicle routing problem with time windows and synchronized visits

We present a simulated annealing based algorithm for a variant of the vehicle routing problem (VRP), in which a time window is associated with each client service and some services require simultaneous visits from different vehicles to be accomplished. The problem is called the VRP with time windows and synchronized visits. The algorithm features a set of local improvement methods to deal with various objectives of the problem. Experiments conducted on the benchmark instances from the literature clearly show that our method is fast and outperforms the existing approaches. It produces all known optimal solutions of the benchmark in very short computational times, and improves the best results for the rest of the instances.     

An exact algorithm for the sequential ordering problem and its application to switching energy minimization in compilers

This article presents an exact algorithm for the precedence-constrained traveling salesman problem, which is also known as the sequential ordering problem. This NP-hard problem has applications in various domains, including operational research and compilers. In this article, the problem is presented and solved in the context of minimizing switching energy in compilers. Most previous work on minimizing switching energy in the compiler domain has been limited to simple heuristics that are not guaranteed to give an optimal solution. In this work, we present an exact algorithm for solving the switching energy minimization problem using a branch-and-bound approach. The proposed algorithm is simple and intuitive, yet powerful. It is the first exact algorithm for the switching energy problem that is shown to solve real instances of the problem within a few seconds per instance. Compared to previous work in the operational research domain, the proposed algorithm is believed to be the most powerful exact algorithm that does not require a linear programming formulation. The proposed algorithm is experimentally evaluated using instances taken from a production compiler. The results show that with a time limit of 10 ms per node, the proposed algorithm optimally solves 99.8 % of the instances. It optimally solves instances with up to 598 nodes within a few seconds. The resulting switching cost is 16 % less than that produced without energy awareness and 5 % less than that produced by a commonly used heuristic.     

A fast heuristic algorithm for the maximum concurrent <Emphasis Type="Italic">k</Emphasis>-splittable flow problem

In this paper, we propose a fast heuristic algorithm for the maximum concurrent k-splittable flow problem. In such an optimization problem, one is concerned with maximizing the routable demand fraction across a capacitated network, given a set of commodities and a constant k expressing the number of paths that can be used at most to route flows for each commodity. Starting from known results on the k-splittable flow problem, we design an algorithm based on a multistart randomized scheme which exploits an adapted extension of the augmenting path algorithm to produce starting solutions for our problem, which are then enhanced by means of an iterative improvement routine. The proposed algorithm has been tested on several sets of instances, and the results of an extensive experimental analysis are provided in association with a comparison to the results obtained by a different heuristic approach and an exact algorithm based on branch and bound rules.     

Progress in the dual simplex method for large scale LP problems: practical dual phase 1 algorithms

The dual simplex algorithm has become a strong contender in solving large scale LP problems. One key problem of any dual simplex algorithm is to obtain a dual feasible basis as a starting point. We give an overview of methods which have been proposed in the literature and present new stable and efficient ways to combine them within a state-of-the-art optimization system for solving real world linear and mixed integer programs. Furthermore, we address implementation aspects and the connection between dual feasibility and LP-preprocessing. Computational results are given for a large set of large scale LP problems, which show our dual simplex implementation to be superior to the best existing research and open-source codes and competitive to the leading commercial code on many of our most difficult problem instances.