Output-Space Branch-and-Bound Reduction Algorithm for a Class of Linear Multiplicative Programs
In this paper, a new relaxation bounding method is proposed for a class of linear multiplicative programs. Although the <inline-formula> <math display="inline"> <semantics> <mrow> <mn>2</mn> <mi>p</mi> <mo>-</mo> <mn>1</m...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-03-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/8/3/315 |
| _version_ | 1818179105814740992 |
|---|---|
| author | Bo Zhang Yuelin Gao Xia Liu Xiaoli Huang |
| author_facet | Bo Zhang Yuelin Gao Xia Liu Xiaoli Huang |
| author_sort | Bo Zhang |
| collection | DOAJ |
| description | In this paper, a new relaxation bounding method is proposed for a class of linear multiplicative programs. Although the <inline-formula> <math display="inline"> <semantics> <mrow> <mn>2</mn> <mi>p</mi> <mo>-</mo> <mn>1</mn> </mrow> </semantics> </math> </inline-formula> variable is introduced in the construction of equivalence problem, the branch process of the algorithm is only carried out in <inline-formula> <math display="inline"> <semantics> <mrow> <mi>p</mi> <mo>-</mo> </mrow> </semantics> </math> </inline-formula>dimensional space. In addition, a super-rectangular reduction technique is also given to greatly improve the convergence rate. Furthermore, we construct an output-space branch-and-bound reduction algorithm based on solving a series of linear programming sub-problems, and prove the convergence and computational complexity of the algorithm. Finally, to verify the feasibility and effectiveness of the algorithm, we carried out a series of numerical experiments and analyzed the advantages and disadvantages of the algorithm by numerical results. |
| first_indexed | 2024-12-11T20:58:35Z |
| format | Article |
| id | doaj.art-8db354c5c6fb46c4a0589fe04b71e1fe |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-12-11T20:58:35Z |
| publishDate | 2020-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-8db354c5c6fb46c4a0589fe04b71e1fe2022-12-22T00:51:03ZengMDPI AGMathematics2227-73902020-03-018331510.3390/math8030315math8030315Output-Space Branch-and-Bound Reduction Algorithm for a Class of Linear Multiplicative ProgramsBo Zhang0Yuelin Gao1Xia Liu2Xiaoli Huang3School of Mathematics and Statistics, Ningxia University, Yinchuan 750021, ChinaNingxia Province Cooperative Innovation Center of Scientific Computing and Intelligent Information Processing, North Minzu University, Yinchuan 750021, ChinaSchool of Mathematics and Statistics, Ningxia University, Yinchuan 750021, ChinaNingxia Province Cooperative Innovation Center of Scientific Computing and Intelligent Information Processing, North Minzu University, Yinchuan 750021, ChinaIn this paper, a new relaxation bounding method is proposed for a class of linear multiplicative programs. Although the <inline-formula> <math display="inline"> <semantics> <mrow> <mn>2</mn> <mi>p</mi> <mo>-</mo> <mn>1</mn> </mrow> </semantics> </math> </inline-formula> variable is introduced in the construction of equivalence problem, the branch process of the algorithm is only carried out in <inline-formula> <math display="inline"> <semantics> <mrow> <mi>p</mi> <mo>-</mo> </mrow> </semantics> </math> </inline-formula>dimensional space. In addition, a super-rectangular reduction technique is also given to greatly improve the convergence rate. Furthermore, we construct an output-space branch-and-bound reduction algorithm based on solving a series of linear programming sub-problems, and prove the convergence and computational complexity of the algorithm. Finally, to verify the feasibility and effectiveness of the algorithm, we carried out a series of numerical experiments and analyzed the advantages and disadvantages of the algorithm by numerical results.https://www.mdpi.com/2227-7390/8/3/315global optimizationlinear multiplicative programmingbranch-and-boundoutput-spacelinear relaxation |
| spellingShingle | Bo Zhang Yuelin Gao Xia Liu Xiaoli Huang Output-Space Branch-and-Bound Reduction Algorithm for a Class of Linear Multiplicative Programs Mathematics global optimization linear multiplicative programming branch-and-bound output-space linear relaxation |
| title | Output-Space Branch-and-Bound Reduction Algorithm for a Class of Linear Multiplicative Programs |
| title_full | Output-Space Branch-and-Bound Reduction Algorithm for a Class of Linear Multiplicative Programs |
| title_fullStr | Output-Space Branch-and-Bound Reduction Algorithm for a Class of Linear Multiplicative Programs |
| title_full_unstemmed | Output-Space Branch-and-Bound Reduction Algorithm for a Class of Linear Multiplicative Programs |
| title_short | Output-Space Branch-and-Bound Reduction Algorithm for a Class of Linear Multiplicative Programs |
| title_sort | output space branch and bound reduction algorithm for a class of linear multiplicative programs |
| topic | global optimization linear multiplicative programming branch-and-bound output-space linear relaxation |
| url | https://www.mdpi.com/2227-7390/8/3/315 |
| work_keys_str_mv | AT bozhang outputspacebranchandboundreductionalgorithmforaclassoflinearmultiplicativeprograms AT yuelingao outputspacebranchandboundreductionalgorithmforaclassoflinearmultiplicativeprograms AT xialiu outputspacebranchandboundreductionalgorithmforaclassoflinearmultiplicativeprograms AT xiaolihuang outputspacebranchandboundreductionalgorithmforaclassoflinearmultiplicativeprograms |