Global optimization of multiplicative programs. (English) Zbl 1052.90091

The following two optimization problems are considered: Linear Multiplicative Problem (LMP); Generalized Linear Multiplicative Problem (GLMP). The LMP consists in finding the global minimum of the objective function, which is equal to the product of a finite number of linear functions, under linear constraints; it is assumed that all variables are bounded from below and from above and the linear functions in the objective function are positive over the whole set of feasible soluhons. The GLMP has the same set of feasible solutions as the LMP and its objective function is the sum of a finite number of functions, each of which has the same form as the objective function of the LMP, i.e., it is the product of a finite number of linear functions; unlike to LMP no assumption about the values of the linear functions involved in the objective function of the GMLP is made.
The primary contributions of the paper are:
(1) Global minimization algorithms that make possible for the first time to solve large-scale LMPs and GMLPs are developed;
(2) A new branching scheme that can be used in the context of any rectangular branch-and-bound algorithm is proposed.
Extensive computational experiments documenting the advantages of the developed algorithms are reported at the end of the paper.


90C30 Nonlinear programming
90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI