Heuristic Methods for Linear Multiplicative Programming

The linear multiplicative programming is the minimization of the product of affine functions over a polyhedral set. The problem with two affine functions reduces to a parametric linear program and can be solved efficiently. For the objective function with more than two affine functions multiplied, no efficient algorithms that solve the problem to optimality have been proposed, however Benson and Boger have proposed a heuristic algorithm that exploits links of the problem with concave minimization and multicriteria optimization. We will propose a heuristic method for the problem as well as its modification to enhance the accuracy of approximation. Computational experiments demonstrate that the method and its modification solve randomly generated problems within a few percent of relative error.