Revisiting subgradient techniques applied to 3d linear assignment problem
Résumé
A subgradient technique which relies on a local approximation of AP3 polytope is proposed. On the one hand, it improves over standard subgradient enhanced with a whole class of facets, since it requires far less facets; furthermore, the selected facets are more accurate with respect to the gap between a relaxed solution and a feasible one. On the other hand, it compares favorably to Bundle-Trust method which is based on a subgradient approximation. Apart from this method, a Monge sequence is devised on a substructure local to relaxed/feasible gap, that affords us to recover from zig-zagging in some pathological cases.
Domaines
Autre [cs.OH]
Loading...