Search

In this paper, we study the quadratic assignment problem with a rank-one cost matrix (QAP-R1). Four integer-programming formulations are introduced of which three are assumed to have partial integer data. Unlike the standard quadratic assignment problem, some of our formulations can solve reasonably large instances of QAP-R1 with impressive running times and are faster than some metaheuristics. Pairwise relative strength of the LP relaxations of these formulations are also analyzed from theoretical and experimental points of view. Finally, we present a new metaheuristic algorithm to solve QAP-R1 along with its computational analysis. Our study offers the first systematic experimental analysis of integer-programming models and heuristics for QAP-R1. The benchmark instances with various characteristics generated for our study are made available to the public for future research work. Some new polynomially solvable special cases are also introduced. Summary of Contribution: This paper aims to advance our knowledge and ability in solving an important special case of the quadratic assignment problem. It shows how to exploit inherent properties of an optimization problem to achieve computational advantages, a strategy that was followed by researchers in model building and algorithm developments for decades. Our computational results attest to this time-tested general philosophy. The paper presents the first systematic computational study of the rank one quadratic assignment problem, along with new mathematical programming models and complexity analysis. We believe the theoretical and computational results of this paper will inspire further research on the topic and will be of significant value to practitioners using rank one quadratic assignment models.

The quadratic assignment problem (QAP) is a combinatorial optimization problem that arises in many real-world applications, such as equipment allocation in industry. The QAP is NP-hard and, in practice, one of the hardest combinatorial optimization problems to solve to optimality. Exact solutions of QAP are typically obtained by the branch-and-bound method. This method, however, potentially requires a high computational effort, and the use of good lower bounds is essential to prune the search tree. Branch-and-bound algorithms that use the dual-ascent procedure based on the level-2 reformulation linearization technique (RLT2) belong to the state of the art on exactly solving QAP. In this work, we propose a parallel implementation of that branch-and-bound algorithm. Our approach uses the Auction Algorithm of Bertsekas and Castañon to solve the linear assignment problems of RLT2, which allows us to take advantage of the massive parallel environment of graphics processing units to speed up the lower bound computation and implement some memory optimization techniques to address large-size problems. We report experimental results that show significant execution time reductions compared to previous works and allow us to provide, for the first time, exact solutions for two instances of QAP: tai35b and tai40b.

We consider a generalization of the classical quadratic assignment problem, where material flows between facilities are uncertain, and only upper and lower bounds are known for each flow. The objective is to find a minmax regret solution. We present an exact Benders decomposition algorithm based on two developed mathematical programming formulations and on the developed linearizations of master problems, and a heuristic based on using tabu search in the context of a Benders decomposition framework. Then, we develop a hybrid Benders decomposition approach that allows us to combine the speed of heuristics with the rigor and precision of the exact Benders method. We discuss the results of extensive computational experiments.

In this paper, we present a general framework for designing approximation schemes for combinatorial optimization problems in which the objective function is a combination of more than one function. Examples of such problems include those in which the objective function is a product or ratio of two linear functions, parallel machine scheduling problems with the makespan objective, robust versions of weighted multiobjective optimization problems, and assortment optimization problems with logit choice models. The main idea behind our approximation schemes is the construction of an approximate Pareto-optimal frontier of the functions that constitute the given objective. Using this idea, we give the first fully polynomial-time approximation schemes for the max-min resource allocation problem with a fixed number of agents, combinatorial optimization problems in which the objective function is the sum of a fixed number of ratios of linear functions, or the product of a fixed number of linear functions, and assortment optimization problems with logit choice model.

We apply the level-3 reformulation-linearization technique (RLT3) to the quadratic assignment problem (QAP). We then present our experience in calculating lower bounds using an essentially new algorithm based on this RLT3 formulation. Our method is not guaranteed to calculate the RLT3 lower bound exactly, but it approximates this lower bound very closely and reaches it in some instances. For Nugent problem instances up to size 24, our RLT3-based lower bound calculation solves these problem instances exactly or serves to verify the optimal value. Calculating lower bounds for problem sizes larger than size 27 still presents a challenge because of the large amount of memory needed to implement the RLT3 formulation. Our presentation emphasizes the steps taken to significantly conserve memory by using the numerous problem symmetries in the RLT3 formulation of the QAP. We implemented this RLT3-based bound calculation in a branch-and-bound algorithm. Experimental results project significant runtime improvement over all other published QAP branch-and-bound solvers.

An instance of the quadratic assignment problem (QAP) with cost matrix Q is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix C such that for each assignment, the QAP and LAP objective function values are identical. Several sufficiency conditions are known that guarantee linearizability of a QAP. However, no polynomial time algorithm is known to test if a given instance of QAP is linearizable. In this paper, we give a necessary and sufficient condition for an instance of a QAP to be linearizable and develop an O(n4) algorithm to solve the corresponding linearization problem, where n is the size of the QAP.

One of the most important variants of the standard linear assignment problem is the bottleneck assignment problem. In this paper we give a method by which one can find all of the asymptotic moments of a random bottleneck assignment problem in which costs (independent and identically distributed) are chosen from a wide variety of continuous distributions. Our method is obtained by determining the asymptotic moments of the time to first complete matching in a random bipartite graph process and then transforming those, via a Maclaurin series expansion for the inverse cumulative distribution function, into the desired moments for the bottleneck assignment problem. Our results improve on the previous best-known expression for the expected value of a random bottleneck assignment problem, yield the first results on moments other than the expected value, and produce the first results on the moments for the time to first complete matching in a random bipartite graph process.

Quadratic assignment is a basic problem in combinatorial optimization that generalizes several other problems such as traveling salesman, linear arrangement, dense k subgraph, and clustering with given sizes. The input to the quadratic assignment problem consists of two n × n symmetric nonnegative matrices $W=(w_{i, j})$ and $D=(d_{i, j})$ . Given matrices W, D, and a permutation $\pi: [n] \rightarrow [n]$ , the objective function is $Q(\pi):= \sum_{i, j \in [n], i \ne j} w_{i, j} \cdot d_{\pi(i), \pi(j)}$ . In this paper, we study the maximum quadratic assignment problem, where the goal is to find a permutation π that maximizes $Q(\pi)$ . We give an $\tilde{O}(\sqrt{n})$ -approximation algorithm, which is the first nontrivial approximation guarantee for this problem. The above guarantee also holds when the matrices W, D are asymmetric. An indication of the hardness of maximum quadratic assignment is that it contains as a special case the dense k subgraph problem, for which the best-known approximation ratio is $\approx n^{1/3}$ (Feige et al. [Feige, U., G. Kortsarz, D. Peleg. 2001. The dense k-subgraph problem. Algorithmica29(3) 410--421]). When one of the matrices W, D satisfies triangle inequality, we obtain a $2e/(e-1) \approx 3.16$ -approximation algorithm. This improves over the previously best-known approximation guarantee of four (Arkin et al. [Arkin, E. M., R. Hassin, M. Sviridenko. 2001. Approximating the maximum quadratic assignment problem. Inform. Processing Lett.77 13--16]) for this special case of maximum quadratic assignment. The performance guarantee for maximum quadratic assignment with triangle inequality can be proved relative to an optimal solution of a natural linear programming relaxation that has been used earlier in branch-and-bound approaches (see, eg., Adams and Johnson [Adams, W. P., T. A. Johnson. 1994. Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS Ser. Discrete Math. Theoret. Comput. Sci.16 43--77]). It can also be shown that this linear program (LP) has an integrality gap of $\tilde{\Omega}(\sqrt{n})$ for general maximum quadratic assignment.

The quadratic assignment problem (QAP) is arguably one of the hardest NP-hard discrete optimization problems. Problems of dimension greater than 25 are still considered to be large scale. Current successful solution techniques use branch-and-bound methods, which rely on obtaining strong and inexpensive bounds. In this paper, we introduce a new semidefinite programming (SDP) relaxation for generating bounds for the QAP in the trace formulation. We apply majorization to obtain a relaxation of the orthogonal similarity set of the quadratic part of the objective function. This exploits the matrix structure of QAP and results in a relaxation with much smaller dimension than other current SDP relaxations. We compare the resulting bounds with several other computationally inexpensive bounds such as the convex quadratic programming relaxation (QPB). We find that our method provides stronger bounds on average and is adaptable for branch-and-bound methods.

In many computational experiments, correlation is induced between certain types of coefficients in synthetic (or simulated) instances of classical optimization problems. Typically, the correlations that are induced are only qualified—that is, described by their presumed intensity. We quantify the population correlations induced under several strategies for simulating 0–1 knapsack problem instances and also for correlation-induction approaches used to simulate instances of the generalized assignment, capital budgeting (or multidimensional knapsack), and set-covering problems. We discuss implications of these correlation-induction methods for previous and future computational experiments on simulated optimization problems.

The traveling salesman problem is one of the most famous combinatorial optimization problems and has been intensively studied. Many extensions to the basic problem have also been proposed, with the aim of making the resulting mathematical models as realistic as possible. We present a new extension to the basic problem, where travel times are specified as a range of possible values. This model reflects the intrinsic difficulties of estimating travel times in reality. We apply the robust deviation criterion to drive optimization over the interval data problem so obtained. Some interesting theoretical properties of the new optimization problems are identified and discussed, together with a new mathematical formulation and some exact and heuristic algorithms. Computational experiments are finally presented.

In the generalized quadratic assignment problem (GQAP) we are given n weighted facilities, m capacitated sites, a traffic intensity matrix between facilities, a distance matrix between sites, unit traffic costs, and assignment costs of facilities to sites. The aim is to determine an assignment of facilities to sites so that the sum of assignment and traffic costs is minimized and the total weight of all facilities assigned to the same site does not exceed the site capacity. The GQAP is a generalization of the quadratic assignment problem (QAP) in which n = m and exactly one facility must be assigned to each site. The problem has applications in container yard management and in the assignment of equipment to manufacturing sites. This article describes a memetic heuristic for the GQAP, as well as an integer linear programming formulation that can be solved by CPLEX for small instances. For larger instances, feasible solutions can be obtained by a truncated branch-and-bound procedure. Computational experiments show that on small instances the proposed heuristic always yields an optimal solution; on larger instances it always outperforms the truncated branch-and-bound algorithm.

We propose a tabu search algorithm for the generalized assignment problem, which is one of the representative combinatorial optimization problems known to be NP-hard. The algorithm features an ejection chain approach, which is embedded in a neighborhood construction to create more complex and powerful moves. We also incorporate an adaptive mechanism for adjusting search parameters, to maintain a balance between visits to feasible and infeasible regions. Computational results on benchmark instances of small sizes show that the method obtains solutions that are optimal or that deviate by at most 0.16% from the best known solutions. Comparisons with other approaches from the literature show that, for instances of larger sizes, our method obtains the best solutions among all heuristics tested.

In this paper we propose several variants of a new genetic algorithm for the solution of the quadratic assignment problem. We designed a special merging rule for creating an offspring that exploits the special structure of the problem. We also designed a new type of a tabu search, which we term a concentric tabu search. This tabu search is applied on the offspring before consideration for inclusion in the population. The algorithm provided excellent results for a set of 29 test problems having between 30 and 100 facilities.

The Generalized Assignment Problem (GAP) is the problem of finding the minimal cost assignment of jobs to machines such that each job is assigned to exactly one machine, subject to capacity restrictions on the machines. We propose a new stochastic model for the GAP. A tight condition on this stochastic model under which the GAP is feasible with probability one when the number of jobs goes to infinity is derived. This new stochastic model enables us to analyze the adequacy of most of the random generators given for the GAP in the literature. We demonstrate that the random generators commonly used to test solution procedures for the GAP tend to create easier problem instances when the number of machines m increases. We describe a greedy heuristic for the GAP, and use it to illustrate the results from the paper.

Multistart constructive approaches operate by applying a local search procedure to start from different initial solutions produced by a repeated (variable) constructive process. The classical Random Restart procedure and the more recent GRASP procedure are prominent examples of such approaches. Adaptive memory strategies that are the heart of tabu search methods give a foundation for alternative, enhanced, multistart approaches. We demonstrate this by showing that a simple implementation of adaptive memory search principles, even when restricted to the constructive phases, can provide more effective multistart methods. Computational experiments for the quadratic assignment problem disclose that these methods improve significantly over previous multistart methods that do not incorporate such memory based strategies.

A new bounding procedure for the Quadratic Assignment Problem (QAP) is described which extends the Hungarian method for the Linear Assignment Problem (LAP) to QAPs, operating on the four dimensional cost array of the QAP objective function. The QAP is iteratively transformed in a series of equivalent QAPs leading to an increasing sequence of lower bounds for the original problem. To this end, two classes of operations which transform the four dimensional cost array are defined. These have the property that the values of the transformed objective function Z′ are the corresponding values of the “old” objective function Z, shifted by some amount C. In the case that all entries of the transformed cost array are nonnegative, then C is a lower bound for the initial QAP. If, moreover, there exists a feasible solution U to the QAP, such that its value in the transformed problem is zero, then C is the optimal value of Z and U is an optimal solution for the original QAP. The transformations are iteratively applied until no significant increase in constant C as above is found, resulting in the so called Dual Procedure (DP). Several strategies are listed for appropriately determining C, or equivalently, transforming the cost array. The goal is the modification of the elements in the cost array to obtain new equivalent problems that bring the QAP closer to solution. In some cases the QAP is actually solved, though solution is not guaranteed. The close relationship between the DP and the Linear Programming formulation of Adams and Johnson is presented. The DP attempts to solve Adams and Johnson's CLP, a continuous relaxation of a linearization of the QAP. This explains why the DP produces bounds close to the optimum values for CLP calculated by Johnson in her dissertation and by Resende, et al. in their Interior Point Algorithm for Linear Programming. The benefit of using DP within a branch-and-bound algorithm is described. Then, two versions of DP are tested on the Nugent test instances from size 5 to size 30, as well as several other test instances from QAPLIB. These compare favorably with earlier bounding methods.

The generalized assignment problem examines the maximum profit assignment of jobs to agents such that each job is assigned to precisely one agent subject to capacity restrictions on the agents. A new algorithm for the generalized assignment problem is presented that employs both column generation and branch-and-bound to obtain optimal integer solutions to a set partitioning formulation of the problem.

Many transportation problems can be formulated as a linearly-constrained convex programming problem whose objective function consists of entropy functions and other cost-related terms. In this paper, we propose an unconstrained convex programming dual approach to solving these problems. In particular, we focus on a class of linearly-constrained entropy maximization problem with quadratic cost, study its Lagrangian dual, and provide a globally convergent algorithm with a quadratic rate of convergence. The theory and algorithm can be readily applied to the trip distribution problem with quadratic cost and many other entropy-based formulations, including the conventional trip distribution problem with linear cost, the entropy-based modal split model, and the decomposed problems of the combined problem of trip distribution and assignment. The efficiency and the robustness of this approach are confirmed by our computational experience.

Statistical experimental design and analysis is a cornerstone for scientific inquiry that is rarely applied in reporting computational testing. This approach is employed to study the relative performance characteristics of the four leading algorithmic and heuristic alternatives to solve the Linear Cost Generalized Assignment Problem (LCGAP) against a newly developed heuristic, Variable-Depth Search Heuristic (VDSH). In assessing the relative effectiveness of the prominent solution methodologies and VDSH under the effects of various problem characteristics, we devise a carefully designed experimentation of state-of-the-art implementations; through a rigorous statistical analysis we identify the most efficient method(s) for commonly studied LCGAPs, and determine the effect on solution time and quality of problem class and size.

We propose an algorithm for combinatorial optimization where an explicit check for the repetition of configurations is added to the basic scheme of Tabu search. In our Tabu scheme the appropriate size of the list is learned in an automated way by reacting to the occurrence of cycles. In addition, if the search appears to be repeating an excessive number of solutions excessively often, then the search is diversified by making a number of random moves proportional to a moving average of the cycle length. The reactive scheme is compared to a “strict” Tabu scheme that forbids the repetition of configurations and to schemes with a fixed or randomly varying list size. From the implementation point of view we show that the Hashing or Digital Tree techniques can be used in order to search for repetitions in a time that is approximately constant. We present the results obtained for a series of computational tests on a benchmark function, on the 0-1 Knapsack Problem, and on the Quadratic Assignment Problem. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

New lower bounds for the quadratic assignment problem QAP are presented. These bounds are based on the orthogonal relaxation of QAP. The additional improvement is obtained by making efficient use of a tractable representation of orthogonal matrices having constant row and column sums. The new bound is easy to implement and often provides high quality bounds under an acceptable computational effort.

We introduce a new lower bound for the quadratic assignment problem based on a sequence of equivalent formulations of the problem. We present a procedure for obtaining tight bounds by sequentially applying our approach in conjunction with the A. Assad and W. Xu bound and the N. Christofides and M. Gerrard bound.

Let A and B be m × m matrices. The aim is to maximize Q(σ) = ∑i, jaijbσ(i)σ(j) over all permutations σ of 1, 2, …, m. We define a simple “greedy” algorithm that constructs a permutation σ* that gives a large Q(σ*). Assuming that the entries of A are i.i.d. with a symmetric distribution, and that the entries of B are independent of A, we show under some weak moment conditions EQ(σ*) ≥ K−1m3/2(log m)1/2, where the constant k does not depend on m. This contrasts with the fact that maxσ ≤ Km3/2(log m)1/2 with overwhelming probability.

This paper describes an adaptation of Tabu Search, a recent technique to overcome local optimality, to the Quadratic Assignment Problem (QAP). Computational experiments with different parameter values and different strategies have been performed for some QAPs from the literature and some randomly generated QAPs of dimensions varying between 42 and 90. The method is implemented in a flexible form which allows the user to interact and change the parameters (tabu list size, the iteration limit, a search diversification parameter and the number of new starting solutions) during the run. The results suggest that good tabu list sizes increase with dimension of the problem. The algorithm appears to be a very efficient method for QAPs: for the standard problems tested, the best known solutions were obtained using less CPU time than previously reported in the literature. For Steinberg's problem (n = 36) with rectangular distances, a better solution than previously known in the literature was obtained. In addition, in comparison with simulated annealing, tabu search appears to be superior with respect to the solution quality. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

This paper presents a new algorithm for solving the assignment problem. The algorithm is based on a scheme of relaxing the given problem into a series of simple network flow (transportation) problems for each of which an optimal solution can be easily obtained. The algorithm is thus seen to be able to take advantage of the nice properties in both the primal and the dual approaches for the assignment problem. The computational bound for the algorithm is shown to be 0(n3) and the average computation time is better than most of the specialized assignment algorithms.

We present a polynomial primal simplex algorithm for the assignment problem. For n × n assignment problem with integer cost coefficients, the algorithm generates at most n3 ln ▵ bases prior to reach the optimal basis, where ▵ is the difference in objective value between an initial extreme point and the optimal extreme point.

An experiment with plant layout formulated as a quadratic assignment problem gave the following results: (1) The CRAFT algorithm does as well as human subjects in solving the plant layout problem; (2) CRAFT does better as problem size increases if the human subjects have no prior knowledge of the computer solution values; (3) there is no breakpoint in relative problem solving ability between humans and computers at 200% flow dominance (the coefficient of variation of the flow matrix expressed as a percent); (4) the point at which the computer becomes better, as opposed to equally good, is more clearly indicated by problem size than by flow dominance; (5) humans can solve problems with high flow dominance and problems with near-zero flow dominance better than they can solve problems with low flow dominance, though the computer is still at least as good across all levels of flow dominance.

For the distance matrix of symmetric traveling salesman problems a simple transformation into an equivalent asymmetric one is given. Assignment algorithms yield sharper lowerbounds and less subtours from the transformed distance matrix. This implies a better performance for traveling salesman algorithms based on the assignment relaxation.

The Tree QAP is a special case of the Quadratic Assignment Problem (QAP) where the nonzero flows form a tree. No condition is required for the distance matrix. This problem is NP-complete and is also a generalization of the Traveling Salesman Problem. In this paper, we present a branch-and-bound algorithm for the exact solution of the Tree QAP based on an integer programming formulation of the problem. The bounds are computed using a Lagrangian relaxation of this formulation. To solve the relaxed problem, we present a Dynamic Programming algorithm which is polynomially bounded. The obtained lower bound is very sharp and equals the optimum in many cases. This fact allows us to employ a reduction method to decrease the number of variables and leads to search-trees with a small number of nodes compared to those usually encountered in problems of this type. Computational results are given for problems with size up to 25.

We know that the effectiveness of the branch-and-bound algorithms proposed for the solution of combinatorial optimization problems greatly depends on the tightness of the available bounds. In this paper, we consider optimization problems with a linear objective function. We propose an additive approach for computing lower bounds that yields an increasing sequence of values. An application to the traveling salesman problem with precedence constraints is presented to exemplify the technique.

We report the solution to optimality of ten large-scale symmetric travelling salesman problems. The travelling salesman problem (TSP) is one of the standard problems of the Operations Research/Management Science literature and is cited in virtually every textbook on this subject. The TSP is a hard combinatorial optimization problem for which to date no technically good algorithm is known. All known algorithmic approaches to the TSP that are amenable to a worst-case analysis have yielded nothing for this problem that is as satisfactory as the existing solution procedures for, as an example, flow problems in networks. Furthermore, recent theoretical work has shown that the TSP is algorithmically equivalent to the general zero-one decision problem with linear constraints and objective function. The phrase “This problem is as hard as a travelling salesman problem” reflects this fact and expresses the slim chances of finding an optimal solution to the problem at hand. It is therefore all the more surprising that in the current study, all of the test problems were solved to optimality—i.e., the proposed methodology did not fail on any one of the ten large-scale test problems of the computational study. Besides being a prototype of a difficult combinatorial optimization problem, the travelling salesman problem has a variety of applications in its own right, mostly in the areas of production management, vehicle routing, and vehicle scheduling. A number of related problems, such as, for example, the multiple travelling salesman problem with m travelling salesmen located at a central depot and with fixed charges for their deployment, have been shown elsewhere to fit the standard form of the TSP treated in this paper. The smallest problem of this computational study has 48 cities and the largest one has 318 cities, i.e., the corresponding zero-one linear programming problems have between 1,128 and 50,403 zero-one variables. The algorithmic procedure is a cutting-plane approach coupled with branch-and-bound. For the latter we use the IBM software system MPSX-MIP/370 in a novel (iterative) way. The cutting-planes that we use are subtour-elimination and comb constraints, i.e., they belong to the class of valid inequalities for the symmetric travelling salesman problem which define facets for the associated polytope. This fact, which has been proven mathematically elsewhere, makes the cutting-planes encountered here different from other arbitrary, but valid, cutting-planes encountered in integer programming. In fact, cutting-planes have been virtually abandoned as an algorithmic tool in integer programming because of the erratic behavior of such algorithms exhibited in earlier computational studies. The present study convincingly establishes the usefulness of mathematically proven good cutting-planes as an invaluable algorithmic tool for difficult combinatorial optimization problems. Here the word optimization is taken in its very meaning—we are interested solely in finding a solution that minimizes a cost function and in proving it to be an optimal solution.

In many public sector location problems, it is often desirable to locate facilities in such a way to minimize the number (or cost) of facilities while insuring tint all demand centers are within a stated maximal service time front any facility. However, when insufficient resources exist to allow die construction of enough facilities to serve all demand centers within the alloted time, the location problem is frequently restated in order to locate the budgeted facilities to serve the serviced population. Problems of the latter type are generally known as maximal covering location problems, which may have a number of extensions, including mandatory closeness constraints which place an upper bound on the maximal service time requirement for the entire population. This note demonstrates how this class of frequently encountered problems can be formulated as generalized assignment problems within the conceptual framework presented by Ross and Soland (Ross, G. T., R. Soland. 1977. Modeling facility location problems as generalized assignment problems. Management Sci. 24 (3, November) 345–357.) for other discrete public and private location problems.

The “signature” of a dual feasible basis of the assignment problem is an n-vector whose ith component is the number of nonbasic activities of type (i, j). This paper uses signatures to describe a method for finding optimal assignments that terminates in at most (n − 1)(n − 2)/2 pivot steps and takes at most O(n3) work.

Let z* be the (unknown) optimal value of a combinatorial optimization problem (in minimization form) and let z be a constant satisfying Prob(z* ≥ z) ≥ 1 − α for a fixed α ∈ (0, 1). Then z is called a statistical or probabilistic lower bound at significance level 1 − α. We discuss how statistical lower bounds can be used to measure the effectiveness of an approximate solution and to fathom subproblems in a branch and bound approach. After reviewing some methods for obtaining statistical lower bounds, we report on extensive computational experience for two notoriously difficult combinatorial optimization problems—the traveling salesman problem and the quadratic assignment problem. From our experience we conclude that statistical bounds are highly useful for quadratic assignment problems. In this problem context, the quality of simple analytic formulas is comparable to the quality of the maximum likelihood formula. In general, using statistics to aid in the solution of combinatorial optimization problems should be most useful when such problems are “large.”

A simplified description of a new computing procedure for the Hitchcock-Koopmans transportation problem is given, together with a step by step solution of an illustrative example. The procedure is based on Kuhn's combinatorial algorithm for the assignment problem and a simple “labeling process” for solving maximal flow problems in networks. The proposed computation appears to be considerably more efficient than the specialized form of the simplex method which is in common use.

In this paper, it is shown that if the cost matrix of an assignment problem has the following property cij = |j − i| then any basic feasible solution is optimal if and only if its unit components belong to two well-defined symmetric regions. The matrix with above mentioned property is called the “reordering matrix,” because it arose for the first time in the reordering of nodes of a critical path and other acyclic network problems. One deals with similar matrices in some problems related to order statistics.

This paper discusses the problem of assigning locations to indivisible facilities and its relation to the quadratic assignment problem. It also develops two suboptimal algorithms, one dealing with the general quadratic assignment problem and the other with an interesting special case. Qualitative and quantitative comparisons with existing suboptimal algorithms are presented.

The multidimensional assignment problem is a higher dimensional version of the standard (two-dimensional) assignment problem in the literature. The higher dimensions can be thought of as time or space dimensions or both. An algorithm is proposed for the solution of the multi-index assignment problem. The algorithm is based on a tree search technique of the branch-and-bound variety. It uses dual subproblems to provide easily computed bounds for the primal assignment problem.

This paper deals with the solution to a discrete optimization problem by decomposition. It develops a criterion for ranking the decomposition procedures, discusses the properties of the optimal decompositions, and gives an algorithm for finding the best decomposition in the case of no storage limitation.

This paper elaborates a method of attack on traveling-salesman problems, proposed by the authors in an earlier paper, in which linear programming is used to reduce the combinatorial magnitude of such problems. To illustrate the method, a step-by-step solution of Barachet's ten-city example is presented.

Assignment problems arise whenever elements of a finite set have to be paired with elements of another finite set in such a way as to maximize a certain function of the pairing. In this paper three different formulations of such a problem are given. They are analyzed and a method for obtaining a low-cost solution is developed.

The transportation problem has offered two mathematical facets: (1) as a specialized type of linear programming problem, (2) as a method of representation of some combinatorial problems. In this paper a third aspect of the mathematical properties of the transportation problem is developed. It is shown that the same mathematical framework can be extended beyond pair-wise connections, to the determination of optimum linked paths over a series of points. This extension although viewed here as a linear programming problem, takes advantage of the combinatorial aspect of the transportation problem, and applications may arise which, like the assignment problem, appear to be combinatorial problems, but which can be solved by linear programming.

The essential features of the branch-and-bound approach to constrained optimization are described, and several specific applications are reviewed. These include integer linear programming (Land-Doig and Balas methods), nonlinear programming (minimization of nonconvex objective functions), the traveling-salesman problem (Eastman and Little, et al. methods), and the quadratic assignment problem (Gilmore and Lawler methods). Computational considerations, including trade-offs between length of computation and storage requirements, are discussed and a comparison with dynamic programming is made. Various applications outside the domain of mathematical programming are also mentioned.

The Hungarian method gives an efficient algorithm for finding the minimal cost assignment. However, in some cases it may be useful to determine the second minimal assignment (i.e., the best assignment after excluding the minimal cost assignment) and in general the kth minimal assignment for k = 1, 2, …. These things can easily be determined if all the assignments can be arranged as a sequence in increasing order of cost. This paper describes an efficient algorithm for such a ranking of all the assignments. The maximum computational effort required to generate an additional assignment in the sequence is that of solving at most (n − 1) different assignment problems, one each of sizes 2, 3, …, n.

We construct numerical examples that force Hungarian-method algorithms for the assignment problem to their worst-case time bounds. These bounds are thereby clarified.

Megiddo (Megiddo, N. 1979. Combinatorial optimization with rational objective functions. Math. Oper. Res. 4 414–424.) has proposed an algorithm to solve a class of combinatorial optimization problems with rational objective functions in polynomial time. The minimum ratio path problem is claimed to be one such problem. This claim is not correct as indicated below.