# Simplex method can't solve assignment problem?

The problem:

I am trying to solve http://acm.timus.ru/problem.aspx?space=1&num=1076 , it's an online judge for programming problems. The problem could be solved by a simple application of an assigment problem solvers like mincost-maxflow or Hungarian algorithm. The matrices are small (150 by 150) and I am trying to push a solution with simplex method - it does not pass time limit and I don't think it's my fault.

Assignment Problem

$$min \sum c_{i,j}x_{i,j}\\ \sum_{i} x_{i,j}=1 \\ \sum_{j} x_{i,j}=1 \\ x_{i,j} \geq 0$$

What I've done:

• I added checking for cycling - indeed cycling was present. I've employed some schemes for cycling elliminations: Bland's rule, lexicographical rule and Zadeh's rule. None of them triggered cycling checking, but the solution still does not pass time limit.
• I removed all artificial variables and slacks. My initialization is $$x_{i,i}=1$$ and other n-1 basic variable are 0 (I use variables that don't have a non-zero value after gaussian eillimination with $$x_{i,i}$$)

My hypothesis

I am no expert in fields of linear programming but here are some of my thoughts: I think the problem is very degenerate, the rank of constraints matrix is $$2n-1$$ with n variables having value equal to 1 and rest n-1 having value equal to 0. During some stage of the algorithm we enter a situation where many 0 valued variables are interchanged making simplex method exponential. I printed function cost and it stops reducing after some time, even though reduced costs indicate that improvement is still possible (i.e. stopping criterion for simplex method is not satisfied).

What I don't want

• I have an accepted verdict on this problem with mincost-maxflow, so please don't suggest Hungarian algorithm or simiar, I want to know if simplex method can solve this problem
• Please don't suggest modifications for simplex method that make assumptions about the graph model of the problem. i.e. suggestions like "make 0 valued edges be an alternating path". I want to know if pure simplex method can solve the problem (with possible modifications, but that do not make any assuptions about the problem).

What I do want

• I want to know if my hypothesis is correct and simplex method is simply not applicable to these kinds of problems.
• If not - what kind of scheme can be used to overcome this problem.
• While it works in principle, Bland's rule can be very slow in getting you out of a cycling situation with a very degenerate problem. – Robert Israel Aug 11 '19 at 20:02

I've managed to resolve the problem with the help of generalized transportation problem:

$$min \sum c_{i,j}x_{i,j}\\ \sum_{i} x_{i,j}=a_i \\ \sum_{j} x_{i,j}=b_j \\ x_{i,j} \geq 0$$

Where, of course, $$\sum_{i} a_i = \sum_{j} b_j\\$$. In general case this problem has constraint matrix with rank $$2n-1$$ where no variables equal to 0, because in this case multiple cells can be used in a row and column.

Having that in mind we can perturb our constraints:

$$\sum_{i} x_{i,j}=1+\epsilon * random(-1,1) \\ \sum_{j} x_{i,j}=1+\epsilon * random(-1,1) \\$$

where $$\epsilon$$ is some small number, and making sure that $$\sum_{i} a_i = \sum_{j} b_j\\$$ by normalizing afterwards. This is probably some variant of the perturbation technique for simplex method.

Having done that, we have other $$n-1$$ variables small and positive making the problem non degenerate.