Groupe d’études et de recherche en analyse des décisions


A simple finite simplicial covering algorithm for concave minimization over a polytope

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.

, 16 pages