Abstract
We first construct a "tight" parallelepiped R, containing 0 by using an arbitrary set of Q-conjugate directions and by solving 2n linear programs. We show that the convex envelope of x with respect to R is linear and obtain an explicit formula for it. We then describe a branch and bound algorithm in which the linearity of the convex envelope allows efficient lower bounding for the subproblems. For each sub problem we obtain the linear convex envelope of x over a smaller parallelepiped, R. Then, we obtain a lower bound by minimizing this convex envelope over R ' n 0 We show that the branch and bound algorithm converges to a feasible solution z e. Preliminary computational results are also presented.