On improvements of multi-objective branch and bound
Branch and bound methods which are based on the principle “divide and conquer” are a well established solution approach in single-objective integer programming. In multi-objective optimization, branch and bound algorithms are increasingly attracting interest. However, the larger number of objectives...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-01-01
|
| Series: | EURO Journal on Computational Optimization |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2192440624000169 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850111121801871360 |
|---|---|
| author | Julius Bauß Sophie N. Parragh Michael Stiglmayr |
| author_facet | Julius Bauß Sophie N. Parragh Michael Stiglmayr |
| author_sort | Julius Bauß |
| collection | DOAJ |
| description | Branch and bound methods which are based on the principle “divide and conquer” are a well established solution approach in single-objective integer programming. In multi-objective optimization, branch and bound algorithms are increasingly attracting interest. However, the larger number of objectives raises additional difficulties for implicit enumeration approaches like branch and bound. Since bounding and pruning is considerably weaker in multiple objectives, many branches have to be (partially) searched and may not be pruned directly. The adaptive use of objective space information can guide the search in promising directions to determine a good approximation of the Pareto front already in early stages of the algorithm. In particular, we focus in this article on improving the branching and queuing of subproblems and the handling of lower bound sets.In our numerical tests, we evaluate the impact of the proposed methods in comparison to a standard implementation of multi-objective branch and bound on knapsack problems, generalized assignment problems and (un)capacitated facility location problems. |
| format | Article |
| id | doaj-art-a69666533d2d48e083dcfceed2ff6949 |
| institution | OA Journals |
| issn | 2192-4406 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | EURO Journal on Computational Optimization |
| spelling | doaj-art-a69666533d2d48e083dcfceed2ff69492025-08-20T02:37:41ZengElsevierEURO Journal on Computational Optimization2192-44062024-01-011210009910.1016/j.ejco.2024.100099On improvements of multi-objective branch and boundJulius Bauß0Sophie N. Parragh1Michael Stiglmayr2University of Wuppertal, School of Mathematics and Natural Sciences, Gauß str. 20, 42119 Wuppertal, GermanyJohannes Kepler University Linz, Institute of Production and Logistics Management / JKU Business School, Altenberger Str. 69, 4040 Linz, AustriaUniversity of Wuppertal, School of Mathematics and Natural Sciences, Gauß str. 20, 42119 Wuppertal, Germany; Corresponding author.Branch and bound methods which are based on the principle “divide and conquer” are a well established solution approach in single-objective integer programming. In multi-objective optimization, branch and bound algorithms are increasingly attracting interest. However, the larger number of objectives raises additional difficulties for implicit enumeration approaches like branch and bound. Since bounding and pruning is considerably weaker in multiple objectives, many branches have to be (partially) searched and may not be pruned directly. The adaptive use of objective space information can guide the search in promising directions to determine a good approximation of the Pareto front already in early stages of the algorithm. In particular, we focus in this article on improving the branching and queuing of subproblems and the handling of lower bound sets.In our numerical tests, we evaluate the impact of the proposed methods in comparison to a standard implementation of multi-objective branch and bound on knapsack problems, generalized assignment problems and (un)capacitated facility location problems.http://www.sciencedirect.com/science/article/pii/S2192440624000169Multi-objective optimizationBranch and boundInteger programmingAdaptive node selectionLower bound sets |
| spellingShingle | Julius Bauß Sophie N. Parragh Michael Stiglmayr On improvements of multi-objective branch and bound EURO Journal on Computational Optimization Multi-objective optimization Branch and bound Integer programming Adaptive node selection Lower bound sets |
| title | On improvements of multi-objective branch and bound |
| title_full | On improvements of multi-objective branch and bound |
| title_fullStr | On improvements of multi-objective branch and bound |
| title_full_unstemmed | On improvements of multi-objective branch and bound |
| title_short | On improvements of multi-objective branch and bound |
| title_sort | on improvements of multi objective branch and bound |
| topic | Multi-objective optimization Branch and bound Integer programming Adaptive node selection Lower bound sets |
| url | http://www.sciencedirect.com/science/article/pii/S2192440624000169 |
| work_keys_str_mv | AT juliusbauß onimprovementsofmultiobjectivebranchandbound AT sophienparragh onimprovementsofmultiobjectivebranchandbound AT michaelstiglmayr onimprovementsofmultiobjectivebranchandbound |