The paper presents an improved decomposition algorithm for solving the global optimization problem min{f(x)+c’Ty•Ax+By+b•0, x∈X, y∈Y∈, where X,Y are polyhedral convex sets in Rp,Rq, respectively and f is a continuous concave function over X (p is assumed to be small as compared to n=p+q). This algorithm is a variant of Tuy’s decomposition algorithm, with, however, a major improvement in the construction of the linear subproblems to be solved in each step. To take advantage of this improvement, the lay-out planning problem with concave cost and the case of bounded variable y are also considered.
