• Despite of the fact that the variables X_ij of the Assignment Problem are binary (not continuous but integer, assuming only the value of 0 or 1), the assignment problem does not need to be solved by integer programming algorithms. Linear programming can solve the assignment problem by providing binary values to the variables at the optimal solution. Why?

Why this cannot happen to the Generalized Assignment Problem?

• The Hungarian Algorithm is a simplex-based algorithm but it is neither primal simplex nor dual simplex. What is it?

As the other two, that algorithm is based on a fundamental theorem of optimization (Karush-Kuhn-Tucker Conditions): An optimal solution should satisfy three conditions: primal feasibility, dual feasibility and complementary slackness.

• The Assignment Problem is highly degenerate. What is the degree of degeneracy of its Basic Feasible Solutions (BFS), i.e. what is the number of zero values in any BFS, expressed in terms of the problem size n (number of assignments and assignees)?