©
Assignment Problem
Solves the Assignment Problem via the CPLEX API.
2024.May.16 10:29:02
Cost Cost matrix (integer or real)*
No null rows !

*(See below) •
Optimization   Maximization or minimization. •
Show interm. ? Shows CPLEX intermediate results.;
Show values ? Shows the coordinates of the graph. •

Solves a typical Assignment Problem (AP), using the IBM ILOG CPLEX software. The problem is solved as a Transportation Problem, i.e., with supplies of 1 and demands of 1 (instead of the "Hungarian algorithm").

The typical problem is usually stated as assigning jobs, J, to workers, W. The result shows the pairs (W, J) corresponding to minimum cost (or time, etc.). So, in terms of an equivalent Transportation Problem, each worker can be a source and each job can be a destination. (Here, the maximum cost is also computed.)

The cost data must be separated by standard characters: space, tab (such as from Excel by copy-paste) or csv, in coherent American or European style.

With the base data, the problem gives zMIN = 61 (zMAX = 92).

A graph is done showing the costs for each assignment, their sum being obviously the minimum cost computed.

Acknowledgements: See CPLEX problem.

References: Plate: Assignment

• Wikipedia: IBM ILOG CPLEX

• Wikipedia: Hungarian algorithm.

HungarianAlgorithm.com (accessed July, 2018).

Bai, Z., et al., eds., 2000, Templates for the Solution of Algebraic Eigenvalue Problems: a Practical Guide, SIAM, Philadelphia (Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, editors).
J. Dongarra, Sparse Matrix Storage Formats.

• 1910-07-06: Collatzs, Lothar (1980-09-26).

 
 
Valid HTML 4.01! IST http://web.tecnico.ulisboa.pt/~mcasquilho/compute/or/Fx-assignment.php
Created: 2018-07-06 — Last modified: 2018-07-06