ISSN:
1573-2894
Keywords:
network programming
;
assignment
;
integer programming
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract This manuscript presents a new heuristic algorithm to find near optimal integer solutions for the singly constrained assignment problem. The method is based on Lagrangian duality theory and involves solving a series of pure assignment problems. The software implementation of this heuristic, ASSIGN+1, successfully solved problems having one-half million binary variables (assignment arcs) in less than 17 minutes of wall clock time on a Sequent Symmetry S81 using a single processor. In computational comparisons with MPSX and OSL on an IBM 3081D, the specialized software was from 100 to 1,000 times faster. In computational comparisons with the specialized code of Mazzola and Neebe, we found that ASSIGN+1 was 40 times faster. In computational comparisons with our best alternating path specialized code, we found that ASSIGN+1 was more than three times faster than that code. This new software proved to be very robust as well as fast. The robustness is due to an elaborate scheme used to update the Lagrangean multipliers and the speed is due to the fine code used to solve the pure assignment problems. We also present a modification of the algorithm for the case in which the number of jobs exceeds the number of men along with an empirical analysis of the modified software.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01299389
Permalink
