Search

The surveillance search problem is a generalization of the detection search problem studied by Brown and Stone, among others. In the surveillance version of the problem, the search terminates only if the time and location of a detection satisfy certain problem specific conditions; the objective is to maximize the expected value of a payoff received during and at the end of the search. For instance, we may wish to maximize the probability of finding the target in a specified subset of the state space or at a specified time. Consequently, we might detect the target several times before the search terminates. A search strategy, i.e., an allocation of the available search effort, must account for this possibility. In this paper, we formulate the surveillance search problem for applications in which the target moves according to a (not necessarily time-homogeneous) Markov process. We then derive a set of necessary conditions for the optimality of a search strategy, end develop algorithms, based on the algorithm of Brown for the detection search problem, to find strategies that satisfy these necessary conditions for problems in which the search effort is infinitely divisible. [ABSTRACT FROM AUTHOR]

Consider the problem of determining a schedule of capacity expansions for m producing regions and a schedule of shipments from the regions to the n markets so as to meet the market demands over a T-period planning horizon at minimum discounted capacity expansion and shipment costs. The capacity expansion costs are assumed to be in the form of a fixed charge plus a cost proportional to the size of the expansion and the shipment costs are assumed to be proportional to the amounts involved. The heuristic algorithm of this paper improves on feasible solutions by the exchange of capacities between pairs of regions. The algorithm imbeds a branch and bound procedure to determine the optimal amounts for the pair-wise exchange of capacities and uses as a subroutine the corresponding algorithm for linear capacity expansion costs developed in an earlier paper. Computational results for both real and randomly generated problems show that the heuristic algorithm is computationally efficient and yields close to optimum solutions. [ABSTRACT FROM AUTHOR]

This paper considers the problem in which a single decision maker must choose an element from a known nonempty choice set Y of multi-attributed elements when his preferences are uncertain. The preferences are uncertain in the sense that they are not explicitly available. The decision-maker's preferences are assumed to take the form of a binary relation on Y. We present an algorithm that requires the identification of preferences during the search process. The convergence of the adopted algorithm to a best element in Y relative to whatever preferences obtain is proved under the assumption that the identification of preferences is costless. We show that the sufficient conditions for convergence of this algorithm are weaker than the sufficient conditions for convergence of the interactive algorithm for the multiple criteria problem developed by Geoffrion, Dyer, and Feinberg. [ABSTRACT FROM AUTHOR]

This paper considers convergence of a method-of-centers algorithm for solving nonlinear programming problems. An upper bound is derived for the number of steps needed to solve each subproblem, defined by the algorithm, when the method of steepest ascent is employed. Also, an upper bound is found for the total number of subproblem steps needed to solve all of the subproblems required to find a feasible point having an objective value with a prescribed maximum deviation from the optimal value. [ABSTRACT FROM AUTHOR]

This paper considers multiple choice programming problems in which the elements of the activity matrix can be normally distributed random variables or random vectors. The truncated block enumeration method of multiple choice programming is described and used in the development of an algorithm to solve problems of this type. Deterministic inequalities computed from the means and variances are employed by the block pivoting algorithm to assure fast convergence to a (sub)optimal solution. The solution will satisfy each constraint with the required marginal probabilities, but a lower bound of the joint probabilities is also computed. As an option, problems can be solved when the lower bound of the joint probability that all the constraints are satisfied is specified alone. [ABSTRACT FROM AUTHOR]

This paper presents a new implicit enumeration algorithm for solving the pure integer linear programming problem. The theory of equivalent integer programming problems is first used to reformulate the problem. A technique originally used with particular success in the bound-and-scan algorithm to deal with only a subset of the variables is extended to all of the variables in the restructured problem. In addition to the resulting basic enumeration scheme, the algorithm includes a scanning procedure and a method for identifying constraints that become redundant during the course of the algorithm. Computational experience on standard test problems is reported. [ABSTRACT FROM AUTHOR]

This paper analyzes a heuristic for the knapsack problem that recursively determines a solution by making a variable with smallest marginal unit cost as large as possible. Recursive necessary and sufficient conditions for the optimality of such 'greedy' solutions and a 'good' algorithm for verifying these conditions are given. Maximum absolute error for nonoptimal 'greedy' solutions is also examined. [ABSTRACT FROM AUTHOR]

This paper treats the problem of locating a given number of interrelated physical facilities in a single- or multi-story building as an optimization model such that the weighted sum of the distances along orthogonal directions is minimized, and describes a constructive heuristic algorithm for the one-dimensional model. This linear placement algorithm is then extended to higher dimensions for placing uniform-size equipment modules at homogeneous fixed locations. The algorithm accommodates lower-bound constraints for the linear case efficiently and produces near-optimal solutions. Its significance, as demonstrated by comparison with some existing heuristic procedures, is that it has the capability of handling efficiently problems with large numbers of equal-size facilities whose solutions are computationally intractable using the present optimum-producing methods. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for the global maximization of a convex function subject to linear inequality constraints. It is computationally finite and is designed to converge rapidly on problems in which there are few local optima or the global optimum is significantly better than most of the other local optima. [ABSTRACT FROM AUTHOR]

This paper gives counterexamples to: (1) Ritter's algorithm for the global maximization of a quadratic subject to linear inequality constraints, and (2) Tui's algorithm for the global minimization of a concave function subject to linear inequality constraints. [ABSTRACT FROM AUTHOR]

Approaches like finite differences with common random numbers, infinitesimal perturbation analysis, and the likelihood ratio method have drawn a great deal of attention recently as ways of estimating the gradient of a performance measure with respect to continuous parameters in a dynamic stochastic system. In this paper, we study the use of such estimators in stochastic approximation algorithms, to perform so-called "single-run optimizations" of steady-state systems. Under mild conditions, for an objective function that involves the mean system time in a G//G/1 queue, we prove that many variants of these algorithms converge to the minimizer. In most cases, however, the simulation length must be increased from iteration to iteration; otherwise the algorithm may converge to the wrong value. One exception is a particular implementation of infinitesimal perturbation analysis, for which the single-run optimization converges to the optimum even with a fixed (and small) number of ends of service per iteration. As a by-product of our convergence proofs, we obtain some properties of the derivative estimators that could be of independent interest. Our analysis exploits the regenerative structure of the system, but our derivative estimation and optimization algorithms do not always take advantage of that regenerative structure. In a companion paper, we report numerical experiments with an M/M/1 queue, which illustrate the basic convergence properties and possible pitfalls of the various techniques. [ABSTRACT FROM AUTHOR]

The bandwidth packing (BWP) problem is a combinatorially difficult problem arising in the area of telecommunications. The problem consists of assigning calls to paths in a capacitated graph, such that capacities are not violated and the total profit is maximized. In this paper we discuss the development of a tabu search (TS) method for the BWP problem. The method makes use of an efficient implementation of the k-shortest path algorithm, that allows the identification of a controlled set of feasible paths for each call. A tabu search is then performed to find the best path assignment for each call. The TS method developed here incorporates a number of features that have proved useful for obtaining optimal and near optimal solutions to difficult combinatorial problems. We establish the effectiveness of our approach by comparing its performance in speed and solution quality to other specialized heuristics and to a standard optimization package applied to a 0-1 integer programming formulation of the problem. [ABSTRACT FROM AUTHOR]

It is known that minimum cost flow problems can be solved by successive augmentations along shortest paths. In this paper the issues of implementing shortest path algorithms in this context are examined. Of particular interest is the dynamic topology that the flow networks exhibit. We develop a network generator capable of emulating such topology. Strategies for exploiting the special structures in such networks are discussed. A set of 9000 test problems is offered, from which a particular strategy/algorithm combination is shown to consistently produce superior results when compared to the other combinations. [ABSTRACT FROM AUTHOR]

This paper considers the problem of scheduling n jobs, each having a processing time, a due date and a weight, on a single machine to minimize the weighted number of late jobs. An O(n log n) algorithm is given for solving the linear programming problem obtained by relaxing the integrality constraints in a zero-one programming formulation of the problem. This linear programming lower bound is used in a reduction algorithm that eliminates jobs from the problem. Also, a branch and bound algorithm that uses the linear programming lower bound is proposed. Computational results with branch and bound algorithms that use this and other lower bounds and with a dynamic programming algorithm for problems with up to 1000 jobs are given. [ABSTRACT FROM AUTHOR]

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 makespan scheduling and one-dimensional bin packing. In so doing, we present many of thc key results in these research areas. [ABSTRACT FROM AUTHOR]

A tree network is a collection of trees rooted at a common central node. Several types of network design problems can be viewed as requiring the formation of a spanning tree network of minimum length, subject to a bound on the sum of "weights" on the nodes of any component tree. Such problems are NP-complete, and experience has shown that only small examples can be solved to optimality. This paper describes an efficient heuristic algorithm based on partitioning of a traveling salesman tour. When all the nodes have a unit weight and the bound is K, the heuristic finds a solution whose cost is at most 3 - 2/K times the minimum; in the general case the error bound is 4. [ABSTRACT FROM AUTHOR]

The Linear Programming Problem is by far the most widely used optimization model. Its impact on economic and government modeling is immense. The Simplex Method for solving the Linear Programming (LP) Problem, due to George Dantzig, has been an extremely efficient computational tool for almost four decades. The method has been the subject of intense investigations for many years, but some major aspects of its behavior are not fully understood yet. The purpose of this paper is to survey the body of knowledge on the efficiency of the Simplex Method, from both practical and theoretical points of view. Adopting the number of iterations (pivot steps) as the yardstick for efficiency, we survey four aspects of the issue: 1. Reports on practical experience of the method's performance on real-life LP problems. 2. Results on controlled (Monte-Carlo) experiments solving LP problems which were randomly generated according to some predetermined distributions. 3. Complexity results, including theoretical analyses on both upper and lower bounds for the performance of the Simplex as well as non-Simplex algorithms for LP. 4. Results of recent theoretical studies using probabilistic analysis to derive bounds on the average behavior of the Simplex Method. We discuss the consequences and limitations of the various studies. Special emphasis is given to open questions. [ABSTRACT FROM AUTHOR]

Planning languages and spreadsheet systems are very popular, and the number of new users is increasing dramatically. On larger computers, IFPS, System W, and FCS-EPS are among the most widely used systems; while on personal computers, Multiplan and 1-2-3 enjoy great popularity. Currently, such languages operate mainly as simulators, evaluating specific cases. In this paper, we propose methodology which is useful in designing an optimization capability for these languages. This capability permits the user to designate certain model variables as decisions, constraints, and the objective. Upper and lower limits on the decisions and constraints are also specified. The optimization interface then diagnoses the problem as linear or nonlinear, computes first partial derivatives needed by the solution algorithms, and invokes the appropriate "solver." Information regarding the optimal solution is obtained using the reporting and graphics capabilities of the planning language. Sensitivity analysis and "what if" features permit easy modification of the problem for further analysis. These ideas have been implemented in a system called IFPS/OPTIMUM, which provides an optimization capability to users of the widely-used planning language IFPS. A simple IFPS/OPTIMUM example is presented, and two applications are described. Endowing planning languages with an optimization capability promises to increase dramatically the use of optimization. There are already hundreds of thousands of users of planning languages and spreadsheet systems, most of whom are unfamiliar with optimization models or methods. Making optimization a natural extension of systems they understand and find very useful holds great promise, both for applications and for teaching optimization concepts. [ABSTRACT FROM AUTHOR]

Multiobjective mathematical programming has been one of the fastest growing areas of OR/MS during the last 15 years. This paper presents: 1. some reasons for the rapidly growing increase in interest in multiobjective mathematical programming. 2. a discussion of the advantages and disadvantages of the three general approaches (articulation of the decision maker's preference structure over the multiple objectives prior to, during, or after the optimization) towards multiobjective mathematical programming, 3. a nontechnical overview of many of the specific solution techniques for multiobjective mathematical programming, and 4. a discussion of important areas for further research. The overview concentrates on those techniques which require an articulation of the decision maker's preference structure either during or after the optimization, since these are the areas where most of the recent research has been conducted. It differs from previous overviews in that, in addition to the timing of the elicited preference information, the techniques are also classified according to the types of decision variables contained in the model (i.e., only continuous decision variables, or at least some discrete decision variables). In addition, the types of preference information (e.g., a ranking of outcomes) required of the various techniques are also discussed. [ABSTRACT FROM AUTHOR]

This paper describes a practical algorithm for large-scale mean-variance portfolio optimization. The emphasis is on developing an efficient computational approach applicable to the broad range of portfolio models employed by the investment community. What distinguishes these from the "usual" quadratic program is (i) the form of the covariance matrix arising from the use of factor and scenario models of return, and (ii) the inclusion of transactions limits and costs. A third aspect is the question of whether the problem should be solved parametrically in the risk-reward trade off parameter, &lamda;, or separately for several discrete values of &lamda;. We show how the parametric algorithm can be made extremely efficient by "sparsifying" the covariance matrix with the introduction of a few additional variables and constraints, and by treating the transaction cost schedule as an essentially nonlinear nondifferentiable function. Then we show how these two seemingly unrelated approaches can be combined to yield good approximate solutions when minimum trading size restrictions ("buy or sell at least a certain amount, or not at all") are added. In combination, these approaches make possible the parametric solution of problems on a scale not heretofore possible on computers where CPU time and storage are the constraining factors. [ABSTRACT FROM AUTHOR]

In a recent paper, Mamer and Smith (1982) presented a formulation for determining the optimal kit of parts and tools for on-site equipment repairs under a job completion criterion. The optimal kit minimizes the sum of expected broken job costs plus the annual inventory holding cost for those parts stocked. A broken job occurs whenever a repair cannot be completed because one or more of its required parts are not included in the field repair kit. Assuming equal penalties for all broken jobs, an algorithm developed by Eisner and Severance (1976) in a different context can be used to determine a set of optimal policies and a range on the penalty cost for which each policy is optimal. The ranges cover all penalty costs from 0 to ∞. This is significant for the repair kit problem since the actual penalty cost of broken jobs may be difficult to determine exactly. [ABSTRACT FROM AUTHOR]

Given n items, each having a weight w[SUBi], and a container of capacity W, the Subset-Sum Problem (SSP) is to select a subset of the items whose total weight is closest to, without exceeding, W. The paper presents a mixed approach (depth first search-dynamic programming) to the exact solution of the problem. An extensive computational experience is presented, comparing the proposed algorithm with that of Ahrens-Finke, as well as with the Balas-Zemel algorithm for large problems. Both "easy" and "hard" problems with values of n up to 10,000 are considered. [ABSTRACT FROM AUTHOR]

This paper presents a constraint logic programming model for the traveling salesman problem with time windows which yields an exact branch-and-bound optimization algorithm without any restrictive assumption on the time windows. Unlike dynamic programming approaches whose performance relies heavily on the degree of discretization applied to the data, our algorithm does not suffer from such space-complexity issues. The data-driven mechanism at its core more fully exploits pruning rules developed in operations research by using them not only a priori but also dynamically during the search. Computational results are reported and comparisons are made with both exact and heuristic algorithms. On Solomon's well-known test bed, our algorithm is instrumental in achieving new best solutions for some of the problems in set RC2 and strengthens the presumption of optimality for the best known solutions to the problems in set C2. [ABSTRACT FROM AUTHOR]

This paper presents a theory of traffic equilibrium which involves responsive signal control policies; in this theory drivers' route choices and the control policy's choice of green times are treated in a symmetrical manner. The central theme of the paper is the iterative optimization assignment algorithm. This algorithm may be considered as a means of calculating equilibria which are consistent with a given responsive control policy. But it may also be regarded as a highly idealized model of the day to day dynamics of drivers' route choices when a responsive signal setting policy is employed; on "day" 1 the signals are held fixed and drivers settle down to an equilibrium flow pattern, on "day 2" the flow pattern is held fixed and the signals are updated according to the control policy for the fixed flow pattern, on "day" 3 the signals are held fixed and drivers settle down to an equilibrium flow pattern.... We state natural but strong conditions on the responsive control policy which guarantee that this algorithm is bound to converge to a convex set of (flow, control) pairs such that (i) the flow is a user equilibrium and (ii) the control parameters satisfy the responsive control policy; and we give a proof of convergence under these conditions--we do not seek to minimize total travel cost. Our conditions involve the delay or cost formula used; with the BPR cost formula, modified in a natural way to allow for green times, the traditional policy of choosing control parameters which minimize delay for the observed traffic pattern does satisfy these conditions in full. However, with Webster's delay formula traditional control policies are a long way... [ABSTRACT FROM AUTHOR]

The paper describes a model for the optimal management of periodic deliveries of a given commodity. The goal is to schedule the deliveries according to feasible combinations of delivery days and to determine the scheduling and routing policies of the vehicles in order to minimize over the planning horizon the maximum number of vehicles simultaneously employed, i.e., the fleet size. Heuristic algorithms are proposed and computational experience is reported. [ABSTRACT FROM AUTHOR]

In this paper we develop a new heuristic for the hierarchical network design problem. The heuristic is based upon Lagrangian relaxation of a reformulation of the problem. In addition, we develop a branch and bound algorithm to identify the optimal solution for the 5% of the test problems for which the new heuristic failed to do so. This algorithm proved to be very efficient due to the tight bounds generated by the heuristic. [ABSTRACT FROM AUTHOR]

Modeling of transportation systems must invariably balance behavioral richness and computational tractability. In this paper, we develop a transportation equilibrium model and an algorithm for the simultaneous prediction of trip generation, trip distribution, modal split, and trip assignment on large-scale networks. The model achieves a practical compromise between behavioral and computational aspects of modeling the problem. It is formulated as an equivalent convex optimization problem, yet it is behaviorally richer than other models that can be cast as equivalent convex programs. Although the model is not as behaviorally rich as the most general equilibrium models, it has computational advantages. The applications reported in this paper of the model to real systems, i.e., the intercity transport network of Egypt and the urban transportation network of Austin, Texas, illustrate the computational attractiveness of the approach. These results indicate that equivalent optimization formulations are not as restrictive as previously thought, and hence, the equivalent convex programming approach for modeling and predicting equilibrium on transportation systems remains a viable and fruitful avenue for future consideration. [ABSTRACT FROM AUTHOR]

For applications of realistic size, both the discrete and continuous versions of the equilibrium network design problem are too computationally intensive to be solved exactly with the algorithms proposed to date. This intractibility owes to Braess' paradox which makes it necessary to constrain the flow pattern to be a noncooperative Nash or user equilibrium. This paper suggests a new heuristic for finding an approximate solution to the continuous equilibrium network design problem. Numerical tests are reported which indicate that, for networks with significant congestion, the heuristic is markedly more efficient than the Hooke-Jeeves algorithm which has been employed previously. The efficiency of the heuristic results from decomposition of the original problem into a set of interacting optimization subproblems. This decomposition is such that, at each iteration of the algorithm, only one user equilibrium needs to be calculated in order to update the improvement variables of all arcs of the network. This contrasts sharply with the Hooke-Jeeves algorithm which can require that a new user equilibrium be calculated each time an individual arc improvement variable is updated. For applications of realistic size, both the discrete and continuous versions of the equilibrium network design problem are too computationally intensive to be solved exactly with the algorithms proposed to date. This intractibility owes to Braess' paradox which makes it necessary to constrain the flow pattern to be a noncooperative Nash or user equilibrium. This paper suggests a new heuristic for finding an approximate solution to the continuous equilibrium network design problem. Numerical tests are reported which indicate that, for networks with significant congestion, the heuristic is markedly more efficient than the Hooke-Jeeves algorithm which has been employed previously. The efficiency of the heuristic results from decomposition of the original problem into a set of interacting optimization subproblems. This decomposition is such that, at each iteration of the algorithm, only one user equilibrium needs to be calculated in order to update the improvement variables of all arcs of the network. This contrasts sharply with the Hooke-Jeeves algorithm which can require that a new user equilibrium be calculated each time an individual arc improvement variable is updated. [ABSTRACT FROM AUTHOR]

This paper focuses on the problem of finding the optimal travel path of a single service unit to nonemergency destinations. Such destinations result from events other than service calls, e.g., repositioning or relocation operations, returning from the scene of the service call to the "home location," preventive patrol, etc. The analysis is performed on a network model of the urban environment. The time period of interest begins when the service unit starts its travel to a nonemergency destination and ends when the new call for service arrives. The paper contains two models each of which is suitable for a different application. For the two models two different algorithms are presented; one of which is a dynamic programming. These algorithms take into considerations the probabilistic nature of the demand for service. Illustrative examples are also included. [ABSTRACT FROM AUTHOR]

In two previous papers Préopa (1986a, b) gave algorithms to approximate probabilities that at least r and exactly r out of n events occur (1 ⩽ r ⩽ n). Primal and dual linear programming problems were formulated and solved by dual type algorithms. The purpose of the present paper is to give closed forms for the basis inverse and the corresponding dual vector in case of an arbitrary basis, furthermore to give closed forms for the lower and upper bounds, approximating the probability in question, in case of a dual feasible basis. In the case when the probability that at least one out of n events occurs is approximated, it is shown that the absolute values of the components of any dual vector form a monotonically decreasing sequence. The paper improves the method of inclusion-exclusion, proves new probability inequalities and proves the sharpness of some known inequalities. [ABSTRACT FROM AUTHOR]

Consider a set function v(·) defined on all subsets of a finite set N. This paper presents a class of set function maximization problems of the form Max(v(S)|S ⊆ N) that are solved optimally by the greedy algorithm. In particular, it is shown that there exists a nested sequence of subsets S[sup *, sub l] ... S[sup *, sub m] that increase to the optimal policy and S[sup *, sub k] maximizes v(S) over all subsets of cardinality k. The class is characterized by conditions on the set function v(·) and related to the notion of submodularity. These results are then applied to two order-preserving machine scheduling problems. The greedy algorithm is shown to be optimal for these problems thereby providing a new algorithm different from previous approaches based on dynamic programming. [ABSTRACT FROM AUTHOR]

The conflict that naturally arises in a hierarchical system can often be modeled as a multistage optimization problem. This paper considers the sequential uncooperative problem in which two decision makers wish to maximize their own objective functions over a feasible region defined by interactive strategy sets. The resultant problem is known as the bilevel program. Such programs are inherently nonconvex and resistant to standard nonlinear programming solution techniques such as piecewise linearization and convex underestimating envelopes. Alternatively, a grid search algorithm is offered which exhibits the desirable property of monotonicity. The algorithm is based on two sets of necessary conditions previously developed and combined here to provide an operational check for stationarity and local optimality. Potential solutions are obtained from a parameterized master program whose feasible region approximates that of the original problem. As the one-dimensional parameter is varied over the unit interval and the master problem solved, a nondecreasing sequence of lower bounds to the first decision maker's objective function is produced. If the solution to the original problem is stable under small perturbations, the sequence is shown to converge to the global optimum. A discussion of the computational requirements follows the presentation of the algorithm. [ABSTRACT FROM AUTHOR]

A lower bound on the total error in an accounting population is required, in conjunction with the point estimate of the total error amount and the upper bound, when adjusting an account to determine the amount of the adjustment. This paper extends the multinomial methodology for obtaining an upper bound on the total overstatement (or understatement) error in an accounting population to the determination of a lower bound on the total overstatement (or understatement) error. The methodology for obtaining a lower multinomial bound differs in several important respects from that for obtaining an upper bound. The proposed lower bound may be computed for up to 25 errors in the sample and provides tighter limits than the widely used Stringer bound. [ABSTRACT FROM AUTHOR]

This paper develops a method for interactive multiple objective linear programming assuming an unknown pseudo concave utility function satisfying certain general properties. The method is an extension of our earlier method published in this journal [18]. Various technical problems present in predecessor versions have been resolved. In addition to presenting the supporting theory and algorithm, we discuss certain options in implementation and summarize our practical experience with several versions of the method. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for determining the optimal allocation to demand points when the distribution system is a capacitated arborescence of N arcs and the cost (return) functions are convex (concave). It is proved that the algorithm generates an optimal solution by solving at most N(N + 1)/2 single-constraint subproblems. If the cost functions allow the Lagrange multiplier for the subproblems to be evaluated in polynomial time, then this is a polynomial algorithm. The analysis is motivated by the problem of allocating spare capacity in the loop plant portion of telephone networks. [ABSTRACT FROM AUTHOR]

Since procedures for producing optimal solutions to a quadratic assignment problem are computationally infeasible for any but small problems, heuristic techniques for producing approximate solutions must be employed for the solution of real practical problems. This paper presents the results of experimentation that demonstrates that a solution procedure which couples a constructive initial placement technique with simple and inexpensive improvement procedures produces good solutions with very reasonable computation requirements. The results indicate that such an approach would make the solution of large-scale quadratic assignment problems feasible. [ABSTRACT FROM AUTHOR]

In many computer applications messages of various lengths need to be stored in some storage device. In this paper we examine the problem in which a fixed number of record lengths can be used to store messages. Whenever a message arrives, it is stored in the smallest possible record which is at least as large as the message. If a message cannot be stored in any single record, it is divided into segments and stored in several records of the same length. Each record is accompanied by a header which contains overhead information. Furthermore, in some applications records of the same length are stored in larger units, called blocks. If so, some space may be wasted at the end of a block. The objective is to find the optimal record lengths so that the expected total space used to store a message is minimized. A dynamic programming algorithm that finds the optimal record lengths is developed for a general message length distribution. Numerical examples are discussed. [ABSTRACT FROM AUTHOR]

This paper addresses the time management problem confronted by sales representatives. The sales representative planning his itinerary must decide the best way to ration time among the accounts comprising his territory. The time management problem is formulated as an integer program whereby each admissible call frequency for each account is represented by a zero-one decision variable. A branch-and-bound integer programming algorithm for this problem is presented. The algorithm is unique in that two integer programming formulations of the problem are used simultaneously in the search procedure and an approximation-cum-relaxation is evaluated at each branch in the search. Computational testing of the algorithm shows that it can solve many realistic time management problems optimally in fractions of a second. [ABSTRACT FROM AUTHOR]

This paper presents and tests an effective optimization algorithm for clustering homogeneous data. The algorithm iteratively employs a subgradient method for determining lower bounds and a simple search procedure for determining upper bounds. The overall objective is to assign n objects to m mutually exclusive "clusters" such that the sum of the distances from each object to a designated cluster median is minimum. The model represents a special case of the uncapacitated facility location and m-median problems. The technique has proven efficient for examples with n ≤ 200 (i.e., the number of 0-1 variables ≤ 40,006); computational experiences with 10 real-world clustering applications are provided. A comparison with a hierarchical agglomerative heuristic, the minimum squared error method, is included. It is shown that the optimization algorithm is an effective solution technique for the homogeneous clustering problem, and also a good method for providing tight lower bounds for evaluating the quality of solutions generated by other procedures. [ABSTRACT FROM AUTHOR]

This paper describes a long-range planning procedure for administrators in private universities. The procedure operates by generating a sequence of alternative future configurations of the university that satisfy several financial constraints and by helping an administrator to assess his preferences on them. A mathematical programming algorithm is used to structure the interactive identification/search procedure. It incorporates the strategy of restriction and linear programming methods to generate new configurations, and it relies upon the interactively assessed preferences of the administrator to guide the search process rather than a standard objective function. [ABSTRACT FROM AUTHOR]

This paper considers a multi-contract bidding situation in which the contracts are interrelated because of limited productive facilities and because of budgetary constraints. A dynamic programming model and computational algorithm are presented which derive a bidding strategy which maximizes total expected return from all contracts subject to the constraints. The computational algorithm is efficient in terms of storage capacity required and computation time. [ABSTRACT FROM AUTHOR]

A dynamic programming algorithm is presented to locate m variable facilities in relation to n existing facilities situated on one route. Each of the n existing facilities has a requirement flow which must be supplied by the variable facilities. The algorithm does the allocation simultaneously with the location. Computational experience indicates that relatively large problems may be solved optimally. [ABSTRACT FROM AUTHOR]

A multi-stage linear program is defined with linking variables that connect consecutive stages. Optimality conditions for the composite problem are partitioned into local and linking conditions. When the Dantzig-Wolfe decomposition scheme is applied with the first stage as the master, the subproblem is also a MLP with one less stage. The same decomposition is then applied to the subproblem, giving rise to a nested decomposition scheme, in which each stage acts as a master for the following stage and a subproblem for the preceding. Optimizing a single stage problem results in satisfying the "local" optimality conditions. A very general rule is given for selecting the next subproblem to optimize, and finite convergence to a solution satisfying all linking conditions is demonstrated. Procedures for extracting the optimal primal solution at the end of the main algorithm and for initialization are given. Particular rules for selecting the next subproblem and for generating additional proposal vectors are discussed. Finally, it is shown how a variety of problems may be restructured as multi-stage linear programs to which this algorithm may be applied, and some computational experience is reported. [ABSTRACT FROM AUTHOR]

This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric travelling-salesman problem. The procedure is based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems. The procedure produces optimum solutions for all problems tested, 'classical' problems appearing in the literature, as well as randomly generated test problems, up to 110 cities. Run times grow approximately as n² in absolute terms, a typical 100-city problem requires less than 25 seconds for one case (GE63S), end about three minutes to obtain the optimum with above 95 per cent confidence. [ABSTRACT FROM AUTHOR]

This paper connects some of the recent developments in concave and integer programming. In particular, it points out parallels between the work of HOANG TUI and R. D. YOUNG. From these methods, a finite algorithm for solving a special class of 0–1 integer programs is developed. Our approach contrasts with an earlier extension of Tui's method due to M. RAGHAVACHARI and general ‘intersection’ or ‘convexity’ cut approaches. [ABSTRACT FROM AUTHOR]

MILLER and WAGNER [Opns. Res. 13, 930–945 (1965)] define joint chance-constrained programming by specifying a set of consists that are joint probability measures of the extent to which constraint violations are permitted. For the special case of a random right-hand-side vector whose elements are independent random variables, they show that an equivalent deterministic concave program exists. The purpose of this paper is to generalize this result to a class of nonlinear chance-constrained programming models with joint constraints. [ABSTRACT FROM AUTHOR]

This paper presents a realistic chemical-process optimization problem in detail, and notes the fact of its equivalence to the general nonlinear programming problem. The eight equality constraints that arise are handled by algebraic substitution, and the resulting four-variable problem is solved by a modified form of the Davidon-Fletcher-Powell algorithm. Details of the method are presented (including a FORTRAN computer program), and results of two typical cases are summarized. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm that finds globally optimum flows in networks having nonlinear costs of arc flows, the flows being finite-dimensional vectors such as multicommodity flows. The algorithm is an extension of an idea of ALLSOP [Trans. Sci. 2, 1–13 (1968)] for minimizing total delays in a traffic network; it is also intimately related to results in nonserial dynamic programming. [ABSTRACT FROM AUTHOR]

This paper studies multistage mathematical programs with an arbitrary transient phase followed by an infinite stationary phase with linear constraints and objective. It presents conditions under which a derived linear program will determine an optimal solution to the infinite problem. These conditions are general and may be validated by simple algebraic tests (perhaps solving a finite linear program). No topological restrictions are placed on the model. [ABSTRACT FROM AUTHOR]

In deriving the well known cuts for cutting-plane methods in 0, 1 integer programming, the integer points outside the 0, 1 space can limit the parallel movement of the hyperplane of the cut toward the solution set. Furthermore it is unnecessarily restrictive to limit the movement of this hyperplane to parallel translations. This paper removes these two limitations in order to derive stronger cuts and reduce the total number of cuts required. Thus, it describes a method based on a special case of the knapsack function that replaces each cut or original constraint by a new inequality whose hyperplane passes through as many integer points in 0, 1 space as possible. [ABSTRACT FROM AUTHOR]