A new branch-and-bound algorithm for generalized affine multiplicative programming

Yaping Deng and Peiping Shen ()
Additional contact information
Yaping Deng: North China University of Water Resources and Electric Power
Peiping Shen: North China University of Water Resources and Electric Power

Journal of Global Optimization, 2025, vol. 93, issue 1, No 4, 87-112

Abstract: Abstract In this paper, we consider a type of affine multiplicative programming (AMP) problem with exponents, which is known to be NP-hard. We initially transform AMP into an equivalent problem (EP) by the logarithmic transformation and the introduction of auxiliary variables. Utilizing a piecewise linear technique, we then develop a mixed-integer linear programming (MILP) relaxation to determine a lower bound for the optimal value of EP. In addition, we propose a successive linear optimization (SLO) method that converges to a KKT point of EP, thereby tightening the upper bound to the optimum of EP. Also, a rectangular contraction rule is introduced to eliminate regions that do not contain the optimal solution of AMP. By combining the MILP relaxation, the SLO method and the rectangular contraction rule, we formulate a new branch-and-bound algorithm for solving EP. Moreover, the convergence and the maximum number of iterations for the algorithm are presented. Finally, numerical experiments are conducted to verify the effectiveness and feasibility of the constructed algorithm.

Keywords: Affine multiplicative programming; Mixed-integer linear programming; Successive linear optimization method; Branch-and-bound; Rectangular contraction rule (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-025-01519-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:93:y:2025:i:1:d:10.1007_s10898-025-01519-z

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-025-01519-z

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().