The colourful feasibility problem |
| |
Authors: | Antoine Deza,Tamá s Terlaky |
| |
Affiliation: | a Advanced Optimization Laboratory, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada L8S 4K1 b Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, BC, Canada V5A 1S6 |
| |
Abstract: | We study a colourful generalization of the linear programming feasibility problem, comparing the algorithms introduced by Bárány and Onn with new methods. This is a challenging problem on the borderline of tractability, its complexity is an open question. We perform benchmarking on generic and ill-conditioned problems, as well as recently introduced highly structured problems. We show that some algorithms can lead to cycling or slow convergence and we provide extensive numerical experiments which show that others perform much better than predicted by complexity arguments. We conclude that the most efficient method is a proposed multi-update algorithm. |
| |
Keywords: | 52C45 68W40 90C60 68Q25 |
本文献已被 ScienceDirect 等数据库收录! |
|