**The problem:**

I'm 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 simply applying an assignment problem solving algorithm such as mincost-maxflow or a Hungarian algorithm. The dice are small (150 out of 150) and I try to put forward a solution with the simplex method – it does not exceed the time limit and I do not think it's my fault.

**Problem of assignment**

$ 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 did:**

- I added the cycling check – indeed, cycling was present. I've used some schemes to eliminate cycling: Bland's rule, lexicographic rule and Zadeh's rule. None of them triggered the cycle check, but the solution still has not exceeded the time limit.
- I've removed all the artificial variables and pants. My initialization is $ x_ {i, i} = $ 1 and the other n-1 basic variables are 0 (I use variables that do not have a non-zero value after a Gaussian elimination with $ x_ {i, i} $)

**My hypothesis**

I am not an expert in the areas of linear programming, but here are some of my thoughts: I think the problem is very degenerate, the rank matrix of constraints is $ 2n-1 $ with n variables having a value equal to 1 and rest n-1 having a value equal to 0. During a step of the algorithm, we enter a situation in which many variables with value 0 are exchanged, which makes the simplex method exponential. I print the cost of the function and the discount ceases after a while, although the cost reduction indicates that an improvement is still possible (that is, the criterion of the ## EQU1 ## Stop of the simplex method is not satisfied).

**What I do not want**

- I have an accepted verdict on this problem with mincost-maxflow, so please do not suggest any Hungarian algorithm or similar, I want to know if
**simplex method can solve this problem**
- Please do not suggest changes for the simplex method that
**make assumptions about the graphical model of the problem**. suggestions such as "make the edges of value 0 an alternative path". I want to know if the purely simplex method can solve the problem (with possible modifications, but that makes no assumptions about the problem).

**What I want**

- I want to know if my hypothesis is correct and that the simplex method simply does not apply to this kind of problem.
- If not, what kind of system can be used to solve this problem.