(This article originally appeared in Management Science, January 1981, Volume 27, Number 1, pp. 1--18, published by The Institute of Management Sciences.) One of the most computationally useful ideas of the 1970s is the observation that many hard integer programming problems can be viewed as...

Recently there has been considerable interest in the average-case performance of heuristics. This paper pursues that interest, where it concerns sequencing and packing problems. In particular, we survey the methods that have been used to obtain formal probabilistic analyses of heuristics for...

A new approximate algorithm for multidimensional zero-one knapsack problems with all positive coefficients is presented. The procedure is controlled by three parameters which affect the tradeoff between solution quality and computation time and whose values are set by the users. For 48 test...

This paper addresses a nonpreemptive single machine scheduling problem where all jobs have a common due date and have zero ready time. The scheduling objective is to minimize mean squared deviation (MSD) of job completion times about the due date. This nonregular measure of performance is...

In this survey paper we discuss the development of the simple assembly line balancing problem (SALBP); modifications and generalizations over time; present alternate 0-1 programming formulations and a general integer programming formulation of the problem; discuss other well-known problems...

In this paper we present a heuristic method, based on Lagrangian relaxation, for multilevel lot-sizing when there is a single bottleneck facility. A series of Lagrangian relaxations (one for each item in the product structure) is imbedded in a branch and bound procedure. The objective is to find...

The most commonly used penalty in branch and bound approaches to integer programming is the Driebeek--Tomlin penalty. It has been used successfully in solving fixed cost linear programs by Kennington and Unger and by Barr, Glover and Klingman. It is well known that the Driebeek--Tomlin penalty...

The branch and bound principle has long been established as an effective computational tool for solving mixed integer linear programming problems. This paper investigates the computational feasibility of branch and bound methods in solving convex nonlinear integer programming problems. The...