Monday, 15:45 - 16:10 h, Room: MA 042


Roland Wunderling
The kernel simplex method


The Simplex Method has stopped seeing major computational advances for years, yet it remains the most widely used algorithm for solving LPs; in particular the dual Simplex algorithm is used for MIP because of its warm-start capabilities. State-of-the-art MIP solvers use branch-and-cut algorithms, but the standard dual simplex algorithm only addresses the branching aspect of it. When cuts are added usually a fresh factorization of the basis matrix is needed which greatly reduces true warm-start support. Using a row basis or dualization can mitigate the issue, but this is only efficient for models with more rows than columns.
In this talk we introduce a new simplex algorithm, the kernel simplex method (KSM), which defines a kernel instead of a basis as the central data structure. KSM, provides full warm-starting functionality for row and column additions or deletions. We describe the algorithm and differentiate its computational properties against the traditional simplex method. Further, we show how KSM unifies primal and dual algorithms into one symmetric algorithm, thus matching duality theory much better than the traditional methods.


Talk 2 of the contributed session Mon.3.MA 042
"Linear optimization" [...]
Cluster 11
"Integer & mixed-integer programming" [...]


  Most online loan lenders allow getting New Jersey Loans Online without visiting a bank, straight to your bank account. Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Levitra, but also as part of its analogs.