11
$\begingroup$

The simplex algorithm walks greedily on the corners of a polytope to find the optimal solution to the linear programming problem. As a result, the answer is always a corner of the polytope. Interior point methods walk the inside of the polytope. As a result, when a whole plane of the polytope is optimal (if the objective function is exactly parallel to the plane), we can get a solution in the middle of this plane.

Suppose that we want to find a corner of the polytope instead. For example if we want to do maximum matching by reducing it to linear programming, we don't want to get an answer consisting of "the matching contains 0.34% of the edge XY and 0.89% of the edge AB and ...". We want to get an answer with 0's and 1's (which simplex would give us since all corners consist of 0's and 1's). Is there a way to do this with an interior point method that guarantees to find exact corner solutions in polynomial time? (for example perhaps we can modify the objective function to favor corners)

$\endgroup$
  • 1
    $\begingroup$ @J.D.: Why don't you make this an answer? $\endgroup$ – Raphael Mar 24 '12 at 19:53
6
$\begingroup$

You might want to read the paper:

Sanjay Mehrotra, On finding a vertex solution using interior point methods, Linear Algebra and its Applications, Volume 152, 1 July 1991, Pages 233-253, ISSN 0024-3795, 10.1016/0024-3795(91)90277-4. sciencedirect article link

$\endgroup$
4
$\begingroup$

While the question in general makes sense, it's odd that you pick maximum matching as an example, because there are many algorithms (max flows for max cardinality bipartite matching, Edmonds' algorithm for nonbipartite matching, and the Hungarian algorithm for max weight bipartite matching) that will all give integer vertex solutions to the problem.

$\endgroup$
  • $\begingroup$ It was more of a theoretical interest rather than practical. Still, many times interior point methods are faster than simplex, so there could be problems where this is a practical issue ;) $\endgroup$ – Jules Mar 27 '12 at 8:17
3
$\begingroup$

For the lack of detail, this is merely a longer comment:

Karmarkar's polynomial time algorithm does only move near the edge. At the end, it finds a suitable basic solution (e.g. corner) which is optimal using a purification scheme¹. You can use this or a similar technique to move to a corner from a plane.


¹ I can't make it out in in Karmarkar's original paper. My reference is "Lineare Optimierung und Netzwerkoptimierung" (English: Linear and network optimisation) by Hamacher and Klamroth which has German and English text side by side.

$\endgroup$
1
$\begingroup$

Yes, there is a simple method and I have implemented it in C++ to combine the speed of interior point methods with the accuracy of simplex methods (using iterative refinement of the inverse of the basis matrix I can achieve accuracies of 1 part in 10^15 and better on dense constraint matrices with more than 1000 variables and constraints).

The key is in the simplex method that you use. Assume that the simplex method has a mechanism for refactoring a basis (e.g. after cumulative rounding errors render it necessary), and that this refactorization method simply recreates a basis inverse matrix for a basis that contains all the desired list of basic variables. Furthermore assume that even if the desired basis cannot be recreated in full, that the simplex algorithm is able to continue from a basis that contains 95% of the target basis, then the answer is very simple.

All you have to do is take the solution from your interior point method, eliminate the variable whose primary solution values are implied to be zero by complementary slackness, and given a basis size in the simplex problem of b, take the b variables in the interior point solution with the largest values (or as many as there are non-zero values if that is less than b), and refactor the simplex basis to contain those b variables. Then continue the simplex method until it solves. Since you are starting the simplex problem close to the finish this is usually very fast.

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