Search

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.

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.

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.

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.

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.

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.

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.”

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.

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.

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.

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.

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.

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.

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 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.