1
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Robert Israel Aug 11 '19 at 20:02
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.