A branch and bound algorithm for solving the multiple-choice knapsack problem

The multiple-choice knapsack problem is a binary knapsack problem with the addition of disjoint multiple-choice constraints. We describe a branch and bound algorithm based on embedding Glover and Klingman's method for the associated linear program within a depth-first search procedure. A heuristic is used to find a starting dual feasible solution to the associated linear program and a ‘pegging’ test is employed to reduce the size of the problem for the enumeration phase. Computational experience and comparisons with the code of Nauss and an algorithm of Armstrong et al. for the same problem are reported.     

Dynamic demand lot-sizing rules for incremental quantity discounts

Numerous studies have developed and compared lot-sizing procedures for finite-horizon dynamic demand, material requirements planning (MRP), environments when either no purchase discounts exist or for the case of all-units quantity discounts. This paper examines lot-sizing rules when product price schedules follow incremental quantity discounts. The optimal (non-discount) procedure and some traditional heuristic procedures are modified to incorporate incremental quantity discounts. We further modify two heuristics with a ‘look-ahead enhancement’ that performs very well under experimentation. Numerical tests revealed the overall best-performing heuristic in this study to be a modified ‘least-unit cost’ method with a look-ahead enhancement. That procedure produced an average cost penalty vs optimal of 0.26%.     

Heuristic Methods for the Data Placement Problem

Databases require a management system which is capable of retrieving and storing information as efficiently as possible. The data placement problem is concerned with obtaining an optimal assignment of data tuples onto secondary storage devices. Such tuples have complicated interrelationships which make it difficult to find an exact solution to our problem in a realistic time.We therefore consider heuristic methods—three of which are discussed and compared — the ‘greedy’ graph-collapsing method, the probabilistic hill-climbing method of simulated annealing and a third ‘greedy’ heuristic, the random improvement method, which is a local search heuristic. Overall, the best performance is obtained from the graph-collapsing method for the less complicated situations, but for larger-scale problems with complex interrelationships between tuples the simulated annealing and random improvement algorithms give better results.     

Formal optimization of some reduced linear programming problems

It is often possible (and profitable) to reduce or ‘Presolve’ linear programs. In particular, there are frequently constraints which force many of the variables to be at bound. Unfortunately, the solution found by the simplex method for such reduced models is not usually ‘formally’ optimal, in the sense that nonoptimal dual values may be present when the original problem is restored. Furthermore, the restored (full) problem is now totally degenerate, and may require many iterations to achieved formal optimality. We describe an efficient ‘Postsolve’ procedure for attaining the formal optimum solution, and give computational results.     

A dual ascent procedure for the set partitioning problem

The set partitioning problem is a fundamental model for many important real-life transportation problems, including airline crew and bus driver scheduling and vehicle routing.In this paper we propose a new dual ascent heuristic and an exact method for the set partitioning problem. The dual ascent heuristic finds an effective dual solution of the linear relaxation of the set partitioning problem and it is faster than traditional simplex based methods. Moreover, we show that the lower bound achieved dominates the one achieved by the classic Lagrangean relaxation of the set partitioning constraints. We describe a simple exact method that uses the dual solution to define a sequence of reduced set partitioning problems that are solved by a general purpose integer programming solver. Our computational results indicate that the new bounding procedure is fast and produces very good dual solutions. Moreover, the exact method proposed is easy to implement and it is competitive with the best branch and cut algorithms published in the literature so far.     

A Cutting Stock and Scheduling Problem in the Copper Industry

This case study was carried out for Thomas Bolton Ltd, a copper component manufacturer. The focus was on the first major production operation that is carried out in the foundry. This operation consists of three processes — melting scrap metal, casting it as ‘logs’ and cutting logs into ‘billets’. The timely production of the billets is essential as these feed a bottleneck process. The objective of the study was to investigate alternative methods of generating a production plan for the foundry that minimized costs whilst meeting the demand for billets at the bottleneck. The production plan was required to include a daily production schedule and a list of the cutting patterns to use when cutting the logs into billets. Thus, both the scheduling and cutting stock problems were addressed. A two-stage solution procedure was proposed. Alternative heuristic methods were investigated at the first stage and an optimal solution using Integer Programming (IP) was proposed for the second stage. It is shown that current performance could be improved using all of the heuristics considered at the first stage, but that using an IP-based heuristic method gives the best results.     

Planning the supply of rewards with cooperative promotion considerations in coalition loyalty programmes management

Coalition loyalty programmes (CLPs) are owned and operated as for-profit enterprises. We consider the ordering decisions of rewards that arise in this context, under a general setting in which not only is the demand for rewards uncertain, but also the CLP firm offers bonus points, a very common cooperative promotion mechanism used in loyalty programmes. The rewards are acquired either at a wholesale ‘discounted’ cost or at a wholesale ‘non-discounted’ cost by the CLP firm from its multiple commercial partners and supplied to customers seeking to redeem their accumulated ‘reward points’, subject to commercial partners’ capacities for offering rewards, the firm’s overall budget for purchasing rewards, and its control policy on points liability. We formulate the problem as a stochastic linear programme with recourse and solve it using a sampling-based heuristic solution procedure previously discussed in the literature. We report on the managerial applicability of our model in dealing with the redemption budget spending resulting from changes in demand variability, changes in the redemption budget, and the control of liability levels within a reasonable range.     

A Greedy Look-ahead Heuristic for Combinatorial Optimization: An Application to Vehicle Scheduling with Time Windows

This paper describes a greedy heuristic for a class of combinatorial optimization problems; a central feature of the method being a look-ahead capability. The power of the heuristic is demonstrated through experimentation using a large, real-life vehicle scheduling problem with tight time-window constraints. Incorporation of the look-ahead feature gave an improvement in performance that was at least as great as, and in addition to, that which had been obtained through use of the well-known ‘savings’ method. Based upon the experimental results, some guidelines are proposed for the application of the heuristic to other problems. One of the conclusions is that designers of heuristics should give greater consideration to the inclusion of a look-ahead element in their algorithms.     

A five facets frame for the design of heuristics

The author suggested to distinguish between the ‘engineering approach’ and the ‘mathematical approach’ in connection with the design of heuristics. Stainton and Papoulias extended the scope by suggesting the ‘relational approach’. Based upon this extension, a five facets frame is presented here which is suggested to precede and accompany the ‘technical’ design of the heuristic. The facets are: coverage by participation, experience by doing, abstraction by structuring, extension by comparison, exploration by creativity.     

The Feeder-bus Network-design Problem

The potential for improving the cost-effectiveness of public transport operations by designing better integrated feeder-bus/rail rapid transit systems has been widely recognized. This paper defines the feeder-bus network-design problem (FBNDP) as that of designing a feeder-bus network to access an existing rail system. The FBNDP is considered under two different demand patterns, many-to-one (M-to-1) and many-to-many (M-to-M). We present a mathematical programming model for the M-to-1 FBNDP, and show that it can be generalized to the M-to-M FBNDP. The FBNDP is a large and difficult vehicle-routeing-type problem with an additional decision variable—operating frequency. A heuristic model is presented, which generalizes the ‘savings approach’ to incorporate operating frequency. The computational analysis shows that the proposed heuristic provides reasonable feeder-bus networks and consistent responses to ‘what if’ questions. A comparison indicates that the proposed heuristic provides solutions that are superior to manually designed networks. The advantages of this heuristic are particularly significant under variable demand.     

Solving Examination Timetabling Problems through Adaption of Heuristic Orderings

Heuristic ordering based methods, very similar to those used for graph colouring problems, have long been applied successfully to the examination timetabling problem. Despite the success of these methods on real life problems, even with limited computing resources, the approach has the fundamental flaw that it is only as effective as the heuristic that is used. We present a method that adapts to suit a particular problem instance “on the fly.” This method provides an alternative to existing forms of ‘backtracking,’ which are often required to cope with the possible unsuitability of a heuristic. We present a range of experiments on benchmark problems to test and evaluate the approach. In comparison to other published approaches to solving this problem, the adaptive method is more general, significantly quicker and easier to implement and produces results that are at least comparable (if not better) than the current state of the art. We also demonstrate the level of generality of this approach by starting it with the inverse of a known good heuristic, a null ordering and random orderings, showing that the adaptive method can transform a bad heuristic ordering into a good one.     

Efficiency measure,modelling and estimation in combined array designs

In off‐line quality control, the settings that minimize the variance of a quality characteristic are unknown and must be determined based on an estimated dual response model of mean and variance. The present paper proposes a direct measure of the efficiency of any given design‐estimation procedure for variance minimization. This not only facilitates the comparison of different design‐estimation procedures, but may also provide a guideline for choosing a better solution when the estimated dual response model suggests multiple solutions. Motivated by the analysis of an industrial experiment on spray painting, the present paper also applies a class of link functions to model process variances in off‐line quality control. For model fitting, a parametric distribution is employed in updating the variance estimates used in an iteratively weighted least squares procedure for mean estimation. In analysing combined array experiments, Engel and Huele (Technometrics, 1996; 39:365) used log‐link to model process variances and considered an iteratively weighted least squares leading to the pseudo‐likelihood estimates of variances as discussed in Carroll and Ruppert (Transformation and Weighting in Regression, Chapman & Hall: New York). Their method is a special case of the approach considered in this paper. It is seen for the spray paint data that the log‐link may not be satisfactory and the class of link functions considered here improves substantially the fit to process variances. This conclusion is reached with a suggested method of comparing ‘empirical variances’ with the ‘theoretical variances’ based on the assumed model. Copyright © 2003 John Wiley & Sons, Ltd.     

Using mathematical programming heuristics in a multicriteria network flow context

In this paper, we propose a local search procedure to test the robustness of a specific ‘satisfying point’ neighbourhood. It consists of the following steps: (1) build an indifference area around the satisfying point in the criteria space by using thresholds (this takes into account the possible uncertainty, vagueness and/or inaccuracy of data); (2) find some points in the satisfying point neighbourhood and the corresponding solutions in the decision variables space; (3) test the quality of these solutions from the point of view of user preference. The indifference area is defined by adding constraints to the network model. This approach, which allows us to verify the adequacy of the model, has been applied to a set of multicriteria network flow problems. A heuristic method, based on Lagrangian duality and subgradient techniques, exploits the combinatorial structure of network flow problems in order to find certain feasible points.     

Scheduling and lot sizing models for the single-vendor multi-buyer problem under consignment stock partnership

We consider a centralized supply chain composed of a single vendor serving multiple buyers and operating under consignment stock arrangement. Solving the general problem is hard as it requires finding optimal delivery schedule to the buyers and optimal production lot sizes. We first provide a nonlinear mixed integer programming formulation for the general scheduling and lot sizing problem. We show that the problem is NP-hard in general. We reformulate the problem under the assumption of ‘zero-switch rule’. We also provide a simple sequence independent lower bound to the solution of the general model. We then propose a heuristic procedure to generate a near-optimal delivery schedule. We assess the cost performance of that heuristic by conducting sensitivity analysis on the key model parameters. The results show that the proposed heuristic promises substantial supply-chain cost savings that increase as the number of buyers increases.     

Heuristic and stochastic methods in optimization

The shifting bottleneck (SB) heuristic is among the most successful approximation methods for solving the job shop problem. It is essentially a machine based decomposition procedure where a series of one machine sequencing problems (OMSPs) are solved. However, such a procedure has been reported to be highly ineffective for the flow shop problems. In particular, we show that for the 2-machine flow shop problem, the SB heuristic will deliver the optimal solution in only a small number of instances. We examine the reason behind the failure of the machine based decomposition method for the flow shop. An optimal machine based decomposition procedure is formulated for the 2-machine flow shop, the time complexity of which is worse than that of the celebrated Johnson’s rule. The contribution of the present study lies in showing that the same machine based decomposition procedures which are so successful in solving complex job shops can also be suitably modified to optimally solve the simpler flow shops.     

Construction of efficient experimental designs under multiple resource constraints

The aim of this paper is twofold. First, we introduce ‘resource constraints’ as a general concept that covers many practical restrictions on experimental design. Second, to compute optimal or near‐optimal exact designs of experiments under multiple resource constraints, we propose a tabu search heuristic related to the Detmax procedure. To illustrate the scope and performance of the proposed method, we chose the criterion of D‐optimality and computed efficient designs for (i) a block model with limits on the numbers of blocks and on the replications of treatments, (ii) a quadratic regression model with simultaneous marginal and cost constraints, and (iii) a non‐linear regression model with simultaneous direct and cost constraints. As we show, the proposed method generates similar or better results compared with algorithms specialized for computing optimal designs under less general constraints. Copyright © 2015 John Wiley & Sons, Ltd.     

Relation between vehicle routing problems: an insertion heuristic for the vehicle routing problem with simultaneous delivery and pick-up applied to the vehicle routing problem with backhauls

Recently, an increasing number of papers on vehicle routing problems with backhauling has been published. Different types of backhauling problems are discussed. Two of them—the vehicle routing problem with backhauls and so-called ‘mixed loads’ (VRPBM) and the vehicle routing problem with simultaneous delivery and pick-up (VRPSDP)—are closely related. In this paper, we discuss that relationship. Our findings are that previously published results for VRPSDP instances obtained by using a heuristic suggested for the VRPBM do not take into account specific properties of the VRPSDP. As a result of the analysis of the relation between both problem types the possibility of solving the VRPBM by applying an insertion heuristic based on the concept of ‘residual capacities’ originally designed for the VRPSDP is investigated. Numerical results indicate that, for certain instances, this approach is more favourable than the application of a heuristic suggested for the VRPBM in the literature.     

A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints

In this paper we propose a dual ascent heuristic for solving the linear relaxation of the generalized set partitioning problem with convexity constraints, which often models the master problem of a column generation approach. The generalized set partitioning problem contains at the same time set covering, set packing and set partitioning constraints. The proposed dual ascent heuristic is based on a reformulation and it uses Lagrangian relaxation and subgradient method. It is inspired by the dual ascent procedure already proposed in literature, but it is able to deal with right hand side greater than one, together with under and over coverage. To prove its validity, it has been applied to the minimum sum coloring problem, the multi-activity tour scheduling problem, and some newly generated instances. The reported computational results show the effectiveness of the proposed method.     

Tactical design of rail freight networks. Part II: Local search methods with statistical analysis

This paper deals with the statistical study of the local search methods which we used in Part I of this work. In that part, a tactical planning model of the rail freight transportation was defined as a network design model. Different local search methods have been used to solve it: Simulated Annealing, Tabu Search and a ‘Descent’ method. The solution and method convergence depends on the initial feasible solution and the convexity of the feasible region, so the comparison among them will be made with the help of statistical theory. Assuming the hypothesis that the distribution of local minima can be represented by the Weibull distribution, it is possible to obtain an approach to the global minimum and a confidence interval of this. The global minimum estimation has been used to compare the heuristic methods and the parameters for a given heuristic, and to obtain a stopping criterion.