G-2011-01
A simple finite simplicial covering algorithm for concave minimization over a polytope
référence BibTeX
We propose a conceptually simple, finite simplicial branch-and-bound algorithm for minimizing a concave function over a polytope. The proposed algorithm requires at each iteration the solution of two closely related linear programs of constant size for the computation of the lower bound and of the subdivision point; moreover, the objective function need to be evaluated only at extreme points of the polytope and of the initial simplex. Preliminary computational results are presented, which point to future improvements.
Paru en janvier 2011 , 16 pages
Document
G-2011-01.pdf (200 Ko)