A finite branch-and-bound algorithm for linear multiplicative programming. (English) Zbl 0983.90075

Summary: On the basis of Soland’s rectangular branch and bound, we develop an algorithm for minimizing a product of \(p\) \((\geq 2)\) affine functions over a polytope. To tighten the lower bound on the value of each subproblem, we install a second-stage bounding procedure, which requires \(O(p)\) additional time in each iteration but remarkably reduces the number of branching operations. Computational results indicate that the algorithm is practical if \(p\) is less than 15, both in finding an exact optimal solution and an approximate solution.


90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C05 Linear programming
Full Text: DOI