Asymptotics in the random assignment problem

Summary We show that, in the usual probabilistic model for the random assignment problem, the optimal cost tends to a limit constant in probability and in expectation. The method involves construction of an infinite limit structure, in terms of which the limit constant is defined. But we cannot improve on the known numerical bounds for the limit.Research supported by NSF Grant MCS90-01710     

Constructive bounds and exact expectations for the random assignment problem

The random assignment problem is to choose a minimum‐cost perfect matching in a complete n×n bipartite graph, whose edge weights are chosen randomly from some distribution such as the exponential distribution with mean 1. In this case it is known that the expectation does not grow unboundedly with n, but approaches some limiting value c* between 1.51 and 2. The limit is conjectured to be π²/6, while a recent conjecture is that for finite n, the expected cost is ∑ 1/i². This paper contains two principal results. First, by defining and analyzing a constructive algorithm, we show that the limiting expectation is c*<1.94. Second, we extend the finite‐n conjecture to partial assignments on complete m×n bipartite graphs and prove it in some limited cases. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 113–144, 1999     

Reducing the elastic generalized assignment problem to the standard generalized assignment problem

The elastic generalized assignment problem (eGAP) is a natural extension of the generalized assignment problem (GAP) where the capacities are not fixed but can be adjusted; this adjustment can be expressed by continuous variables. These variables might be unbounded or restricted by a lower or upper bound, respectively. This paper concerns techniques aiming at reducing several variants of eGAP to GAP, which enables us to employ standard approaches for the GAP. This results in a heuristic, which can be customized in order to provide solutions having an objective value arbitrarily close to the optimal.     

An on-line assignment problem with random effectiveness and costly information

We study the on-line assignment problem, where the testing of effectiveness incurs a cost. An optimal testing policy to maximize expected net effectiveness is derived.     

Contributions to the quadratic assignment problem

Tree search procedures for solving the Koopmans Beckmann quadratic assignment problem (QAP) are unable to solve any reasonable size QAP's mainly because good quality lower bounds for this problem cannot be computed.The purpose of this paper is to propose a bounding technique based on the extraction from the QAP formulation, of a large linear assignment problem (which can then be solved optimally), leaving as a residual problem as ‘small’ a QAP as possible. The solution of this residual QAP can then be bounded by a separate procedure. This 2-step method produces improved bounds as compared with those produced by the direct application of the bounding algorithms to the original QAP. In addition, a procedure is described for the a priori fixing of variables in the QAP formulation, thus reducing the number of variables in the problem.     

The quadratic three-dimensional assignment problem: Exact and approximate solution methods

This paper reports on algorithm development for solving the quadratic three-dimensional assignment problem (Q3AP). The Q3AP arises, for example, in the implementation of a hybrid ARQ (automatic repeat request) scheme for enriching diversity among multiple packet re-transmissions, by optimizing the mapping of data bits to modulation symbols. Typical practical problem sizes would be 8, 16, 32 and 64.     

On optimality of a polynomial algorithm for random linear multidimensional assignment problem

We demonstrate that the linear multidimensional assignment problem with iid random costs is polynomially e{\varepsilon} -approximable almost surely (a.s.) via a simple greedy heuristic, for a broad range of probability distributions of the assignment costs. Specifically, conditions on discrete and continuous distributions of the cost coefficients, including distributions with unbounded support, have been established that guarantee convergence to unity in the a.s. sense of the cost ratio between the greedy solution and optimal solution. The corresponding convergence rates have been determined.     

A graph-theoretic model to solve the approximate string matching problem allowing for translocations

In this paper, we study the approximate string matching problem under a string distance whose edit operations are translocations of equal length factors. We extend a graph-theoretic approach proposed by Rahman and Illiopoulos (2008) to model our problem. In the sequel, we devise efficient algorithms based on this model to solve a number of variants of the string matching problem with translocations.     

MIP approaches for the integrated berth allocation and quay crane assignment and scheduling problem

In this paper we consider an integrated berth allocation and quay crane assignment and scheduling problem motivated by a real case where a heterogeneous set of cranes is considered. A first mathematical model based on the relative position formulation (RPF) for the berth allocation aspects is presented. Then, a new model is introduced to avoid the big-M constraints included in the RPF. This model results from a discretization of the time and space variables. For the new discretized model several enhancements, such as valid inequalities, are introduced. In order to derive good feasible solutions, a rolling horizon heuristic (RHH) is presented. A branch and cut approach that uses the enhanced discretized model and incorporates the upper bounds provided by the RHH solution is proposed. Computational tests are reported to show (i) the quality of the linear relaxation of the enhanced models; (ii) the effectiveness of the exact approach to solve to optimality a set of real instances; and (iii) the scalability of the RHH based on the enhanced mathematical model which is able to provide good feasible solutions for large size instances.     

ILP approaches to the blockmodel problem

Blockmodelling is a method for identifying structural similarities or equivalences between elements which has applications in a variety of contexts, including multiattribute performance assessment. One criterion for forming blocks results in a difficult non-linear integer programme. We give several integer linear programming formulations of this problem and provide comparative computational results. We show that methods of reducing symmetry proposed by Sherali and Smith are not effective in this case and propose an iterative approach in which the size of the problem is reduced.     

Construction of an interpolant operator: Application to the three-dimensional electrostatic problem

We propose in Zaghdani (2006) [2] and Zaghdani and Daveau (in press) [3], a discontinuous Galerkin formulation with a mixed setting. In this paper, we construct an interpolant on a discontinuous space to obtain the inf–sup condition which is necessary to show that the formulation is well posed.     

Novel approaches to the discrimination problem

We consider the problem of determining a hyperplane that separates, as well as possible, two finite sets of points inR ⁿ . We analyze two criteria for judging the quality of a candidate hyperplane (i) the maximal distance of a misclassified point to the hyperplane (ii) the number of misclassified points. In each case, we investigate the computational complexity of the corresponding mathematical programs, give equivalent formulations, suggest solution algorithms and present preliminary numerical results.Research supported by NSERC grants 5789 and 46405, the Academic Research Program of the Department of National Defense (Canada) and FCAR grant 91NC0510. (Québec).     

A reduction approach to the repeated assignment problem

We consider the repeated assignment problem (RAP), which is a K-fold repetition of the n × n linear assignment problem (LAP), with the additional requirement that no assignment can be repeated more than once. In actual applications K is typically much smaller than n. First, we derive upper and lower bounds respectively by a heuristic together with local search, and an efficient method solving the continuous relaxation. The latter also solves a Lagrangian relaxation, such that the related pegging test, to fix variables at zero or one, decomposes into K independent pegging tests to LAPs. These can be solved exactly by transforming them into all-pairs shortest path problems. Together with these procedures, we also employ a virtual pegging test and reduce RAP in size. Numerical experiments show that the reduced instances, with K ? n, can be solved exactly using standard MIP solvers.     

The ζ(2) limit in the random assignment problem

The random assignment (or bipartite matching) problem asks about A_n=min_π ∑c(i, π(i)), where (c(i, j)) is a n×n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations π. Mézard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EA_n→ζ(2)=π²/6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Here we construct the optimal matching on the infinite tree. This yields a rigorous proof of the ζ(2) limit and of the conjectured limit distribution of edge‐costs and their rank‐orders in the optimal matching. It also yields the asymptotic essential uniqueness property: every almost‐optimal matching coincides with the optimal matching except on a small proportion of edges. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 381–418, 2001     

Biological computation of the solution to the quadratic assignment problem

Biological computing provides a promising approach to attacking computationally intractable problems. The quadratic assignment problem (QAP) is a well-known NP-hard combinatorial optimization problem. This paper addresses the problem of how to solve QAP under the Adleman–Lipton-sticker model. A theoretically efficient DNA algorithm for solving QAP is proposed, which is executed by performing O(Kn⁴) operations on test tubes of DNA molecular strands with n² + K + 1 bit regions, where n is the number of facilities, and K is the length of the binary representation of an upper bound on the objective function. With the rapid progress of molecular biology techniques, the proposed algorithm might be of practical use in treating medium-sized instances of QAP.     

On the bottleneck assignment problem

In this paper, a new approach for solving the bottleneck assignment problem is presented. The problem is treated as a special class of permutation problems which we call max-min permutation problems. By defining a suitable neighborhood system in the space of permutations and designating certain permutations as critical solutions, it is shown that any critical solution yields a global optimum. This theorem is then used as a basis to develop a general method to solve max-min permutation problems.This work was carried out by the junior author while holding a Purdue University Fellowship.     

Globally solving a nonlinear UAV task assignment problem by stochastic and deterministic optimization approaches

In this paper, we consider a task allocation model that consists of assigning a set of m unmanned aerial vehicles (UAVs) to a set of n tasks in an optimal way. The optimality is quantified by target scores. The mission is to maximize the target score while satisfying capacity constraints of both the UAVs and the tasks. This problem is known to be NP-hard. Existing algorithms are not suitable for the large scale setting. Scalability and robustness are recognized as two main issues. We deal with these issues by two optimization approaches. The first approach is the Cross-Entropy (CE) method, a generic and practical tool of stochastic optimization for solving NP-hard problem. The second one is Branch and Bound algorithm, an efficient classical tool of global deterministic optimization. The numerical results show the efficiency of our approaches, in particular the CE method for very large scale setting.     

On the advantage over a random assignment

We initiate the study of a new measure of approximation. This measure compares the performance of an approximation algorithm to the random assignment algorithm. This is a useful measure for optimization problems where the random assignment algorithm is known to give essentially the best possible polynomial time approximation. In this paper, we focus on this measure for the optimization problems Max‐Lin‐2 in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2, and Max‐k‐Lin‐2, a special case of the above problem in which each equation has at most k variables. The main techniques we use, in our approximation algorithms and inapproximability results for this measure, are from Fourier analysis and derandomization. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Multistate components assignment problem with optimal network reliability subject to assignment budget

The typical assignment problem for finding the optimal assignment of a set of components to a set of locations in a system has been widely studied in practical applications. However, this problem mainly focuses on maximizing the total profit or minimizing the total cost without considering component’s failure. In practice, each component should be multistate due to failure, partially failure, or maintenance. That is, each component has several capacities with a probability distribution and may fail. When a set of multistate components is assigned to a system, the system can be treated as a stochastic-flow network. The network reliability is the probability that d units of homogenous commodity can be transmitted through the network successfully. The multistate components assignment problem to maximize the network reliability is never discussed. Therefore, this paper focuses on solving this problem under an assignment budget constraint, in which each component has an assignment cost. The network reliability under a components assignment can be evaluated in terms of minimal paths and state-space decomposition. Subsequently an optimization method based on genetic algorithm is proposed. The experimental results show that the proposed algorithm can be executed in a reasonable time.