Note however, that although there is a binary optimal solution, it is possible, for instance if using an interior point solver, for the Continuous Linear Program to produce a non-integer (non-binary) optimal solution (even though there is also an optimal solution which is binary).
Alternatively, note that in the original rectangular formulation, the problem has totally unimodular constraint matrix and integer constraint right-hand side, so the Integrality Theorem directly applies.
The assignment problem is specified by the cost matrix cij for minimization problems or the benefit matrix aij for maximization problems.
Those matrices describe the cost or benefit of assigning object j to person i.
Even as the auction is considered one of the fastest algorithms, for large-scale and complex instances of the assignment problem the auction algorithm can take a lot of time to find the optimal solution. discussed five types of the assignment problem instances which are Geometric, Fixed-Cost, High-Cost, Low-Cost and Uniformly Random.
It was shown that for the first two problem types the auction algorithm performs poorly in terms of the running time in comparison with the other three problem types.
Due to the dynamic nature of many applications, as well as the expansion of problem sizes, where a solution needs to be found under tight time constraints, heuristics that give rise to solutions that are close to optimal solution are sought.
Our efforts in that regards lead us to the Deep Greedy Switching (DGS) algorithm.
DGS was developed to fulfill these requirement and in our context it sacrificed a mere 0.6% of the optimal solution obtained by the auction algorithm while attaining a substantial speedup in terms of computational time.
A plethora of greedy heuristics have been developed for different optimization problems.