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.
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.