|
|
 |
|
Vendredi 29 Novembre
| Heure: |
12:00 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Vector space decomposition for linear programming |
| Description: |
Jacques Desrosiers This presentation describes a vector space decomposition algorithm for
a linear program with bounded variables. Given a current feasible
solution, the exchange mechanism towards the next one is split into
independent parts based on two orthogonal vector subspaces, that is,
the master and the subproblem ones. The subproblem generates
directions (rays) compatible with the vector subspace of the master
problem. Indeed the subproblem partially satisfies the exchange
mechanism that is completed at the master level. Special cases of this
generic vector space decomposition algorithm are, amongst others, the
Primal Simplex, the Improved Primal Simplex yielding non-degenerate
pivots only, the Dynamic Constraints Aggregation method for the set
partitioning problem, and the strongly polynomial Minimum Mean
Cycle-Cancelling algorithm for the capacitated network flow problem. |
|
|
