A five facet frame for the design of heuristics —A rejoinder

An argument was put forward by Stainton and Papoulias for an additional category of heuristics to those proposed by Müller-Merbach, which the authors called ‘relational’. In response to the subsequent suggestion by Müller-Merbach of a five facet frame for the design of heuristics, this paper sets out to expand upon and clarify the characteristics of the relational approach, as defined by the authors.     

A computational study of several heuristics for the DRPP

The problem of designing a route of minimum length for a postman that starts and finishes at his office and has to deliver the mail along a set of streets in a city is known as the Rural Postman Problem. When the postman has to obey the directions of the streets, we have the directed version of this problem. Finding an exact solution, in the general case, is intractably difficult. Hence, we have implemented three heuristic algorithms for approximately solving this problem and a procedure for obtaining a lower bound to the optimal length. Also, we present numerical experimentations based on a collection of random instances with up to 30 connected components, 240 vertices and 801 arcs. A lower bound for the optimal DRPP value is obtained by using cutting plane techniques, producing an optimal solution in 21 out of 60 instances. The main purpose of this work is to compare these three algorithms. We also give guidelines concerning the performance of the algorithms depending on the characteristics of the problem to solve.     

Partitioning heuristics for two geometric maximization problems

Given n points randomly selected from a uniform distribution on the unit square, we describe linear-time partitioning heuristics which will construct a matching or a tour of these points. We show that the heuristics closely approximate the optimum values as n → ∞. Hence we show that the asymptotic values of the maximum matching and tour are about 0·3826n and twice this value respectively.     

Clustering heuristics for set covering

We introduce a new class of set covering heuristics, based on clustering techniques. In its simplest form, a heuristic in this class may be described as follows: firstly, partition the column set into clusters formed by columns that are close to each other (e.g. in the Hamming distance sense). Then select a best (e.g. a cheapest) column in each cluster; if the selected columns form a coverC, then extract fromC a prime cover and stop; else, modify the partition (e.g. by increasing the number of clusters) and repeat. We describe two implementations of this general algorithmic strategy, relying on the Single Linkage and the Leader clustering algorithm, respectively. Numerical experiments performed on 72 randomly generated test problems with 200 or 400 rows and 1000 columns indicate that the above two heuristics often yield cheaper covers than other well-known (greedy-type) heuristics when the cost-range is not too narrow.The present work is based on R.K. Kwatera's dissertation, written under the supervision of B. Simeone. A preliminary version was presented at EURO VIII, Paris, July 1988.     

A class of heuristics for the constrained forest problem

The constrained forest problem seeks a minimum-weight spanning forest in an undirected edge-weighted graph such that each tree spans at least a specified number of vertices. We present a structured class of greedy heuristics for this NP-hard problem, and identify the best heuristic.     

Two new heuristics for the location set covering problem

Summary In this paper we present two new greedy-type heuristics for solving the location set covering problem. We compare our new pair of algorithms with the pair GH1 and GH2 [Vasko and Wilson (1986)] and show that they perform better for a selected set of test problems.     

Multiple-objective heuristics for scheduling unrelated parallel machines

This research proposes two heuristics and a Genetic Algorithm (GA) to find non-dominated solutions to multiple-objective unrelated parallel machine scheduling problems. Three criteria are of interest, namely: makespan, total weighted completion time, and total weighted tardiness. Each heuristic seeks to simultaneously minimize a pair of these criteria; the GA seeks to simultaneously minimize all three. The computational results show that the proposed heuristics are computationally efficient and provide solutions of reasonable quality. The proposed GA outperforms other algorithms in terms of the number of non-dominated solutions and the quality of its solutions.     

Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem

Bin-oriented heuristics for one-dimensional bin-packing problem construct solutions by packing one bin at a time. Several such heuristics consider two or more subsets for each bin and pack the one with the largest total weight. These heuristics sometimes generate poor solutions, due to a tendency to use many small items early in the process. To address this problem, we propose a method of controlling the average weight of items packed by bin-oriented heuristics. Constructive heuristics and an improvement heuristic based on this approach are introduced. Additionally, reduction methods for bin-oriented heuristics are presented. The results of an extensive computational study show that: (1) controlling average weight significantly improves solutions and reduces computation time of bin-oriented heuristics; (2) reduction methods improve solutions and processing times of some bin-oriented heuristics; and (3) the new improvement heuristic outperforms all other known complex heuristics, in terms of both average solution quality and computation time.     

Learning heuristics for basic block instruction scheduling

Instruction scheduling is an important step for improving the performance of object code produced by a compiler. A fundamental problem that arises in instruction scheduling is to find a minimum length schedule for a basic block—a straight-line sequence of code with a single entry point and a single exit point—subject to precedence, latency, and resource constraints. Solving the problem exactly is known to be difficult, and most compilers use a greedy list scheduling algorithm coupled with a heuristic. The heuristic is usually hand-crafted, a potentially time-consuming process. In contrast, we present a study on automatically learning good heuristics using techniques from machine learning. In our study, a recently proposed optimal basic block scheduler was used to generate the machine learning training data. A decision tree learning algorithm was then used to induce a simple heuristic from the training data. The automatically constructed decision tree heuristic was compared against a popular critical-path heuristic on the SPEC 2000 benchmarks. On this benchmark suite, the decision tree heuristic reduced the number of basic blocks that were not optimally scheduled by up to 55% compared to the critical-path heuristic, and gave improved performance guarantees in terms of the worst-case factor from optimality.     

Analysis of heuristics for finding a maximum weight planar subgraph

The problem of identifying a planar subgraph of maximum total weight in an edge-weighted graph has application to the layout of facilities in a production system and elsewhere in industrial engineering.This problem is NP-hard, and so we confine our attention to polynomial-time heuristics. In this paper we analyse the performance of some heuristics for this problem.     

Hybrid heuristics for a short sea inventory routing problem

We consider a short sea fuel oil distribution problem where an oil company is responsible for the routing and scheduling of ships between ports such that the demand for various fuel oil products is satisfied during the planning horizon. The inventory management has to be considered at the demand side only, and the consumption rates are given and assumed to be constant within the planning horizon. The objective is to determine distribution policies that minimize the routing and operating costs, while the inventory levels are maintained within their limits. We propose an arc-load flow formulation for the problem which is tightened with valid inequalities. In order to obtain good feasible solutions for planning horizons of several months, we compare different hybridization strategies. Computational results are reported for real small-size instances.     

Worst-case analysis of two travelling salesman heuristics

In this paper we analyze the worst-case performance of some heuristics for the symmetric travelling salesman problem. We show that the worst-case ratios of tour length produced by the savings and greedy heuristics to that of a minimum tour are bounded by [log₂n]+1 and 0.5([log₂n]+1) respectively, where n is the number of cities.     

Column generation extensions of set covering greedy heuristics

Large-scale set covering problems are often approached by constructive greedy heuristics, and many selection criteria for such heuristics have been considered. These criteria are typically based on measures of the cost of setting an additional variable to one in relation to the number of yet unfulfilled constraints that it will satisfy. We show how such greedy selections can be performed on column-oriented set covering models, by using a fractional optimization formulation and solving sequences of ordinary column generation problems for the application at hand.     

对中国期货机构投资者锚定启发式偏差的实证研究

本运用行为金融学的理论，通过对期货投资情绪变化和历史投资收益率进行回归分析，检验了中国期货经纪公司这类机构投资是否存在锚定启发式偏差。经过分析，得出了中国期货机构投资具有锚定启发式偏差的结论。     

Analysis of heuristics for the design of tree networks

We analyze the tour partitioning heuristics for the Capacitated Minimum Spanning Tree problem. Lower bounds for the worst-case performance ratios of these heuristics are obtained by using worst-case examples. We also generalize the heuristics to the multi-center case with the same worst-case bounds.The work of the first author was supported by a Dean Summer Research Grant from Owen Graduate School of Management, Vanderbilt University.Work done in part in the Department of Industrial Engineering and Operations Research at Columbia University.The work of the last two authors was supported in part by ONR contract N00014-90-J-1649, NSF contract DDM-8922712 and the Center for Telecommunications Research under NSF contract CDR 84-21402.     

A travel-time model for a person-onboard order picking system

The design of an order picking system in a distribution center depends on several decisions, where a key decision is determining the optimal storage system configuration (the number, length, and height of the storage aisles). To make this decision, a throughput model that considers vertical, as well as horizontal, travel is needed. In this paper we extend prior research that considers horizontal travel for a given number and length of the storage aisles so that we are also able to consider the height of the aisles as well. Such a model will provide a more accurate estimate of the throughput of an order picker and it will also permit an examination of the tradeoff between the length and height of the aisles. The analytical model we develop to estimate throughput is based on probability models and order statistics results assuming random storage. It is intended for person-onboard order picking systems and we consider both Tchebychev and rectilinear travel. We illustrate the use of our travel-time model by incorporating it into a simple, cost-based optimization model to recommend the height of a one-pallet-deep storage system.     

Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems

In this paper, we present a random iterative graph based hyper-heuristic to produce a collection of heuristic sequences to construct solutions of different quality. These heuristic sequences can be seen as dynamic hybridisations of different graph colouring heuristics that construct solutions step by step. Based on these sequences, we statistically analyse the way in which graph colouring heuristics are automatically hybridised. This, to our knowledge, represents a new direction in hyper-heuristic research. It is observed that spending the search effort on hybridising Largest Weighted Degree with Saturation Degree at the early stage of solution construction tends to generate high quality solutions. Based on these observations, an iterative hybrid approach is developed to adaptively hybridise these two graph colouring heuristics at different stages of solution construction. The overall aim here is to automate the heuristic design process, which draws upon an emerging research theme on developing computer methods to design and adapt heuristics automatically. Experimental results on benchmark exam timetabling and graph colouring problems demonstrate the effectiveness and generality of this adaptive hybrid approach compared with previous methods on automatically generating and adapting heuristics. Indeed, we also show that the approach is competitive with the state of the art human produced methods.     

Efficient implementation of heuristics for the continuous network design problem

In this paper, we present an efficient implementation of heuristic procedures for solving the continuous network design problem where network users behave according to Wardrop's first principle of traffic equilibrium. Numerical results involving a standard benchmark problem are given. Also, it is shown that the cost mapping arising in the Iterative-Optimization-Assignment algorithm is integrable if and only if the volume-delay function is of either the BPR or some logarithmic form.Research supported by the National Sciences and Engineering Research Council of Canada (Grant A5789) and the Academic Research Program of the Department of National Defense (Grant FUHBP).     

The convergence of estimators based on heuristics: theory and application to a GARCH model

Econometric theory describes estimators and their properties, e.g., the convergence of maximum likelihood estimators. However, it is ignored that often the estimators cannot be computed using standard tools, e.g., due to multiple local optima. Then, optimization heuristics might be helpful. The additional random component of heuristics might be analyzed together with the econometric model. A formal framework is proposed for the analysis of the joint convergence of estimator and stochastic optimization algorithm. In an application to a GARCH model, actual rates of convergence are estimated by simulation. The overall quality of the estimates improves compared to conventional approaches. We are indebted to Manfred Gilli and an anonymous referee of this journal for valuable comments on a preliminary draft of this paper. Financial support from the EU Commission through MRTN-CT-2006-034270 COMISEF is gratefully acknowledged.