Determination of lockbox collection points via simulated annealing

This research presents a heuristic to solve the lockbox location problem via a search-based technique known as simulated annealing. In the past, more traditional mathematical programming techniques have been used to address this problem, but with limited success due to its combinatorial nature. Because simulated annealing is a search-based technique, an optimal solution is not guaranteed, but past research has demonstrated that search-based heuristics can provide reasonable solutions without the difficulties associated with the more traditional formulations. In this paper, the simulated annealing methodology is used to solve a large lockbox location problem at several differing levels of cost. The results compare favourably to solutions obtained from a K-means clustering heuristic.     

An effective and simple heuristic for the set covering problem

This paper investigates the development of an effective heuristic to solve the set covering problem (SCP) by applying the meta-heuristic Meta-RaPS (Meta-heuristic for Randomized Priority Search). In Meta-RaPS, a feasible solution is generated by introducing random factors into a construction method. Then the feasible solutions can be improved by an improvement heuristic. In addition to applying the basic Meta-RaPS, the heuristic developed herein integrates the elements of randomizing the selection of priority rules, penalizing the worst columns when the searching space is highly condensed, and defining the core problem to speedup the algorithm. This heuristic has been tested on 80 SCP instances from the OR-Library. The sizes of the problems are up to 1000 rows × 10,000 columns for non-unicost SCP, and 28,160 rows × 11,264 columns for the unicost SCP. This heuristic is only one of two known SCP heuristics to find all optimal/best known solutions for those non-unicost instances. In addition, this heuristic is the best for unicost problems among the heuristics in terms of solution quality. Furthermore, evolving from a simple greedy heuristic, it is simple and easy to code. This heuristic enriches the options of practitioners in the optimization area.     

A multi-heuristic approach for solving the pre-marshalling problem

Minimizing the number of reshuffling operations at maritime container terminals incorporates the pre-marshalling problem (PMP) as an important problem. Based on an analysis of existing solution approaches we develop new heuristics utilizing specific properties of problem instances of the PMP. We show that the heuristic performance is highly dependent on these properties. We introduce a new method that exploits a greedy heuristic of four stages, where for each of these stages several different heuristics may be applied. Instead of using randomization to improve the performance of the heuristic, we repetitively generate a number of solutions by using a combination of different heuristics for each stage. In doing so, only a small number of solutions is generated for which we intend that they do not have undesirable properties, contrary to the case when simple randomization is used. Our experiments show that such a deterministic algorithm significantly outperforms the original nondeterministic method. The improvement is twofold, both in the quality of found solutions, and in the computational effort.     

Pareto optimality and a class of set covering heuristics

The set covering problem has many diverse applications to problems arising in crew scheduling, facility location and other business areas. Since the problem is known to be hard to solve optimally, a number of approximate (heuristic) approaches have been designed for it. These approaches (with one exception) divide into two main groups, greedy heuristics and dual saturation heuristics. We use the concept of a Pareto optimal dual solution to show that an arbitrary dual saturation heuristic has the same worst-case performance guarantee as the two best known heuristics of that type. Moreover, this poor performance level is always attainable by those two heuristics.     

Greedy Differencing Edge-Contraction heuristic for the Max-Cut problem

The Max-Cut problem is a classical NP-hard problem where the objective is to partition the nodes of an edge-weighted graph in a way that maximizes the sum of edges between the parts. We present a greedy heuristic for solving Max-Cut that combines an Edge-Contraction heuristic with the Differencing Method. We compare the heuristic’s performance to other greedy heuristics using a large and diverse set of problem instances.     

Designing greedy algorithms for the flow-shop problem by means of Empirically Adjusted Greedy Heuristics (EAGH)

This paper introduces Empirically Adjusted Greedy Heuristics (EAGH), a procedure for designing greedy algorithms for a given combinatorial optimization problem and illustrates the way in which EAGH works with an application to minimize the makespan in the permutation flow-shop problem. The basic idea behind EAGH is that a greedy heuristic can be seen as a member of an infinite set of heuristics, this set being defined by a function that depends on several parameters. Each set of values of the parameters corresponds to a specific greedy heuristic. Then, the best element of the set, for a training set of instances of the problem, is found by applying a non-linear optimization algorithm to a function that measures the quality of the obtained solutions to the instances of the training set, and which depends on the parameters that characterize each specific algorithm. EAGH allows improving known heuristics or finding good new ones.     

A Two Stage Search Heuristic for Scheduling Payments in Projects

When the Net Present Value (NPV) of a project is used as a measure of its financial performance, effective management of cash flows over the duration of the project is critical for improved profitability. Progress payments are a major component of project cash flows. In many project environments, the contractor can negotiate payment terms. Payments are typically tied to completion of project activities and therefore have significant impact on the schedule of activities and the timing of the payments. In this paper, we consider the problem of simultaneously determining the amount, timing and location of progress payments in projects to maximize NPV. Due to the combinatorial nature of the problem, heuristics are a practical approach to solving the problem. We propose a two-stage heuristic where simulated annealing is used in the first stage to determine a set of payments. In the second stage, activities are rescheduled to improve project NPV. We compare the performance of this general purpose heuristic with other problem-dependent heuristics from the literature. Our results indicate that the simulated annealing heuristic significantly outperforms the parameter-based heuristics. Although rescheduling in the second stage improves NPV, increases are relatively small in magnitude. While the specific parameters settings suggested by the simulated annealing heuristic in this study may have limited generalizability at this time due to the narrow range of problems tested, our analysis suggests that a pure simulated annealing approach is a very attractive alternative for obtaining good heuristic solutions to the complex problem of scheduling payments in projects.     

A comparison of algorithm RS with algorithm OPTSOL70

In a very recent paper (Almiñana and Pastor (1997)) we proposed a new lagrangian surrogate heuristic, called RS, for solving the location (or unicost) set covering problem. In that paper we show that RS is more accurate than the pair of greedy type heuristics FMC/CMA and that RS outperforms the surrogate heuristic SH. Here we are going to compare algorithms RS with the best designed hybrid algorithm for the location set covering problem, known as OPTSOL70.     

Greedy heuristics for the diameter-constrained minimum spanning tree problem

The diameter-constrained minimum spanning tree problem is an NP-hard combinatorial optimization problem that seeks a minimum cost spanning tree with a limit D imposed upon the length of any path in the tree. We begin by presenting four constructive greedy heuristics and, secondly, we present some second-order heuristics, performing some improvements on feasible solutions, hopefully leading to better objective function values. We present a heuristic with an edge exchange mechanism, another that transforms a feasible spanning tree solution into a feasible diameter-constrained spanning tree solution, and finally another with a repetitive mechanism. Computational results show that repetitive heuristics can improve considerably over the results of the greedy constructive heuristics, but using a huge amount of computation time. To obtain computational results, we use instances of the problem corresponding to complete graphs with a number of nodes between 20 and 60 and with the value of D varying between 4 and 9.     

On the Significance of the Initial Solution in Travelling Salesman Heuristics

The quality requirements set by edge exchange heuristics on their initial solutions are evaluated in connection with the travelling salesman problem. The performance of the heuristics is measured using the expected value of the best solution achievable in a certain computing time. The computational results show that the use of initial solutions generated by applying a construction heuristic, instead of random initial solutions, typically improves the performance of edge exchange heuristics. The improvement, however, is dependent on the edge exchange heuristic to be used, the properties of the problem, and the computing time available.     

Using Lagrangian dual information to generate degree constrained spanning trees

In this paper, a Lagrangian-based heuristic is proposed for the degree constrained minimum spanning tree problem. The heuristic uses Lagrangian relaxation information to guide the construction of feasible solutions to the problem. The scheme operates, within a Lagrangian relaxation framework, with calls to a greedy construction heuristic, followed by a heuristic improvement procedure. A look ahead infeasibility prevention mechanism, introduced into the greedy heuristic, allowed us to solve instances of the problem where some of the vertices are restricted to having degrees 1 or 2. Furthermore, in order to cut down on CPU time, a restricted version of the original problem is formulated and used to generate feasible solutions. Extensive computational experiments were conducted and indicate that the proposed heuristic is competitive with the best heuristics and metaheuristics in the literature.     

Sensitivity analysis of a greedy heuristic for knapsack problems

In this paper, we carry out parametric analysis as well as a tolerance limit based sensitivity analysis of a greedy heuristic for two knapsack problems—the 0–1 knapsack problem and the subset sum problem. We carry out the parametric analysis based on all problem parameters. In the tolerance limit based approach, we use a definition of the sensitivity analysis problem that is polynomial for polynomial heuristics. One of the interesting and counterintuitive results described in this paper is that the tolerance limits obtained from the heuristic sensitivity analysis cannot be used as bounds for the tolerance limits of the sensitivity analysis of optimal solutions in most cases.     

An Almost Optimal Heuristic for Preemptive C max Scheduling of Dependent Tasks on Parallel Identical Machines

We consider the problem of scheduling preemptable, dependent tasks on parallel, identical machines to minimize the makespan. The computational complexity of this problem remains open if the number of machines is fixed and larger than 2. The aim of this paper is to compare two heuristic algorithms on a basis of a computational experiment. The solutions generated by the heuristics are compared with optimal solutions obtained by a branch-and-bound algorithm. Computational results show that the heuristic based on node ordering finds optimal schedules for 99.9% of instances with the maximum relative deviation from optimum of 4.8%.     

Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique Problem

In this work, the NP-hard maximum clique problem on graphs is considered. Starting from basic greedy heuristics, modifications and improvements are proposed and combined in a two-phase heuristic procedure. In the first phase an improved greedy procedure is applied starting from each node of the graph; on the basis of the results of this phase a reduced subset of nodes is selected and an adaptive greedy algorithm is repeatedly started to build cliques around such nodes. In each restart the selection of nodes is biased by the maximal clique generated in the previous execution. Computational results are reported on the DIMACS benchmarks suite. Remarkably, the two-phase procedure successfully solves the difficult Brockington-Culberson instances, and is generally competitive with state-of-the-art much more complex heuristics.     

Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem

The unconstrained binary quadratic programming problem (BQP) is known to be NP-hard and has many practical applications. This paper presents a simulated annealing (SA)-based heuristic for the BQP. The new SA heuristic for the BQP is based on a simple (1-opt) local search heuristic and designed with a simple cooling schedule, but the multiple annealing processes are adopted. To show practical performances of the SA, we test on publicly available benchmark instances of large size ranging from 500 to 2500 variables and compare them with other heuristics such as multi-start local search, the previous SA, tabu search, and genetic algorithm incorporating the 1-opt local search. Computational results indicate that our SA leads to high-quality solutions with short times and is more effective than the competitors particularly for the largest benchmark set. Furthermore, the values of new best-known solutions found by the SA for several large instances are also reported.     

An Application of Tabu Search Heuristic for the Maximum Edge-Weighted Subgraph Problem

The purpose of this article is to describe an efficient search heuristic for the Maximum Edge-weighted Subgraph (MEwS) problem. This problem requires to find a subgraph such that the sum of the weights associated with the edges of the subgraph is maximized subject to a cardinality constraint. In this study a tabu search heuristic for the MEwS problem is proposed. Different algorithms to obtain an initial solution are presented. One neighborhood search strategy is also proposed. Preliminary computational results are reported for randomly generated test problems of MEwS problem with different densities and sizes. For most of test problems, the tabu search heuristic found good solutions. In addition, for large size test problems, the tabu search outperformed the local search heuristic appearing in the literature.     

A Comparison of Heuristics for the Discrete Cost Multicommodity Network Optimization Problem

In this paper, approximate solutions algorithms for discrete cost multicommodity network optimization problems are presented and compared. Firstly, extensions of classical greedy heuristics, based on link-rerouting and flow-rerouting heuristics, are presented in details. Secondly, a new approximate solution algorithm, which basically consists of a heuristic implementation of the exact Benders-type cutting plane generation method, is proposed. All these algorithms are extensively compared on randomly generated graphs up to 50 nodes and 90 links. It clearly appears that this new Benders-type approach is very promising since it produces the best heuristic solutions.     

Iterated greedy for the maximum diversity problem

The problem of choosing a subset of elements with maximum diversity from a given set is known as the maximum diversity problem. Many algorithms and methods have been proposed for this hard combinatorial problem, including several highly sophisticated procedures. By contrast, in this paper we present a simple iterated greedy metaheuristic that generates a sequence of solutions by iterating over a greedy construction heuristic using destruction and construction phases. Extensive computational experiments reveal that the proposed algorithm is highly effective as compared to the best-so-far metaheuristics for the problem under consideration.     

A cooperative hyper-heuristic search framework

In this paper, we aim to investigate the role of cooperation between low level heuristics within a hyper-heuristic framework. Since different low level heuristics have different strengths and weaknesses, we believe that cooperation can allow the strengths of one low level heuristic to compensate for the weaknesses of another. We propose an agent-based cooperative hyper-heuristic framework composed of a population of heuristic agents and a cooperative hyper-heuristic agent. The heuristic agents perform a local search through the same solution space starting from the same or different initial solution, and using different low level heuristics. The heuristic agents cooperate synchronously or asynchronously through the cooperative hyper-heuristic agent by exchanging the solutions of the low level heuristics. The cooperative hyper-heuristic agent makes use of a pool of the solutions of the low level heuristics for the overall selection of the low level heuristics and the exchange of solutions. Computational experiments carried out on a set of permutation flow shop benchmark instances illustrated the superior performance of the cooperative hyper-heuristic framework over sequential hyper-heuristics. Also, the comparative study of synchronous and asynchronous cooperative hyper-heuristics showed that asynchronous cooperative hyper-heuristics outperformed the synchronous ones.