The quadratic minimum spanning tree problem: A lower bounding procedure and an efficient search algorithm

In this paper we consider the quadratic minimum spanning tree problem (QMSTP) which is known to be NP-hard. Given a complete graph, the QMSTP consists of finding a minimum spanning tree (MST) where interaction costs between pairs of edges are prescribed. A Lagrangian relaxation procedure is devised and an efficient local search algorithm with tabu thresholding is developed. Computational experiments are reported on standard test instances, randomly generated test instances and quadratic assignment problem (QAP) instances from the QAPLIB by using a transformation scheme. The local search heuristic yields very good performance and the Lagrangian relaxation procedure gives the tightest lower bounds for all instances when compared to previous lower bounding approaches.     

A lower bound for the Node,Edge, and Arc Routing Problem

The Node, Edge, and Arc Routing Problem (NEARP) was defined by Prins and Bouchenoua in 2004, although similar problems have been studied before. This problem, also called the Mixed Capacitated General Routing Problem (MCGRP), generalizes the classical Capacitated Vehicle Routing Problem (CVRP), the Capacitated Arc Routing Problem (CARP), and the General Routing Problem. It captures important aspects of real-life routing problems that were not adequately modeled in previous Vehicle Routing Problem (VRP) variants. The authors also proposed a memetic algorithm procedure and defined a set of test instances called the CBMix benchmark. The NEARP definition and investigation contribute to the development of rich VRPs. In this paper we present the first lower bound procedure for the NEARP. It is a further development of lower bounds for the CARP. We also define two novel sets of test instances to complement the CBMix benchmark. The first is based on well-known CARP instances; the second consists of real life cases of newspaper delivery routing. We provide numerical results in the form of lower and best known upper bounds for all instances of all three benchmarks. For three of the instances, the gap between the upper and lower bound is closed. The average gap is 25.1%. As the lower bound procedure is based on a high quality lower bound procedure for the CARP, and there has been limited work on approximate solution methods for the NEARP, we suspect that a main reason for the rather large gaps is the quality of the upper bound. This fact, and the high industrial relevance of the NEARP, should motivate more research on approximate and exact methods for this important problem.     

A GRASP algorithm to solve the unicost set covering problem

The set covering problem (SCP) is a well-known combinatorial optimization problem. This paper presents a GRASP algorithm to solve a special SCP case known in the literature as the unicost set covering problem. The algorithm incorporates a local improvement procedure based on the heuristics to solve binary constraint satisfiability problems (SAT). The quality of the proposed algorithm is tested on a set of reference instances, comparing the obtained results with those found in the literature. Our algorithm improves the best-known solutions for many of these instances.     

An evolutionary implicit enumeration procedure for solving the resource‐constrained project scheduling problem

This paper presents a procedure for solving the resource‐constrained project scheduling problem. It consists of an implicit enumeration module and a genetic algorithm. If the procedure is provided access to all of its required computational resources of the problem at hand, it guarantees the optimality of the produced solution. In contrast, and in the case of limited access to computational resources, the procedure gradually moves the root of the search‐tree downward, and consequently prunes part of the search space, trading speed with precision effectively. In the cases where speed has been traded with precision, and the guarantee of optimality has been lost, the final schedule created by the implicit enumeration module is used as a template whose modified instances fill an initial pool of a genetic algorithm to improve the proposed solution. The procedure has been applied to 2040 benchmark instances. The results are promising; whereas for all small‐ and some medium‐sized instances, the procedure has found and guaranteed optimal solutions, for other instances, whose optimal solutions cannot be guaranteed within the limit of computational resources, it has produced high‐quality solutions.     

A three-phase algorithm for flowshop scheduling with blocking to minimize makespan

This paper proposes a three-phase algorithm (TPA) for the flowshop scheduling problem with blocking (BFSP) to minimize makespan. In the first phase, the blocking nature of BFSP is exploited to develop a priority rule that creates a sequence of jobs. Using this as the initial sequence and a variant of the NEH-insert procedure, the second phase generates an approximate solution to the problem. Then, utilizing a modified simulated annealing algorithm incorporated with a local search procedure, the schedule generated in the second phase is improved in the third phase. A pruning procedure that helps evaluate most solutions without calculating their complete makespan values is introduced in the local search to further reduce the computational time needed to solve the problem. Results of the computational experiments with Taillard's benchmark problem instances show that the proposed TPA algorithm is relatively more effective and efficient in minimizing makespan for the BFSP than the state-of-the-art procedures. Utilizing these results, 53 out of 60 new tighter upper bounds have been found for large-sized Taillard's benchmark problem instances.     

A water-flow algorithm for flexible flow shop scheduling with intermediate buffers

We investigate the flexible flow shop scheduling problem with limited or unlimited intermediate buffers. A common objective of the problem is to find a production schedule that minimizes the completion time of jobs. Other objectives that we also consider are minimizing the total weighted flow time of jobs and minimizing the total weighted tardiness time of jobs. We propose a water-flow algorithm to solve this scheduling problem. The algorithm is inspired by the hydrological cycle in meteorology and the erosion phenomenon in nature. In the algorithm, we combine the amount of precipitation and its falling force to form a flexible erosion capability. This helps the erosion process of the algorithm to focus on exploiting promising regions strongly. To initiate the algorithm, we use a constructive procedure to obtain a seed permutation. We also use an improvement procedure for constructing a complete schedule from a permutation that represents the sequence of jobs in the first stage of the scheduling problem. To evaluate the proposed algorithm, we use benchmark instances taken from the literature and randomly generated instances of the scheduling problem. The computational results demonstrate the efficacy of the algorithm. We have also obtained several improved solutions for the benchmark instances using the proposed algorithm. We further illustrate the algorithm’s capability for solving problems in practical applications by applying it to a maltose syrup production problem.     

Probabilistic GRASP-Tabu Search algorithms for the UBQP problem

This paper presents two algorithms combining GRASP and Tabu Search for solving the Unconstrained Binary Quadratic Programming (UBQP) problem. We first propose a simple GRASP-Tabu Search algorithm working with a single solution and then reinforce it by introducing a population management strategy. Both algorithms are based on a dedicated randomized greedy construction heuristic and a tabu search procedure. We show extensive computational results on two sets of 31 large random UBQP instances and one set of 54 structured instances derived from the MaxCut problem. Comparisons with state-of-the-art algorithms demonstrate the efficacy of our proposed algorithms in terms of both solution quality and computational efficiency. It is noteworthy that the reinforced GRASP-Tabu Search algorithm is able to improve the previous best known results for 19 MaxCut instances.     

Modeling and solving the steelmaking and casting scheduling problem

We propose a general model for the problem of planning and scheduling steelmaking and casting activities obtained by combining common features and constraints of the operations from a real plant and the literature. For tackling the problem, we develop a simulated annealing approach based on a solution space made of job permutations, which uses as submodule a chronological constructive procedure that assigns processing times and resources to jobs. Our technique, properly tuned in a statistically principled way, is able to find good solutions for a large range of different settings and horizons. In addition, it outperforms both a greedy procedure and a constraint‐based solver developed for comparison purposes on almost all instances. Finally, we have collected several real‐world instances that we make available on the web along with the solution validator and our best results.     

Path relinking for the vertex separator problem

This paper presents the first population-based path relinking algorithm for solving the NP-hard vertex separator problem in graphs. The proposed algorithm employs a dedicated relinking procedure to generate intermediate solutions between an initiating solution and a guiding solution taken from a reference set of elite solutions (population) and uses a fast tabu search procedure to improve some selected intermediate solutions. Special care is taken to ensure the diversity of the reference set. Dedicated data structures based on bucket sorting are employed to ensure a high computational efficiency. The proposed algorithm is assessed on four sets of 365 benchmark instances with up to 20,000 vertices, and shows highly comparative results compared to the state-of-the-art methods in the literature. Specifically, we report improved best solutions (new upper bounds) for 67 instances which can serve as reference values for assessment of other algorithms for the problem.     

Algorithm based on taboo search and shifting bottleneck for job shop scheduling

In this paper, a computational effective heuristic method for solving the minimum makespan problem of job shop scheduling is presented. It is based on taboo search procedure and on the shifting bottleneck procedure used to jump out of the trap of the taboo search procedure. A key point of the algorithm is that in the taboo search procedure two taboo lists are used to forbid two kinds of reversals of arcs, which is a new and effective way in taboo search methods for job shop scheduling. Computational experiments on a set of benchmark problem instances show that, in several cases, the approach, in reasonable time, yields better solutions than the other heuristic procedures discussed in the literature.     

Scheduling two parallel machines with machine-dependent availabilities

A two-parallel-machine scheduling problem with machine-dependent availabilities where one machine is subject to tool changes and the other is subject to periodic maintenance is considered. The objective is to determine the start time of each tool change activity and schedule all the jobs to the two machines such that the makespan is minimized. Due to the NP-hardness of the non-approximability of the problem, there does not exist any polynomial time approximation algorithm with a worst-case ratio less than 2 for the problem unless P=NP. To solve small sized and moderate sized instances of the problem, a mixed 0–1 programming model is proposed. To solve large sized instances of the problem, nine heuristic algorithms that employ two classical dispatching rules, two assignment mechanisms and a post-optimization procedure are proposed. To evaluate the performance of the algorithms, some machine setting featured lower bounds are provided. Computational experiment shows that the average-case relative error ratio of the heuristic algorithm that based on the classical LPT rule, two assignment procedures and a post-optimization procedure is less than 8%, which implies that it is promising for problem and suitable for real-world application.     

A simple and effective evolutionary algorithm for the vehicle routing problem

The vehicle routing problem (VRP) plays a central role in the optimization of distribution networks. Since some classical instances with 75 nodes resist the best exact solution methods, most researchers concentrate on metaheuristics for solving real-life problems. Contrary to the VRP with time windows, no genetic algorithm (GA) can compete with the powerful tabu search (TS) methods designed for the VRP. This paper bridges the gap by presenting a relatively simple but effective hybrid GA. In terms of average solution cost, this algorithm outperforms most published TS heuristics on the 14 classical Christofides instances and becomes the best solution method for the 20 large-scale instances generated by Golden et al.Scope and purposeThe framework of this research is the development of effective metaheuristics for hard combinatorial optimization problems met in vehicle routing. It is surprising to notice in the literature the absence of effective genetic algorithms (GA) for the vehicle routing problem (VRP, the main capacitated node routing problem), contrary to node routing problems with time windows or arc routing problems. Earlier attempts were based on chromosomes with trip delimiters and needed a repair procedure to get feasible children after each crossover. Such procedures are known to weaken the genetic transmission of information from parents to children. This paper proposes a GA without trip delimiters, hybridized with a local search procedure. At any time, a chromosome can be converted into an optimal VRP solution (subject to chromosome sequence), thanks to a special splitting procedure. This design choice avoids repair procedures and enables the use of classical crossovers like OX. The resulting algorithm is flexible, relatively simple, and very effective when applied to two sets of standard benchmark instances ranging from 50 to 483 customers.     

A solution approach based on Benders decomposition for the preventive maintenance scheduling problem of a stochastic large-scale energy system

This paper describes a Benders decomposition-based framework for solving the large scale energy management problem that was posed for the ROADEF 2010 challenge. The problem was taken from the power industry and entailed scheduling the outage dates for a set of nuclear power plants, which need to be regularly taken down for refueling and maintenance, in such a way that the expected cost of meeting the power demand in a number of potential scenarios is minimized. We show that the problem structure naturally lends itself to Benders decomposition; however, not all constraints can be included in the mixed integer programming model. We present a two phase approach that first uses Benders decomposition to solve the linear programming relaxation of a relaxed version of the problem. In the second phase, integer solutions are enumerated and a procedure is applied to make them satisfy constraints not included in the relaxed problem. To cope with the size of the formulations arising in our approach we describe efficient preprocessing techniques to reduce the problem size and show how aggregation can be applied to each of the subproblems. Computational results on the test instances show that the procedure competes well on small instances of the problem, but runs into difficulty on larger ones. Unlike heuristic approaches, however, this methodology can be used to provide lower bounds on solution quality.     

A branch-and-bound procedure for a single-machine earliness scheduling problem with two agents

This paper addresses a two-agent scheduling problem on a single machine where the objective is to minimize the total weighted earliness cost of all jobs, while keeping the earliness cost of one agent below or at a fixed level Q. A mixed-integer programming (MIP) model is first formulated to find the optimal solution which is useful for small-size problem instances. To solve medium- to large-size problem instances, a branch-and-bound algorithm incorporating with several dominance properties and a lower bound is then provided to derive the optimal solution. A simulated annealing heuristic algorithm incorporating with a heuristic procedure is developed to derive the near-optimal solutions for the problem. A computational experiment is also conducted to evaluate the performance of the proposed algorithms.     

Assessing a Metaheuristic for Large-Scale Commercial Districting

In this article, we present an empirical evaluation of a metaheuristic approach to a commercial districting problem. The problem consists of partitioning a given set of basic units into p districts in order to minimize a measure of territory dispersion. Additional constraints include territory connectivity and balancing with respect to several criteria. To obtain feasible solutions to this NP-hard problem, a reactive greedy randomized adaptive search metaheuristic procedure (GRASP) is used. Previous work addressed medium-scale instances. In this study, we report our computational experience when we addressed larger instances ressembling more closely the size of real-world instances. The empirical work includes full assessment of the algorithmic parameters and the local search phase, and a sensitivity analysis of the balance tolerance parameter in terms of solution quality and feasibility. The empirical evidence shows the effectiveness of the proposed approach and how this approach is significantly better than the method used by the industrial partner. The complexity of the planning constraints make the current practice method struggle to obtain feasible designs. Even for the larger cases, the proposed procedure successfuly solved instances with balance tolerance parameter values of as low as 3%, something impossible to achieve by the company’s current standards.     

The satisfiability problem in regular CNF-formulas

 In this paper we deal with the propositional satisfiability (SAT) problem for a kind of multiple-valued clausal forms known as regular CNF-formulas and extend some known results from classical logic to this kind of formulas. We present a Davis–Putnam-style satisfiability checking procedure for regular CNF-formulas equipped with suitable data structures and prove its completeness. Then, we describe a series of experiments for regular random 3-SAT instances. We observe that, for the regular 3-SAT problem with this procedure, there exists a threshold of the ratio of clauses to variables such that (i) the most computationally difficult instances tend to be found near the threshold, (ii) there is a sharp transition from satisfiable to unsatisfiable instances at the threshold and (iii) the value of the threshold increases as the number of truth values considered increases. Instances in the hard part provide benchmarks for the evaluation of regular satisfiability solvers.     

Simulating realistic set covering problems with known optimal solutions

This paper outlines a methodology to generate random Set Covering Problem (SCP) instances with known optimal solutions and correlated coefficients. Positive correlation between the objective function coefficients and the column sums of the SCP constraint matrix is known to affect the performance of SCP solution methods. Generating large SCP instances with known optimal solutions and realistic coefficient correlation provides a plethora of test problems with controllable problem characteristics, including correlation, and an ample opportunity to test the performance of SCP heuristics and algorithms without having to solve the problems to optimality. We describe the procedure for generating SCP instances and present the results of a computational demonstration conducted on SCP instances generated by our procedure. This computational demonstration shows that the heuristics’ relative errors increase as the correlation increases, that the likelihood of finding a non-optimal solution also increases with the level of correlation, and that the quality of the solutions found is affected by the number of constraints.     

An efficient deterministic heuristic for two-dimensional rectangular packing

This paper proposes a deterministic heuristic, a best fit algorithm (BFA), for solving the NP-hard two-dimensional rectangular packing problem to maximize the filling rate of a rectangular sheet. There are two stages in this new approach: the constructive stage and the tree search stage. The former aims to rapidly generate an initial solution by employing the concepts of action space and fit degree in evaluating different placements. The latter seeks to further improve the solution and searches for promising placements by a partial tree search procedure. We then compare BFA with other approaches in terms of solution quality and computing time. We carry out computational experiments on two sets of well-known benchmark instances, C21 proposed by Hopper and Turton, and N13 proposed by Burke et al. BFA gained an average filling rate of 100% for the C21 instances within short times, indicating that all the layouts obtained are optimal. To the best of our knowledge, this is the first time that optimal layouts on all the 21 instances were obtained by a deterministic algorithm. As for the N13 instances, to date, researchers have found optimal solutions to the first three instances, whereas BFA solved seven, including the first three, within a reasonable period. An additional work is to adapt BFA to solve a relevant problem, the constrained two-dimensional cutting (or packing) problem (CTDC). Though BFA is not for the CTDC in the original design such that some specific characteristics of CTDC are not considered, the adapted algorithm still performed well on 21 public CTDC instances.     

A hybrid method for the Probabilistic Maximal Covering Location–Allocation Problem

This paper presents a hybrid algorithm that combines a metaheuristic and an exact method to solve the Probabilistic Maximal Covering Location–Allocation Problem. A linear programming formulation for the problem presents variables that can be partitioned into location and allocation decisions. This model is solved to optimality for small- and medium-size instances. To tackle larger instances, a flexible adaptive large neighborhood search heuristic was developed to obtain location solutions, whereas the allocation subproblems are solved to optimality. An improvement procedure based on an integer programming method is also applied. Extensive computational experiments on benchmark instances from the literature confirm the efficiency of the proposed method. The exact approach found new best solutions for 19 instances, proving the optimality for 18 of them. The hybrid method performed consistently, finding the best known solutions for 94.5% of the instances and 17 new best solutions (15 of them optimal) for a larger dataset in one-third of the time of a state-of-the-art solver.     

Parallel Satisfiability Test with Synchronous Simulated Annealing on Distributed-Memory Multiprocessor

Solving the hard Satisfiability Problem is time consuming even for modest-sized problem instances. Solving the Random L-SAT Problem is especially difficult due to the ratio of clauses to variables. This report presents a practical approach to solving the Random L-SAT Problem on a large-scale distributed-memory multiprocessor. In particular, we use a parallel synchronous simulated annealing procedure, called Generalized Speculative Computation, which guarantees the same decision sequence as sequential simulated annealing. We have selected problem instances varying in size from 100-variable/425-clause to 5000-variable/21,250-clause. Experimental results on the AP1000 distributed-memory multiprocessor indicate that Generalized Speculative Computation of synchronous simulated annealing can satisfy 99.9% of the clauses while giving almost a 70-fold speedup on 500 processors.