Optimization Online


Solving the Rectangular assignment problem and applications

A. Volgenant (a.volgenant***at***uva.nl)
J. Bijsterbosch (a.volgenant***at***uva.nl)

Abstract: The rectangular assignment problem is a generalization of the linear assignment problem (LAP): one wants to assign a number of persons to a smaller number of jobs, minimizing the total corresponding costs. Applications are, e.g., in the fields of object recognition and scheduling. Further, we show how it can be used to solve variants of the LAP, such as the k-cardinality LAP and the LAP with outsourcing by transformation. We introduce a transformation to solve the machine replacement LAP. We describe improvements of a LAP-algorithm for the rectangular problem, in general and slightly adapted for these variants, based on the structure of the corresponding cost matrices. For these problem instances, we compared the best special codes from literature to our codes, which are more general and easier to implement. The improvements lead to more efficient and robust codes, making them competitive on all problem instances and often showing much shorter computing times.

Keywords: Linear assignment; k-cardinality Linear Assignment; Linear Assignment Problem with outsourcing, Machine replacement

Category 1: Integer Programming (0-1 Programming )

Citation: Annals of OR, to appear


Entry Submitted: 10/15/2008
Entry Accepted: 10/15/2008
Entry Last Modified: 05/31/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society