Augmenting bi-objective branch and bound by scalarization-based information

Bauß, Julius; Stiglmayr, Michael Article — Published Version Augmenting bi-objective branch and bound by scalarization-based information Mathematical Methods of Operations Research Provided in Cooperation with: Springer Nature Suggested Citation: Bauß, Julius; Stiglmayr, Michael (2024) : Augmenting bi-objective branch and bound by scalarization-based information, Mathematical Methods of Operations Research, ISSN 1432-5217, Springer, Berlin, Heidelberg, Vol. 100, Iss. 1, pp. 85-121, https://doi.org/10.1007/s00186-024-00854-3 This Version is available at: https://hdl.handle.net/10419/314978 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Mathematical Methods of Operations Research (2024) 100:85–121 https://doi.org/10.1007/s00186-024-00854-3 ORIGINAL ARTICLE Augmenting bi-objective branch and bound by scalarization-based information Julius Bauß1·Michael Stiglmayr1 Received: 7 February 2023 / Revised: 10 January 2024 / Accepted: 10 February 2024 / Published online: 15 April 2024 © The Author(s) 2024 Abstract While branch and bound based algorithms are a standard approach to solve singleobjective (mixed-)integer optimization problems, multi-objective branch and bound methodsareonlyrarelyappliedcomparedtothepredominantobjectivespacemethods. In this paper we propose modifications to increase the performance of multi-objective branch and bound algorithms by utilizing scalarization-based information. We use the hypervolume indicator as a measure for the gap between lower and upper bound set to implement a multi-objective best-first strategy. By adaptively solving scalarizations in the root node to integer optimality we improve both, upper and lower bound set. The obtained lower bound can then be integrated into the lower bounds of all active nodes, while the determined solution is added to the upper bound set. Numerical experiments show that the number of investigated nodes can be significantly reduced by up to 83% and the total computation time can be reduced by up to 80%. Keywords Multi-objective optimization ·Multi-objective branch and bound ·Integer programming ·Hypervolume indicator 1 Introduction Many optimization problems occurring in real-word applications include a conflict of interests and goals, or secondary objectives, in a word, they are multi-objective. Thus, there is (in general) not one solution that optimizes all objectives at once. Following the Julius Bauß and Michael Stiglmayr have contributed equally to this work BJulius Bauß [email protected] Michael Stiglmayr [email protected] 1School of Mathematics and Natural Sciences, IMACM, University of Wuppertal, Gaußstr. 20, 42119 Wuppertal, Germany 123 86 J. Bauß, M. Stiglmayr a posteriori paradigm of decision making, we aim at determining the set of so-called efficient solutions or the images, the so-called non-dominated points, which cannot be improved in one objective without deterioration in at least one other objective. Thus, efficient solutions are reasonable choices for decision makers. As we are considering specifically bi-objective integer linear programs and their solution with multi-objective branch and bound methods, the following literature survey will also focus on this and closely related topics. A comprehensive introduction to multi-objective optimization in general is given, e.g., in Steuer (1986), Ehrgott (2005). Solution approaches for multi-objective optimization problems are often categorized in: objective space and decision space methods. Objective space methods scalarize the underlying problem, i.e., it is replaced by a series of single-objective problems to determine successively the set of efficient solutions. In the case of multi-objective integer programming, these scalarized problems can be solved with commercial integer programming solvers like CPLEX or Gurobi. The utilization of these optimized, single-criteria solvers are a major advantage and one of the reasons why those methods are predominant in multi-objective optimization. There are numerous objective space methods and a popular one is the ε-constraint method that was introduced for two objectives by Haimes et al. (1971). In every iteration the first objective is optimized with an updated constraint to ensure an improvement regarding the second objective. In Laumanns et al. (2006) an extension to three and more objectives is presented. Many approaches based on the ε-constraint method have been published in the last decades, for example Boland et al. (2017) and Kirlik and Sayın (2014) combine the method with reduction of dimension in the trirespectively multi-dimensional case. The weighted sum scalarization is an objective space method based on the optimization of a weighted sum of the objective functions using non-negative weights. Note that not all efficient solutions can be determined as optimal solutions of the weighted sum scalarization using suitable weights (see, e.g. Aneja and Nair 1979). Efficient solutions which can be obtained by using weighted sum scalarization are denoted as supported efficicent and their corresponding non-dominated points are located on the boundary of the convex hull of feasible image points. Extensions of the weighted sum method to the multi-objective case are proposed in Przybylski et al. (2010a), Özpeynirci and Köksalan (2010), Bökler and Mutzel (2015), and Przybylski et al. (2019). Ulungu and Teghem (1995) introduced the so-called two-phase method for biobjective problems. In the first phase the extreme supported non-dominated points are generated with an algorithm similar to the initial weighted sum approach. In the second phase the remaining non-dominated points are generated by searching in triangles defined by two consecutive extreme supported non-dominated points. In Przybylski et al. (2008) and Tuyttens et al. (2000) problem specific algorithms are suggested for the second phase, while in Przybylski et al. (2010b) a two-phase method for problems with more than two objectives is proposed. The augmented weighted Tchebycheff method, first presented in Steuer and Choo (1983), minimizes the augmented weighted Tchebycheff distance between a predefined reference point and the set of feasible image points. Dächert et al. (2012) suggested an adaptive choice of the augmentation term for the bi-objective case. 123 Augmenting bi-objective branch and bound 87 In Boland et al. (2015a), Boland et al. (2015b) (for the bi-objective case), Dächert and Klamroth (2014), and Klamroth et al. (2015) (for the trirespectively multiobjective case) search region splitting methods are proposed. In this class of objective space methods, the search region (based on the already determined non-dominated points) is splitted into so-called search zones on which scalarizations are solved indpendently. Besides their advantages, objective space methods share a shortcoming: In each iteration a scalarized integer program is solved from scratch. Even though in some objective space methods starting solutions can be transfered from previous iterations, a large number of very similar problems has to be solved. In order to avoid this effort, decision space methods, mainly the branch and bound method, have been increasingly investigated in the recent years. Klein and Hannan (1982) developed one of the first branch and bound algorithms for multi-objective integeger programs with a typical one tree structure. In Kiziltan and Yucao˘glu (1983) a general branch and bound framework for multi-objective integer programs with binary variables is presented. Ulungu and Teghem (1997) and Visée et al. (1998) proposed problem specific branch and bound approaches for bi-objective Knapsack problems, where the latter approach is integrated in a two-phase method. Mavrotas and Diakoulaki (1998) extend the branch and bound approach to multiobjective mixed integer programs. Parts of the algorithm are refined in Mavrotas and Diakoulaki (2005). In Vincent et al. (2013) this algorithm is improved and it is shown that the original algorithm is not correct because the final dominance test is incomplete. In Belotti et al. (2012) a branch and bound method is presented that can handle bi-objective mixed integer programs with continious variables in bothobjective functions. The branch and bound method proposed in Sourd and Spanjaard (2008) uses a set of points as lower bound instead of just using a single point. Furthermore hyperplanes are used to fathom nodes by dominance. In Stidsen et al. (2014) this idea is continued. They use hyperplanes as a lower bound set that are generated by solving weighted sum scalarizations. Additionally they present the so-called Pareto branching and the slicing technique. With Pareto branching it is possible to divide the objective space to possibly ignore parts of it in specific nodes. Slicing partitions the objective space in equally large parts and a respective slice can be fathomed if it is dominated by an already found integer point. In Stidsen and Andersen (2018)thisalgorithmisimproved and an approach to parallelize the algorithm is presented. Based on this, the idea Pareto branching is further investigated in Parragh and Tricoire (2019) and Gadegaard et al. (2019) for the bi-objective case and Forget et al. (2022) for the tri-objective case. A self-contained survey of multi-objective branch and bound approaches is given in Przybylski and Gandibleux (2017). Inthispaperwepresentabi-objectivebranchandboundalgorithmthatisaugmented by scalarization-based information. We make use of optimized single-objective solvers for scalar integer programs and integrate the resulting information into the bi-objective branch and bound by improving lower and upper bounds. Furthermore, we propose a new adaptive node selection strategy, which relies on objective space information. In our numerical analysis we show the effectiveness of these improvements by comparing 123 88 J. Bauß, M. Stiglmayr them with a generic multi-objective branch and bound algorithm, which we use as our baseline algorithm. The remainder of the article is organized as follows: In Sect.2, we introduce notations and definitions for multi-objective optimization. In Sect.3, we present a general multi-objective branch and bound framework and its key components. Furthermore, wedescribeaspecific(howeverstandard)multi-objectivebranchandboundalgorithm, which will be used as baseline implementation in our numerical tests. In Sect.4,we present augmentations of the multi-objective branch and bound, that utilize objective space information to improve the node selection as well as the computation of upper and lower bounds. We provide numerical results in Sect.5and in Sect.6, we outline conclusions and outlooks for further research. 2 Preliminaries We introduce a general multi-objective integer linear program which can be written in the form: min z1(x), . . . , zp(x) s.t.Ax ≤b x≥0 x∈Zn. (MOILP) Thereby, z(x):=(z1(x),...,zp(x))=C·x∈Rp(with p≥2) denotes the objective function vector, with C∈Rp×nthe matrix of objective coefficients. The set of feasible solutions X:={x∈Zn:A≤b,x≥0}is a subset of the decision space Rn, while its image Y:={Cx:x∈X}is a subset of the objective space Rp. We use the Pareto concept of optimality which relies on the componentwise order. Let y1,y2∈Rp, then we define the corresponding dominance relations as follows: •y1y2, i.e., y1weakly dominates y2if y1 k≤y2 kfor k=1,...,p, •y1<y2, i.e., y1strictly dominates y2if y1 k<y2 kfor k=1,...,p, •y1≤y2, i.e., y1dominates y2if y1y2and y1= y2. A feasible solution x∈Xis called efficient if there is no other solution ˆx∈X dominating it, i.e., z(ˆx)≤z(x). A feasible solution x∈Xis called weakly efficient if there is no ˆx∈Xsuch that z(ˆx)<z(x). The set of efficient solutions is denoted by XE.ByYN={z(x)∈Y:x∈XE}we denote the set of the non-dominated points in the objective space. Moreover, for any set Q⊆Rpwe denote by QNthe set of its non-dominated points (i.e., q∈QN⇐⇒ q∈Q:q≤q). For a comprehensive introduction to multi-objective optimization see, e.g., Ehrgott (2005). In this article we consider a minimal complete set as solution of a multi-objective optimization problem. A minimal complete set denotes the set of all non-dominated points YNand one efficient solution for each non-dominated point. See Serafini (1987) for a comparison of solution concepts in multi-objective optimization. 123 Augmenting bi-objective branch and bound 89 A standard solution approach in multi-objective optimization is the weighted sum scalarization given in (WSλ). min WSλ(x):=λz(x)= p  i=1 λizi(x) s.t.x∈X (WSλ) Obviously, every optimal solution of the weighted sum scalarization for λ∈ Rp >:={λ∈Rp:λ>0}is efficient for (MOILP). However, in general not all efficient solutions are optimal solutions of a corresponding weighted sum problem. An efficient solution x∈XEis called supported if there is a weighting vector λ∈Rp > such that xis optimal for (WSλ)forλ=λ, otherwise xis unsupported. Note that the non-dominated points corresponding to supported efficient solutions are located on the boundary of the convex hull of Y, while the unsupported non-dominated points are located in its (relative) interior. As already mentioned in the introduction the computation of upper and lower bounds on the non-dominated set is a crucial component of any multi-objective branch and bound algorithm. The tightest componentwise upper and lower bounds of YNare the ideal point yIand the Nadir point yNgiven by: yI k=min y∈Yykand yN k=max y∈YN ykfor k=1,...p. Obviously, yIyyNholds for every y∈YN, i.e., YNis contained in the hyperbox spanned by the corner points yIand yN. However, these single point bounds are in general very weak except for the degenerate case of yI=yN. This motivates to consider bound sets instead of bounds consisting of a single point. We will rely on the definition of bound sets proposed in Ehrgott and Gandibleux (2007). Let Rp :={y∈ Rp:y0}, then •Alower bound set L⊂Rpfor YNis a –Rp -closed (i.e., the set L+Rp is closed), –Rp -bounded (i.e., there exists a y∈Rpsuch that L⊂y+Rp ) – stable set (i.e., L⊂(L+Rp )N), such that YN⊂(L+Rp ). •An upper bound set U⊂Rpfor YNis a –Rp -closed, –Rp -bounded, – stable sets, such that YN⊂cl(U+Rp ). 123 90 J. Bauß, M. Stiglmayr The upper bound and lower bound that we will define for our branch and bound framework in Sect.3will suit these definitions. We say a lower bound Lis weakly dominated by an upper bound Uif for all l∈Lthere exists an u∈Usuch that ul. In the following we restrict ourselves to bi-objective binary linear optimization problems, i.e., problems with two linear objective functions and variables x∈{0,1}n: min z(x)=z1(x), z2(x) s.t. Ax ≤b x∈{0,1}n. (BO01LP) 3 A generic multi-objective branch and bound framework In this section we present a generic multi-objective branch and bound framework, which we specify and augment by using scalarization based information in the then following sections. Branchandboundmethodsfollowa “divideand conquer” paradigm. A problem that is too hard to be solved directly, is divided into smaller and thus easier subproblems. Thereby, subproblems are associated with nodes in a tree data structure according to their descent, i.e., node iis a descendant node of node jiff the feasible set of the subprobem associated with node iis a subset of the feasible set of the subproblem associated with node j. The corresponding subproblems of the child nodes are created by subdividing the feasible set of the corresponding (sub)problem of the parent node. Starting with the root node, to which the original optimization problem is associated, the algorithm selects in each iteration one active node and updates its lower bound and upper bound. Then the active node can be fathomed if the corresponding subproblem is either solved or irrelevant for the determination of a minimal complete set. If we cannot prune we subdivide the corresponding problem into new subproblems and create corresponding child nodes (branching). For a more detailed introduction and survey of multi-objective branch and bound algorithms see Przybylski and Gandibleux (2017). A recent survey of single-objective branch and bound frameworks is given e.g. in Morrison et al. (2016). In the following we specify the lower bound, upper bound, branching rule and node selection we use in our framework. Lower bound: Lower bound sets are often determined by solving relaxations of the respective subproblem. Like in the single-objective case, the most frequently used relaxations are linear and convex relaxations. In order to solve the linear relaxation we are using in our framework, we apply Benson’s outer approximation algorithm (Benson 1998; Ehrgott et al. 2012). The algorithm is initiated with a lower bound, whichisimproved in every iteration by generating cuts. Due to the outer approximation structure the algorithm can be aborted at any time returning a valid lower bound. Alternatively, linear(orconvex)relaxationscan beobtainedusingadichotomicscheme (see, for example, Aneja and Nair 1979; Özpeynirci and Köksalan 2010; Przybylski et al. 2010a). In the following we denote a lower bound set Las convex lower bound 123 Augmenting bi-objective branch and bound 91 set or convex lower bound if L+R2 ≥is a convex set. Note that the set Lis thereby not necessarily convex. Upper bound: The upper bound set, in the following denoted by U,isstoredintheform of a so-called incumbent list. Throughout the run of the algorithm, it contains all integer feasible solutions and their corresponding outcome vectors that are not dominated by another feasible solution found so far. In every iteration the extreme supported solutions of the computed lower bound sets are checked for integer feasibility. An integer feasible solution ¯x∈Xis then appended to the incumbent list, if there is no x∈Udominating ¯x,i.e.,C(x)≤C(¯x). If a new solution ¯xis added to the incumbent list Uall solutions x∈Uwhich are dominated by ¯x(C(¯x)≤C(x)) are removed from it, that is U{¯x}:= Uif ∃x∈U:C(x)≤C(¯x) {¯x}∪{x∈U:C(¯x)C(x)}otherwise. Note that an update of the incumbent list requires a subsequent update of the list of local upper bounds. A detailed description of local upper bounds, their computation and update in an arbitrary number of criteria is given in Klamroth et al. (2015). In this framework we start with an empty upper bound set. However, it is also possible to initialize the incumbent list by heuristic methods, or by solving scalarizations like, e.g., in the two-phase method (Ulungu and Teghem 1995; Visée et al. 1998). Node selection: In every iteration of the algorithm an unexplored node is selected from the tree of subproblems. This node is called active node. The order in which the nodes of the tree are considered has a significant impact on the number of created nodes that have to be explored and thus on the computation time. Twotypesof strategiesneedtobedistinguished:static strategiesand dynamic strategies. The two most common examples of static strategies are the depth-first strategy and the breadth-first strategy. Most multi-objective branch and bound algorithms in literature follow a depth-first strategy. Thus, we use this strategy for our baseline implementation as well. In contrast to the single-objective case, dynamic node selection strategies are rarely appliedinthemulti-objectivecase. Dynamic node selection strategiesare, for example, applied in Belotti et al. (2012), Stidsen et al. (2014), Jesus et al. (2021). Fathoming: In order to avoid the total enumeration of all feasible solutions, nodes are fathomed if the respective subproblem is either solved to optimality or does not contain solutions which are necessary to determine a minimal complete set. In particular, there are three different situations in which a node can be fathomed: i) Fathoming by infeasibility: If the LP-relaxation of a subproblem is infeasible then the corresponding subproblem is infeasible as well, since the feasible set of the subproblem is a subset of the feasible set of its relaxation. ii) Fathoming by optimality: Similar to the single-objective case we can fathom a node by optimality if the lower bound Lis equal to the upper bound U.This implies the subproblem is solved to optimality and the associated node must not be subdiveded further. However, this can happen in the multi-objective case only 123 92 J. Bauß, M. Stiglmayr if the lower and upper bound consist of the same single point, namely the ideal point. iii) Fathoming by dominance: A node can be fathomed by dominance if all feasible solutions of this subproblem are dominated by points in the incumbent list. In order to check dominance for all feasible outcome vectors of a subproblem we compare the lower bound Lof the corresponding node to the current upper bound U.Iffor all l∈Lthere is a point in the incumbent list u∈Uwith ulthen all feasible points in the subtree are dominated by the current incumbent list. In other words, if there is no local upper bound defined by Uabove the computed lower bound the node can be fathomed by dominance. Branching: As mentioned in the beginning of this section, one of the key aspects of branch and bound is iterative subdivision into smaller subproblems. Thereby subproblems are associated with nodes in a tree, such that the subproblem associated to a child node is obtained by one branching step. Since we consider binary optimization problems (BO01LP), we can divide a (sub)problem into two new subproblems by fixing a specific variable to 0 and respectively to 1 in the other subproblem. This results in a binary branch and bound tree. The branching rule determines which variable is selected as branching variable in each iteration. Thereby, one distinguishes between static and dynamic strategies. Static strategies determine an order of the variables in advance. In each iteration of the algorithm the next variable in this list is used as branching variable. With dynamic strategies the branching variable is selected by considering information obtained from previous iterations, i.e., from the solution of (linear) relaxations of (sub)problems. The basic idea of static strategies for single-objective problems is to sort the variables, beginning with the most promising according to the objective function values (see, e.g., Kellerer et al. 2004). However, this cannot be easily extended to the multiobjective case due to conflicting objective functions. Nevertheless there are some approaches to extend static strategies to the multi-objective case (see for example Ulungu and Teghem 1997; Bazgan et al. 2009). In contrast to most of the published papers which apply static strategies we use a dynamic strategy as proposed in Belotti et al. (2012). By solving the linear relaxation of a (sub)problem we obtain the lower bound set L. For all extreme points of Lwe check how often a variable is fractional in the corresponding solutions. As branching variable we choose the one which is most often fractional. 4 Using objective space information in multi-objective branch and bound In this section, we propose modifications which improve the computational efficiency of bi-objective branch and bound algorithms in two critical aspects. One of the weaknesses of multi-objective branch and bound as compared to its single-objective counterpart is the bounding procedure. While any feasible solution ¯x∈Xdominates w.r.t. one (linear) objective a half-space in decision space (i.e., {x∈Rn:cx≥c¯x}), the set of feasible solutions which are dominated by a solution ¯xin p≥2 objective 123 Augmenting bi-objective branch and bound 99 Fig. 3 Example of updating the lower and upper bound with the usage of the augmented weighted Tchebycheff scalarization that has not been found yet in Fig.3a. By using the local ideal point of z1and z2as the reference point s,Fig.3b illustrates how the non-dominated point z3is found by applying the augmented weighted Tchebycheff scalarization. In Fig.3c, d the resulting improvements of the lower and upper bound are shown. Obviously the lower bound is improved beyond the convex hull of YN. We now define our second hybrid branch and bound approach: Hybrid Branch and Bound Algorithm using Augmented Weighted Tchebycheff Scalarization •Lower bound: linear relaxation •Upper bound: incumbent list •Node selection: node with the biggest total/local hypervolume gap •Branching rule: most fractional 123 100 J. Bauß, M. Stiglmayr •Adaptively solve weighted sum and augmented weighted Tchebycheff scalarizations in the root node to integer optimality to improve lower and upper bounds by objective space information In addition to the weighted sum scalarization, we use the augmented weighted Tchebycheff scalarization. Since two adjacent non-dominated points are required as input of the augmented weighted Tchebycheff scalarization, we cannot rely on points intheincumbent list, which areonlynon-dominatedsofar.In fact,weapply augmented weighted Tchebycheff IP scalarizations only to boxes spanned by points obtained as optimal solutions of the weighted sum scalarization. Thus, we do not rely on parameters from the currently active node, but solve the augmented weighted Tchebycheff scalarization in the largest area defined by two adjacent known non-dominated points. When using augmented weighted Tchebycheff IP scalarizations, the lower bound can become tighter than the convex hull of the set of non-dominated points, which reduces the area where new non-dominated points can be found. Additionally, we can find non-supported non-dominated points in early stages of the algorithm. This improves the upper bound in the beginning resulting in a higher chance of fathoming a node by dominance. However, this also implies that the lower bound gets non-convex in general, which makes the fathoming tests significantly harder, and the lower bound improves only locally. 4.3 Algorithmic control of IP scalarizations In the previous subsections we did not specify when to solve IP scalarizations, which implies a significant computational cost itself. However, this might be the most crucial part within the presented methods. Obviously, we aim at gaining as much information as possible by solving IP scalarizations. More objective space information will lead to tighter bounds that reduce the number of created nodes, due to a higher probability of fathoming by dominance and smaller search zones. Moreover, a reduced number of created nodes will reduce the total computation time. At the same time, solving overly many IP scalarizations will have a negative impact on the computation time. Furthermore, at a certain point the lower and upper bound will not improve anymore when solving additional IP scalarizations. So, there exists a trade-off between the reduction of the number of created subproblems and the decrease of the computation time. The difficulty is to find an appropriate condition to trigger an IP scalarization. Obviously, solving IP scalarizations more frequently in the beginning of the branch and bound algorithm is very promising. The earlier the lower and upper bounds are improved the more nodes might be fathomed. Moreover, solving the IP scalarization when the active node has weak bounds will lead to stronger improvements than in later stages of the algorithm. This is complemented by our adaptive branching strategy, which tends to select subproblems with weak lower bounds first. The hybrid branch and bound algorithm using augmented weighted Tchebycheff scalarization entails also another problem. The augmented weighted Tchebycheff scalarization improves the lower bound just locally. If we use this scalarization at the beginning of the algorithm instead of the weighted sum scalarization, this could 123 Augmenting bi-objective branch and bound 101 lead to an increase of created nodes. Once again, the intuitive idea is to start with the weighted sum IP scalarization more frequently in the beginning of the algorithm. This ensures that the lower bound improves globally at early stages of the branch and bound. The augmented weighted Tchebycheff scalarization should be used in later stages of the algorithm to find non-supported non-dominated points and to improve the lower bound locally. The efficiency of this idea and other approaches will be shown in the next section where we present numerical test results. 5 Numerical results All algorithms were implemented in Julia 1.7.1 and the linear relaxations were solved with Bensolve 2.1 (Löhne and Weißing 2017). The numerical tests were executed on a single core of a 3.20 GHz Intel®Core™ i7-8700 CPU processor in a computer with 32 GB RAM, running under openSUSE linux Leap 15.3. We present numerical results of our new approaches and compare them to the general branch and bound framework presented in Sect.3which we use as baseline implementation. We consider three different types of problems: multidimensional knapsack problems, assignment problems and discrete facility location problems. The implementation of the proposed multiobjective branch and bound method and the considered benchmark instances are publicly available (Bauß and Stiglmayr 2023). Multiple combinations of parameter settings are used to solve these test problems. Thereby, we compare the average number of explored nodes, the average number of solved IPs and the average computation time for 20 instances per problem size. The different evaluated approaches are •the generic bi-objective Branch and Bouch (BB), •bi-objective branch and bound using the local (BS1) respectively global (BS2) hypervolume gap as node selection criterion, •hybrid branch and bound including weighted sum IP scalarizations (WS), and •different combinations of the hybrid branch and bound algorithm using weighted sum IP scalarization (M1.α.β) and hybrid branch and bound algorithm using weighted sum and augmented weighted Tchebycheff IP scalarization (M2.α.β.γ). The parameter α∈{1,2,3}controls how often IP scalarizations are applied. Since the number of IP scalarizations is chosen depending on the problem class, the meaning of the different values for αis described in detail in the corresponding subsections. In general, however, the larger the parameter αis chosen, the fewer IP scalarizations are solved. With βwe distinguish between the local (β=1) and the global (β=2) hypervolume gap strategy. In the hybrid branch and bound algorithm using augmented weighted Tchebycheff scalarization we also distinguish between integrating the objective space information of the augmented weighted Tchebycheff into the lower bound (γ=1) or not (γ=2). Note that the parameter values have been chosen based on preliminary results obtained from a different sets of instances, where they shown to provide good results. Thus, the parameter values are chosen depending on the problem class but are not 123 102 J. Bauß, M. Stiglmayr optimized w.r.t. the specific test instances. Hence, we avoid an instance depending fitting of the parameters to the data set. 5.1 Bi-objective multidimensional knapsack problems We consider bi-objective, multidimensional knapsack problems with one, two and three linear restrictions (i.e. m=1,2,3). For every problem size we randomly generate 20 instances of the form max n  i=1 ck ixik=1,2 s.t. n  i=1 wixi≤b n  i=1 vij xi≤djj=1,...,m−1 x∈{0,1}n with ck i∈[50,100],wi∈[5,15],b=5n,v ij ∈[5,15]and dj=rn 2with r∈[5,15]. Depending on the parameter αwe specify when and how often IP scalarizations are solved. In M1.1.βand WS we apply the weighted sum scalarization every 10-th iterations. In M1.2.βwe apply it every 10-th iteration but only within the first n2iterations. In M1.3.βwe apply the weighted sum scalarization every 10-th iteration within the first n2/3 iterations, every n-th iteration within the next n2/3 iterations and every 2n-th iteration within the third n2/3 iterations. In M2.1.β.γwe apply the weighted sum scalarization every 10-th iteration and every 50-th iteration the augmented weighted Tchebycheff scalarization is used instead. In M2.2.β.γwe operate likeinM1.2.βbutafterthefirstn2iterationsweapplytheaugmentedweightedTcheby- cheff scalarization every 50-th iteration. In M2.3.β.γwe operate like in M1.3.βbut after the first n2iterations we apply the augmented weighted Tchebycheff scalarization every 50-th iteration. If a scalarization cannot be applied or the same IP scalarization has already been solved before, no IP scalarization is solved in that iteration. Firstof all, we notice that our branching strategieshavea huge impact on the number of explored nodes and the computation time in knapsack problems. We observe that in general the local hypervolume gap strategy works better than the global hypervolume gap strategy. With the local strategy we can reduce the number of explored nodes by up to 76% (Table 1c, b) and the computation time by up to 73% (Table 1c). Although the local strategy works better the global hypervolume gap strategy has also a significant impact. The number of explored nodes can be reduced by up to 58% (Table 2c) and the computation time by up to 52% (Table 2c). The number of nodes and the computation time is reduced in all our approaches and we can notice that combinations with the local hypervolume strategy work better. By limiting the number of solved weighted sum IPs (i.e. in M1.2.β, M1.3.β, M2.2.β.γand M2.3.β.γ) we notice two consequences. The number of nodes increases while the number of solved IPs decreases. Although the number of nodes (and thus 123 Augmenting bi-objective branch and bound 103 Table 1 Numerical results of the bi-objective, multidimensional knapsack problems (a) Knapsack problem, m=1,n=50 Version Nodes Time (s) Solved IPs BB 27916.3 18.153 0.0 BS1 11788.1 8.339 0.0 WS 14270.7 10.507 33.75 M1.1.1 10789.7 8.452 26.4 M1.2.1 10793.5 8.188 21.2 M1.3.1 10795.7 8.116 17.95 M2.1.1.1 9888.5 10.873 48.7 M2.2.1.1 10140.3 9.437 32.65 M2.3.1.1 10521.0 8.774 25.65 M2.1.1.2 9840.1 8.396 45.55 M2.2.1.2 10130.6 8.422 32.35 M2.3.1.2 10401.8 8.288 26.25 BS2 16739.8 11.397 0.0 M1.1.2 11026.3 8.861 26.1 M1.2.2 11024.5 8.860 19.85 M1.3.2 11047.4 8.645 16.05 M2.1.2.1 10071.8 10.907 45.85 M2.2.2.1 10421.4 9.587 31.8 M2.3.2.1 10583.2 9.448 24.45 M2.1.2.2 9994.1 8.940 46.65 M2.2.2.2 10413.4 8.820 32.55 M2.3.2.2 10568.9 8.727 25.15 (b) Knapsack problem, m=1,n=80 Version Nodes Time (s) Solved IPs BB 153938.9 186.330 0.0 BS1 36392.0 50.952 0.0 WS 58825.7 79.545 54.0 M1.1.1 34337.7 50.431 41.65 M1.2.1 34333.9 50.312 33.1 M1.3.1 34307.1 50.505 26.35 M2.1.1.1 31643.7 81.625 100.2 M2.2.1.1 32708.9 68.939 76.2 M2.3.1.1 32986.3 69.848 63.6 M2.1.1.2 31274.5 46.721 102.85 M2.2.1.2 32795.7 48.576 76.3 M2.3.1.2 33025.8 48.358 63.4 123 104 J. Bauß, M. Stiglmayr Table 1 continued (b) Knapsack problem, m=1,n=80 Version Nodes Time (s) Solved IPs BS2 90976.0 116.847 0.0 M1.1.2 39745.1 59.321 45.25 M1.2.2 40083.2 59.350 31.2 M1.3.2 39918.1 58.999 24.5 M2.1.2.1 31905.8 80.505 99.7 M2.2.2.1 34496.9 79.444 84.0 M2.3.2.1 34571.7 72.955 65.15 M2.1.2.2 32074.9 48.510 104.85 M2.2.2.2 34169.8 51.464 87.15 M2.3.2.2 34943.3 51.887 63.1 (c) Knapsack problem, m=1,n=100 Version Nodes Time (s) Solved IPs BB 297345.3 484.676 0.0 BS1 68920.5 128.967 0.0 WS 128080.8 224.587 66.95 M1.1.1 67369.1 128.665 54.1 M1.2.1 67370.1 128.924 39.95 M1.3.1 67353.3 128.993 32.9 M2.1.1.1 58214.2 198.683 156.85 M2.2.1.1 61533.1 179.516 123.0 M2.3.1.1 62127.3 177.621 104.55 M2.1.1.2 58151.3 112.575 158.1 M2.2.1.2 61490.6 118.600 120.1 M2.3.1.2 61762.6 118.306 108.65 BS2 187306.9 318.524 0.0 M1.1.2 73766.2 144.684 54.75 M1.2.2 74065.4 144.677 37.9 M1.3.2 73865.0 144.306 31.0 M2.1.2.1 59512.7 200.754 158.05 M2.2.2.1 64489.2 192.211 127.0 M2.3.2.1 64330.5 187.803 114.65 M2.1.2.2 60470.8 118.479 157.75 M2.2.2.2 64943.8 127.428 123.5 M2.3.2.2 64711.1 126.525 113.5 (d) Knapsack problem, m=2,n=50 Version Nodes Time (s) Solved IPs BB 32655.6 25.8684 0.0 BS1 10982.3 9.6578 0.0 123 Augmenting bi-objective branch and bound 105 Table 1 continued (d) Knapsack problem, m=2,n=50 Version Nodes Time (s) Solved IPs WS 14180.9 13.1749 33.25 M1.1.1 9784.7 9.5159 26.6 M1.2.1 9782.5 9.2684 19.65 M1.3.1 9791.1 9.1580 14.85 M2.1.1.1 8900.7 12.6639 47.75 M2.2.1.1 9407.5 11.5112 34.5 M2.3.1.1 9507.5 11.0256 24.8 M2.1.1.2 8892.9 9.2702 47.0 M2.2.1.2 9370.2 9.2053 33.05 M2.3.1.2 9484.3 9.1161 24.75 BS2 15639.2 13.1246 0.0 M1.1.2 10665.3 10.8423 28.5 M1.2.2 10671.3 10.5141 19.4 M1.3.2 10854.2 10.5765 15.7 M2.1.2.1 9045.3 12.8916 48.9 M2.2.2.1 9629.7 12.1913 34.9 M2.3.2.1 9814.7 11.6068 28.1 M2.1.2.2 9030.0 9.5854 48.2 M2.2.2.2 9608.5 9.7621 36.05 M2.3.2.2 9787.6 9.6722 28.35 the number of considered subproblems) is increasing, the total computation time decreases. This implies that the reduced computation time to solve IP scalarizations compensates the increase of nodes, which results in a trade-off between the number of explored nodes and the computation time. Another interesting aspect can be observed in M2.α.β.1 and M2.α.β.2. The computation time can be reduced if we do not integrate the augmented weighted Tchebycheff objective level set into the lower bound. This can be explained by the fact that the lower bound improvements of augmented weighted Tchebycheff are only local and do not compensate the computation time needed to integrate the information. The intuitive assumption that the number of explored nodes will then rise significantly is false. So, both our branching strategies work better, if we do not consider the local updates of the lower bound. We can reach a reduction of the explored nodes by up to 83% (Table 2b) and a reduction of the computation time by up to 80% (Table 2b) in the best case. The strategies M2.1.1.1 and M2.1.1.2 seem to work best for knapsack problems. In most cases these two strategies have the largest impact on the number of explored nodes. Nevertheless, M2.1.1.2 achieves for all instance sizes the best computation times, since computation time is saved by not integrating the augmented weighted Tchebycheff objective space information into the lower bound. Note that with rising numbers of variables 123 106 J. Bauß, M. Stiglmayr Table 2 Numerical results of the bi-objective, multidimensional knapsack problems (a) Knapsack problem, m=2,n=80 Version Nodes Time (s) Solved IPs BB 159911.4 287.925 0.0 BS1 41092.0 88.121 0.0 WS 63215.0 130.338 55.0 M1.1.1 37799.1 82.654 43.9 M1.2.1 37835.8 82.544 30.55 M1.3.1 37811.3 82.369 24.75 M2.1.1.1 31615.0 115.164 102.55 M2.2.1.1 34772.5 102.965 72.5 M2.3.1.1 35127.1 100.706 60.6 M2.1.1.2 31590.2 69.290 104.7 M2.2.1.2 34977.7 77.063 72.45 M2.3.1.2 35170.3 77.279 61.3 BS2 115223.3 224.926 0.0 M1.1.2 43581.8 97.039 47.8 M1.2.2 43744.8 97.874 29.1 M1.3.2 45481.1 102.689 23.45 M2.1.2.1 32388.8 116.173 106.25 M2.2.2.1 36453.2 120.161 78.3 M2.3.2.1 35942.7 116.972 69.05 M2.1.2.2 33264.8 74.207 104.75 M2.2.2.2 36578.1 81.915 77.2 M2.3.2.2 35505.1 77.971 69.55 (b) Knapsack problem, m=2,n=100 Version Nodes Time (s) Solved IPs BB 428526.3 1074.21 0.0 BS1 100962.6 326.98 0.0 WS 166108.1 464.71 67.25 M1.1.1 98831.5 323.54 54.8 M1.2.1 99313.5 325.32 38.95 M1.3.1 98770.6 322.65 32.6 M2.1.1.1 69951.9 402.48 149.35 M2.2.1.1 73433.8 379.33 119.6 M2.3.1.1 73424.7 371.63 102.95 M2.1.1.2 70172.3 212.40 153.15 M2.2.1.2 72824.8 219.73 121.55 M2.3.1.2 73651.5 221.96 107.5 123 Augmenting bi-objective branch and bound 107 Table 2 continued (b) Knapsack problem, m=2,n=100 Version Nodes Time (s) Solved IPs BS2 271110.8 720.46 0.0 M1.1.2 113605.9 381.46 57.45 M1.2.2 117188.3 394.57 36.45 M1.3.2 113665.3 378.63 29.85 M2.1.2.1 70603.0 404.28 150.8 M2.2.2.1 77836.0 400.18 121.4 M2.3.2.1 76818.2 399.89 110.8 M2.1.2.2 72316.9 219.91 148.4 M2.2.2.2 78135.2 240.57 121.3 M2.3.2.2 77073.0 235.49 112.45 (c) Knapsack problem, m=3,n=50 Version Nodes Time (s) Solved IPs BB 54430.4 51.5026 0.0 BS1 15260.1 17.9276 0.0 WS 18112.9 20.5208 36.2 M1.1.1 13522.4 16.8431 28.8 M1.2.1 13530.7 16.4735 19.0 M1.3.1 13576.5 16.4442 14.95 M2.1.1.1 12345.3 22.1289 51.15 M2.2.1.1 12973.5 19.7592 34.5 M2.3.1.1 13014.0 19.6348 28.8 M2.1.1.2 12241.1 16.1190 53.55 M2.2.1.2 12934.3 16.2933 35.15 M2.3.1.2 12908.3 16.1009 30.35 BS2 22597.3 24.5736 0.0 M1.1.2 14645.7 18.6425 29.55 M1.2.2 14573.2 18.0521 16.75 M1.3.2 14597.0 17.9793 14.5 M2.1.2.1 12617.9 22.3518 54.65 M2.2.2.1 13324.9 20.7655 33.4 M2.3.2.1 13252.3 20.4366 30.55 M2.1.2.2 12682.4 16.8670 56.65 M2.2.2.2 13180.2 16.7601 33.6 M2.3.2.2 13274.4 16.8497 32.15 (d) Knapsack problem, m=3,n=80 Version Nodes Time (s) Solved IPs BB 263971.6 724.999 0.0 BS1 81609.9 287.899 0.0 123 108 J. Bauß, M. Stiglmayr Table 2 continued (d) Knapsack problem, m=3,n=80 Version Nodes Time (s) Solved IPs WS 121360.8 376.247 56.4 M1.1.1 80406.5 282.897 47.35 M1.2.1 79971.5 279.885 32.2 M1.3.1 80089.6 279.686 26.55 M2.1.1.1 54187.1 340.389 115.7 M2.2.1.1 55915.9 328.411 85.45 M2.3.1.1 58486.8 330.347 66.9 M2.1.1.2 53396.0 164.755 116.0 M2.2.1.2 56572.6 174.131 86.25 M2.3.1.2 57452.9 176.657 67.85 BS2 140681.4 390.578 0.0 M1.1.2 92175.8 334.414 50.45 M1.2.2 96339.3 350.148 29.05 M1.3.2 96099.5 348.915 24.0 M2.1.2.1 54119.5 349.261 112.5 M2.2.2.1 59379.8 344.899 89.1 M2.3.2.1 60326.6 349.874 74.15 M2.1.2.2 54595.6 176.090 119.65 M2.2.2.2 62851.9 211.373 88.9 M2.3.2.2 61200.8 205.413 76.6 and constraints the hybridization techniques have larger impact on the performance of the branch and bound algorithm. 5.2 Bi-objective assignment problems We consider bi-objective assignment problems having n=2variables, max   i=1   j=1 ck ij xij k=1,2 s.t.   i=1 xij =1j=1,...,   j=1 xij =1i=1,..., x∈{0,1}× where the cost coefficients ck ij ∈[50,100]. The algorithmic strategy for the solution of IP scalarizations depending on the value of the parameter αis chosen similarly to 123 Augmenting bi-objective branch and bound 115 Table 4 continued (b) Facility location problem n=84 Version Nodes Time (s) Solved IPs BS2 7084.4 11.5822 0.0 M1.1.2 4873.8 8.7719 26.35 M1.2.2 4874.8 8.7534 17.45 M1.3.2 4894.1 8.7031 12.6 M2.1.2.1 4673.6 9.5755 49.65 M2.2.2.1 4832.0 8.9275 23.6 M2.3.2.1 4812.8 8.8050 17.4 M2.1.2.2 4628.9 8.7019 46.15 M2.2.2.2 4825.9 8.7491 24.4 M2.3.2.2 4807.5 8.5984 17.5 (c) Facility location problem n=130 Version Nodes Time (s) Solved IPs BB 17461.9 51.6307 0.0 BS1 10684.0 34.5157 0.0 WS 16795.9 50.9317 51.35 M1.1.1 10753.9 35.4356 37.1 M1.2.1 10753.9 35.2764 25.5 M1.3.1 10753.9 35.1007 19.15 M2.1.1.1 10104.4 38.3909 89.65 M2.2.1.1 10678.1 35.7434 39.35 M2.3.1.1 10722.3 35.6262 27.7 M2.1.1.2 10103.0 34.5003 85.95 M2.2.1.2 10691.2 35.3730 39.05 M2.3.1.2 10718.6 35.1690 27.45 BS2 15474.7 46.5130 0.0 M1.1.2 11548.8 38.4891 39.3 M1.2.2 11601.4 38.5848 24.6 M1.3.2 11535.1 38.2917 18.0 M2.1.2.1 10684.3 39.8639 81.5 M2.2.2.1 11381.8 39.1988 37.15 M2.3.2.1 11336.0 38.7754 28.45 M2.1.2.2 10695.5 36.9098 78.25 volume gap strategy chooses the node with the largest search zone, which has the biggest potential to reduce this gap. Moreover, the local hypervolume gap strategy aims at an uniform distribution of points in the incumbent list. In our numerical test, M2.1.1.2 turn out to be the best choice in most cases with respect to the number of explored nodes and computation time. In this version, we use the local hypervolume gap strategy for the choice of the active node, every 10-th iteration the weighted sum 123 116 J. Bauß, M. Stiglmayr Table 4 continued (c) Facility location problem n=130 Version Nodes Time (s) Solved IPs M2.2.2.2 11341.6 38.2646 39.55 M2.3.2.2 11352.1 38.0063 25.9 (d) Facility location problem n=186 Version Nodes Time (s) Solved IPs BB 67369.3 373.238 0.0 BS1 31844.1 203.145 0.0 WS 62192.8 349.741 69.95 M1.1.1 32106.6 206.244 53.05 M1.2.1 32097.9 206.851 33.4 M1.3.1 32148.5 207.199 23.75 M2.1.1.1 28384.2 224.486 186.8 M2.2.1.1 31074.5 218.314 101.15 M2.3.1.1 32004.8 209.608 50.1 M2.1.1.2 28558.8 186.010 172.7 M2.2.1.2 30946.4 202.329 97.75 M2.3.1.2 32011.8 207.715 47.5 BS2 50759.0 292.344 0.0 M1.1.2 35150.1 230.687 55.5 M1.2.2 35789.8 233.967 30.8 M1.3.2 35255.0 233.163 21.95 M2.1.2.1 29704.3 230.016 172.65 M2.2.2.1 33959.7 236.351 81.75 M2.3.2.1 34228.0 233.553 50.2 M2.1.2.2 30412.6 202.719 167.4 M2.2.2.2 34511.8 229.970 69.95 M2.3.2.2 34405.0 229.021 47.1 IP scalarization is applied and every 50-th iteration we apply the augmented weighted Tchebycheff scalarization instead. Futhermore, the objective space information gained by the augmented weighted Tchebycheff scalarization is not used to update the lower bound set, since its local improvements do not compensate the increased computation time. Although we need to solve more IPs than in most other approaches, the computation time is the lowest compared to the others. So, using the augmented weighted Tchebycheff scalarization in the beginning of the branch and bound works best. Due to the likelihood of finding non-supported non-dominated points in the early stages of the algorithm, the upper bound can be further improved. This results to a higher probability of fathoming a node by dominance. Nevertheless, with version BS1 we also achive a remarkable reduction in terms of the number of explored nodes and computation time by using the local hypervolume gap strategy for node selection. 123 Augmenting bi-objective branch and bound 117 Fig. 4 Visualization of branch and bound node reduction and runtime reduction for varying test instance sizes on a selection of approaches 123 118 J. Bauß, M. Stiglmayr 6 Conclusion and outlook In this paper, we propose two approaches to incorporate objective space information in bi-objective branch and bound. By using the local or global (approximated) hypervolume gap as a node selection criterion, we adapt the run of the branch and bound algorithm to the problem instance. Additionally, we adaptively solve scalarizations to integer optimality to improve the lower and the upper bound set by the obtained objective space information. Our numerical results show the effectiveness of both approaches and in particular of their combination. The dynamic branching rule based on the local (approximated) hypervolume gap has large impact on the number of explored subproblems, is compuationally efficient and can be easily integrated in other multi-objective branch and bound algorithms. While we tested in this paper the individual contributions of our augmentations on a generic bi-objective branch and bound, we will continue to extend our ideas to multiple dimensions and integrate them into a competetive multi-objective branch and bound framework. Particularly in higher dimensions, it may be promising to combine our approaches with objective space branching. Funding Open Access funding enabled and organized by Projekt DEAL. The authors thankfully acknowledge financial support by Deutsche Forschungsgemeinschaft, Project Number KL 1076/11-1. Data availability The implementation in Julia and the used test datasets are available in Git repository https://git.uni-wuppertal.de/bauss/augmented-bi-objective-branch-and-bound. Declarations Conflict of interest The authors have no competing interests to declare that are relevant to the content of this article. Open Access This articleislicensedunderaCreativeCommonsAttribution4.0InternationalLicense,which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References Aneja YP, Nair KPK (1979) Bicriteria transportation problem. Manag Sci 25(1):73–78. https://doi.org/10. 1287/mnsc.25.1.73 Bauß J, Stiglmayr M (2023) Augmented Bi-objective Branch and Bound. Git repository. https://git.uniwuppertal.de/bauss/augmented-bi-objective-branch-and-bound Bazgan C, Hugot H, Vanderpooten D (2009) Solving efficiently the 0–1 multi-objective knapsack problem. Comput Oper Res 36(1):260–279. https://doi.org/10.1016/j.cor.2007.09.009 Belotti P, Soylu B, Wiecek MM (2012) A branch-and-bound algorithm for biobjective mixed-integer programs. Technical report. https://optimization-online.org/?p=12266 123 Augmenting bi-objective branch and bound 119 Benson HP (1998) An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem. J Glob Optim 13(1):1–24. https:// doi.org/10.1023/A:1008215702611 Bökler F, Mutzel P (2015) Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems. In: Algorithms—ESA 2015. Springer, Berlin, pp 288–299. https://doi.org/10.1007/978-3-662-48350-3_25 Boland N, Charkhgard H, Savelsbergh M (2015a) A criterion space search algorithm for biobjective integer programming: the balanced box method. INFORMS J Comput 27(4):735–754. https://doi.org/10. 1287/ijoc.2015.0657 Boland N, Charkhgard H, Savelsbergh M (2015b) A criterion space search algorithm for biobjective mixed integer programming: the triangle splitting method. INFORMS J Comput 27(4):597–618. https://doi. org/10.1287/ijoc.2015.0646 Boland N, Charkhgard H, Savelsbergh M (2017) The quadrant shrinking method: a simple and efficient algorithm for solving tri-objective integer programs. Eur J Oper Res 260(3):873–885. https://doi.org/ 10.1016/j.ejor.2016.03.035 Dächert K, Klamroth K (2014) A linear bound on the number of scalarizations needed to solve discrete tricriteria optimization problems. J Glob Optim 61(4):643–676. https://doi.org/10.1007/s10898-014- 0205-z Dächert K, Gorski J, Klamroth K (2012) An augmented weighted Tchebycheff method with adaptively chosen parameters for discrete bicriteria optimization problems. Comput Oper Res 39(12):2929–2943. https://doi.org/10.1016/j.cor.2012.02.021 DechterR,PearlJ(1985)Generalizedbest-firstsearchstrategiesandtheoptimalityofA∗.JACM32(3):505– 536. https://doi.org/10.1145/3828.3830 Ehrgott M (2005) Multicriteria Optimization. Springer, Berlin. https://doi.org/10.1007/3-540-27659-9 Ehrgott M, Gandibleux X (2007) Bound sets for biobjective combinatorial optimization problems. Comput Oper Res 34(9):2674–2694. https://doi.org/10.1016/j.cor.2005.10.003 Ehrgott M, Löhne A, Shao L (2012) A dual variant of Benson’s “outer approximation algorithm” for multiple objective linear programming. J Glob Optim 52:757–778 Forget N, Gadegaard SL, Klamroth K, Nielsen LR, Przybylski A (2022) Branch-and-bound and objective branching with three or more objectives. Comput Oper Res 148:106012. https://doi.org/10.1016/j.cor. 2022.106012 GadegaardSL,NielsenLR,EhrgottM(2019)Bi-objectivebranch-and-cutalgorithmsbasedonLPrelaxation and bound sets. INFORMS J Comput 31(4):790–804. https://doi.org/10.1287/ijoc.2018.0846 Haimes Y, Lasdon L, Wismer D (1971) On a bicriterion formation of the problems of integrated system identification and system optimization. IEEE Trans Syst Man Cybernet. https://doi.org/10.1109/TSMC. 1971.4308298 Jesus AD, Paquete L, Derbel B, Liefooghe A (2021) On the design and anytime performance of indicatorbased branch and bound for multi-objective combinatorial optimization. In: Proceedings of the genetic and evolutionary computation conference. ACM, Lille. https://doi.org/10.1145/3449639.3459360 Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin. https://doi.org/10.1007/ 978-3-540-24777-7 Kirlik G, Sayın S (2014) A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems. Eur J Oper Res 232(3):479–488. https://doi.org/10.1016/j.ejor.2013. 08.001 Kiziltan G, Yucao˘glu E (1983) An algorithm for multiobjective zero-one linear programming. Manag Sci 29(12):1444–1453. https://doi.org/10.1287/mnsc.29.12.1444 Klamroth K, Lacour R, Vanderpooten D (2015) On the representation of the search region in multi-objective optimization. Eur J Oper Res 245(3):767–778. https://doi.org/10.1016/j.ejor.2015.03.031 Klein D, Hannan E (1982) An algorithm for the multiple objective integer linear programming problem. Eur J Oper Res 9(4):378–385. https://doi.org/10.1016/0377-2217(82)90182-5 LaumannsM, Thiele L, ZitzlerE (2006) Anefficient,adaptiveparametervariationschemefor metaheuristics based on the epsilon-constraint method. Eur J Oper Res 169(3):932–942. https://doi.org/10.1016/j. ejor.2004.08.029 Löhne A, Weißing B (2017) The vector linear program solver bensolve—notes on theoretical background. Eur J Oper Res 260(3):807–813. https://doi.org/10.1016/j.ejor.2016.02.039 123 120 J. Bauß, M. Stiglmayr Mavrotas G, Diakoulaki D (1998) A branch and bound algorithm for mixed zero-one multiple objective linear programming. Eur J Oper Res 107(3):530–541. https://doi.org/10.1016/s0377-2217(97)00077- 5 Mavrotas G, Diakoulaki D (2005) Multi-criteria branch and bound: a vector maximization algorithm for mixed 0–1 multiple objective linear programming. Appl Math Comput 171(1):53–71. https://doi.org/ 10.1016/j.amc.2005.01.038 Miettinen K (1998) Nonlinear multiobjective optimization. Springer, New York. https://doi.org/10.1007/ 978-1-4615-5563-6 Morrison DR, Jacobson SH, Sauppe JJ, Sewell EC (2016) Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning. Discret Optim 19:79–102. https://doi.org/10.1016/j. disopt.2016.01.005 Özpeynirci Ö, Köksalan M (2010) An exact algorithm for finding extreme supported nondominated pointsof multiobjective mixed integer programs. Manag Sci 56(12):2302–2315. https://doi.org/10.1287/mnsc. 1100.1248 Parragh SN, Tricoire F (2019) Branch-and-bound for bi-objective integer programming. INFORMS J Comput 31(4):805–822. https://doi.org/10.1287/ijoc.2018.0856 Przybylski A, Gandibleux X (2017) Multi-objective branch and bound. Eur J Oper Res 260(3):856–872. https://doi.org/10.1016/j.ejor.2017.01.032 Przybylski A, Gandibleux X, Ehrgott M (2008) Two phase algorithms for the bi-objective assignment problem. Eur J Oper Res 185(2):509–533. https://doi.org/10.1016/j.ejor.2006.12.054 Przybylski A, Gandibleux X, Ehrgott M (2010a) A recursive algorithm for finding all nondominated extreme points in the outcome set of a multiobjective integer programme. INFORMS J Comput 22(3):371–386. https://doi.org/10.1287/ijoc.1090.0342 Przybylski A, Gandibleux X, Ehrgott M (2010b) A two phase method for multi-objective integer programminganditsapplicationtotheassignmentproblemwiththreeobjectives.Discrete Optim 7(3):149–165. https://doi.org/10.1016/j.disopt.2010.03.005 Przybylski A, Klamroth K, Lacour R (2019) A simple and efficient dichotomic search algorithm for multiobjective mixed integer linear programs. arXiv. https://doi.org/10.48550/ARXIV.1911.08937 Serafini P (1987) Some considerations about computational complexity for multi objective combinatorial problems. In: Recent advances and historical development of vector optimization. Springer, Berlin, pp 222–232. https://doi.org/10.1007/978-3-642-46618-2_15 Sourd F, Spanjaard O (2008) A multiobjective branch-and-bound framework: application to the biobjective spanning tree problem. INFORMS J Comput 20(3):472–484. https://doi.org/10.1287/ijoc.1070.0260 Steuer RE (1986) Multiple criteria optimization: theory, computation and application. Wiley, New York. https://doi.org/10.1002/oca.4660100109 Steuer RE, Choo E-U (1983) An interactive weighted Tchebycheff procedure for multiple objective programming. Math Program 26(3):326–344. https://doi.org/10.1007/BF02591870 Stidsen T, Andersen KA (2018) A hybrid approach for biobjective optimization. Discret Optim 28:89–114. https://doi.org/10.1016/j.disopt.2018.02.001 Stidsen T, Andersen KA, Dammann B (2014) A branch and bound algorithm for a class of biobjective mixed integer programs. Manag Sci 60(4):1009–1032. https://doi.org/10.1287/mnsc.2013.1802 Tuyttens D, Teghem J, Fortemps P, Nieuwenhuyze KV (2000) Performance of the MOSA method for the bicriteria assignment problem. J Heurist 6(3):295–310. https://doi.org/10.1023/a:1009670112978 Ulungu EL, Teghem J (1995) The two phases method: an efficient procedure to solve bi-objective combinatorial optimization problems. Found Comput Decis Sci 20:149–156 Ulungu EL, Teghem J (1997) Solving multi-objective knapsack problem by a branch-and-bound procedure. In: Multicriteria analysis. Springer, Berlin, pp 269–278. https://doi.org/10.1007/978-3-642-60667- 0_26 Vincent T, Seipp F, Ruzika S, Przybylski A, Gandibleux X (2013) Multiple objective branch and bound for mixed 0–1 linear programming: corrections and improvements for the biobjective case. Comput Oper Res 40(1):498–509. https://doi.org/10.1016/j.cor.2012.08.003 Visée M, Teghem J, Pirlot M, Ulungu EL (1998) Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem. J Glob Optim 12(2):139–155. https://doi.org/10.1023/A: 1008258310679 Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans Evol Comput 3(4):257–271. https://doi.org/10.1109/4235.797969 123 Augmenting bi-objective branch and bound 121 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123