Efficient storage of Pareto points in biobjective mixed integer
programming
Nathan Adelgren∗,†1 , Pietro Belotti2 , and Akshay Gupte†3

arXiv:1411.6538v3 [cs.DS] 2 May 2017

1

Department of Mathematics and Computer Science, Edinboro University, Edinboro,
PA 16444, nadelgren@edinboro.edu
2
FICO, International Square, Starley Way, Birmingham B37 7GN, United Kingdom,
pietrobelotti@fico.com
3
Department of Mathematical Sciences, Clemson University, Clemson, SC 29634,
agupte@clemson.edu

Abstract
In biobjective mixed integer linear programs (BOMILPs), two linear objectives are minimized over a polyhedron while restricting some of the variables to be integer. Since many
of the techniques for finding or approximating the Pareto set of a BOMILP use and update
a subset of nondominated solutions, it is highly desirable to efficiently store this subset.
We present a new data structure, a variant of a binary tree that takes as input points and
line segments in R2 and stores the nondominated subset of this input. When used within
an exact solution procedure, such as branch-and-bound (BB), at termination this structure
contains the set of Pareto optimal solutions.
We compare the efficiency of our structure in storing solutions to that of a dynamic list
which updates via pairwise comparison. Then we use our data structure in two biobjective
BB techniques available in the literature and solve three classes of instances of BOMILP, one
of which is generated by us. The first experiment shows that our data structure handles up
to 107 points or segments much more efficiently than a dynamic list. The second experiment
shows that our data structure handles points and segments much more efficiently than a list
when used in a BB.

1

Introduction

Biobjective mixed integer linear programs (BOMILP) have the following form:


>
>
>
minx,y f (x, y) := f1 (x, y) := c>
1 x + d1 y, f2 (x, y) := c2 x + d2 y
s.t.
(x, y) ∈ PI := {(x, y) ∈ Rm × Zn : Ax + By ≤ b},

(1)

where PI is a bounded set. Define as Ω := {ω ∈ R2 : ω = f (x, y) ∀(x, y) ∈ PI } the collection of
all points in R2 which can be obtained using the objective function values of feasible solutions
to (1). We refer to the space R2 containing Ω as the objective space.
For any two vectors v 1 , v 2 ∈ R2 we use the following notation: v 1 5 v 2 if vi1 ≤ vi2 for
i = 1, 2; v 1 ≤ v 2 if v 1 5 v 2 and v 1 6= v 2 ; and v 1 < v 2 if vi1 < vi2 for i = 1, 2. Given distinct
(x, y), (x0 , y 0 ) ∈ PI , we say that f (x, y) dominates f (x0 , y 0 ) if f (x, y) ≤ f (x0 , y 0 ). This dominance
is strong if f (x, y) < f (x0 , y 0 ); otherwise it is weak. A point (x, y) ∈ PI is (weakly) efficient if
@ (x0 , y 0 ) ∈ PI such that f (x0 , y 0 ) (strongly) dominates f (x, y). The set of all efficient solutions
∗
†

Part of the work was carried out at Department of Mathematical Sciences, Clemson University
Partial support by ONR grant N00014-16-1-2725 is acknowledged

1

in PI is denoted by XE . A point ω = f (x, y) is called Pareto optimal if (x, y) ∈ XE . Given
Ω0 ⊆ Ω we say that ω 0 ∈ Ω0 is nondominated in Ω0 if @ ω 00 ∈ Ω0 such that ω 00 dominates ω 0 . Note
that Pareto optimal points are nondominated in PI . We consider a BOMILP solved when the
set of Pareto optimal points ΩP := {ω ∈ R2 : ω = f (x, y) ∀(x, y) ∈ XE } is found.
It is known [7] that a biobjective LP (BOLP) can be solved by taking convex combinations
of f1 (·) and f2 (·) and solving a finite number of LPs. Thus for BOLP, the set of Pareto points
can be characterized as ΩP = {(f1 , f2 ) ∈ R2 : f2 = ψ(f1 )} where ψ(·) is a continuous, convex,
piecewise linear function obtained using extreme points of the feasible region. For biobjective
integer programs (BOIPs) it is known that ΩP is a finite set of points in R2 . Now consider
the case of BOMILP. Let Y = Projy PI be the set of integer feasible subvectors to (1). Since
PI is bounded, we have Y = {y 1 , . . . , y k } for some finite k. Then for each y i ∈ Y there is an
associated BOLP, referred to as a slice problem and denoted P(y i ), obtained by fixing y = y i in
(1):
> i
>
> i
P(y i )
minx {f1 (x) = c>
1 x + d1 y , f2 (x) = c2 x + d2 y }
(2)
s.t. Ax ≤ b − By i .
Problem P(y i ) has a set of Pareto solutions Ωi := {(f1 , f2 ) ∈ R2 : f2 = ψi (f1 )}, where ψi (·) is a
continuous convex piecewise linear function as explained before. Then ΩP ⊆ ∪ki=1 Ωi and this
inclusion is strict in general. In particular, we have:



k
2
ΩP = ∪ Ωi \ ∪ Ωj + R+ \ {0} .
(3)
i=1

j6=i

Such union of sets is not, in general, represented by a convex piecewise linear function. Figure
1 shows an example with k = 5.
It should be noted that finding ΩP is not a trivial task in general. In the worst case,
ΩP = ∪ki=1 Ωi and one may have to solve every slice problem to termination, which can have
exponential complexity. For multiobjective IPs (i.e. m = 0), De Loera et al. [5] prove that ΩP
can be enumerated in polynomial-time for fixed n, which extends the well known result that
single-objective IP’s can be solved in polynomial-time for fixed n [11]. We are unaware of any
similar results for BOMILP.
Exact procedures for solving BOMILP with general integers have been recently the subject
of intense research. Exact methods have been presented by Belotti et al. [2, 3], Boland et al. [4],
and more recently by Soylu and Yıldız [18]. Özpeynirci and Köksalan [14] give an exact method
for finding supported solutions of BOMILP. Most other techniques in the literature tackle specific
cases. Vincent et al. [22] improved upon the method of Mavrotas and Diakoulaki [12] for mixed
0-1 problems. Stidsen et al. [19] propose a method for solving mixed 0-1 problems in which only
one of the objectives contains continuous variables. Belotti et al. [2], Mavrotas and Diakoulaki
[12], Stidsen et al. [19] and Vincent et al. [22] are based on branch-and-bound (BB) procedures
in which the Pareto set is determined by solving several BOLPs. Instead, Boland et al. [4],
Özpeynirci and Köksalan [14], and Soylu and Yıldız [18] determine the Pareto set by solving
several MIPs, albeit in different ways: while, for example, Boland et al. [4] recursively partition
the objective space to circumscribe subsets of Pareto points and segments, Soylu and Yıldız [18]
find the Pareto frontier incrementally, starting from a solution to a single-objective problem.
The pure integer case has been studied for binary variables [9], general integers [16] and specific
classes of combinatorial problems [17, 15, 8].
We present a data structure for efficiently storing a nondominated set of feasible solutions to
a BOMILP. For lack of better names, we call it biobjective tree, or BoT. The BoT can be used
in exact and heuristic solution procedures that aim at finding or approximating the Pareto set.
Data structures such as quad-trees have been used for storing Pareto points in the past [21, 20],
although only in the pure integer case. Sun and Steuer [21] stored nondominated solutions
using both quad-trees and dynamic lists which were updated via pairwise comparison. They

2

(a) Generated points and segments

(b) Nondominated subset

Figure 1: Example of solutions generated when solving an instance of BOMILP.
showed that in the pure integer, biobjective case, dynamic lists store nondominated solutions
more efficiently than quad-trees.
In Section 2 we describe the BoT, and in Section 3 we describe the insertion function,
prove its correctness and provide an example of use. In Section 4 we present the results of two
experiments. The first experiment shows that a BoT is able to store nondominated points and
segments more efficiently than a dynamic list and can insert up to 107 solutions in reasonable
time. In the second experiment we utilize a BoT in the BB procedures of Belotti et al. [2]
and Adelgren and Gupte [1] to solve specific instances of BOMILP. The results show that BoT
handles points and segments much more efficiently than a list when used in a BB.

2

Biobjective tree (BoT)

Figure 1(a) shows an example of solutions that might be generated when solving an instance of
BOMILP. We would like to store the nondominated portion of these points and segments, as
shown in Figure 1(b). A BoT stores only the nondominated subset of the solutions regardless of
the order in which they are inserted. Consider the set of solutions in Figures 1(a) and suppose
that the segments connecting (1,17), (2,15), (4,14), and (9,13) are currently stored. When
inserting the point (5,11), which dominates a portion of the segment connecting (4,14) and
(9,13), the portion must be removed before the point is added. Similarly, when the segment
connecting (6,16) and (7,10) is inserted, because a portion of this segment is dominated by
(5,11), only the nondominated portion of the segment should be added.
A BoT is a binary search tree (BST) in which each node represents either a singleton or
a line segment associated with a Pareto point or set of Pareto points in the objective space.
Denote as Π the set of nodes in the tree. Each π ∈ Π is defined as a triplet π = (S, l, r), its
components defined as follows:
• S = (x1 , x2 , y1 , y2 ) represents a segment [(x1 , y1 ), (x2 , y2 )] defined in the objective space;
the segment collapses to a point if x1 = x2 and y1 = y2 .
• l and r are the left and the right child node of π, respectively.
We identify each element of a triplet π as π.S, π.l, and π.r. Let us define operators that are
used in the remainder: size(π) is the size of the subtree rooted at π, defined as size(∅) = 0 and
size(π) = 1 + size(π.l) + size(π.r); also, parent(π) is a node π 0 such that π 0 .l = π or π 0 .r = π,
if any exists, or ∅ otherwise. Hence π is a leaf node if π.l = π.r = ∅, or the root node if
parent(π) = ∅. Finally, subtree(π) is the subtree rooted at π. In the remainder, even though a

3

π2
π
π1

(a) Segment

(b) Single point

(c) Weak domination.

Figure 2: Partition of R2 w.r.t. a segment or point π.S (a,b); example of weak domination (c).

node π is defined by a triplet, we sometimes use π to refer to π.S for ease of notation (especially
with set operations), but only where we believe this does not lead to confusion. In particular,
for π = (S, l, r) the operation π ∩ A, where A ⊆ R2 , returns a point π 0 = (S 0 , l, r) such that
S 0 = S ∩ A.
A BoT contains nodes that correspond each to a segment S = [(x1 , y1 ), (x2 , y2 )] such that
x1 ≤ x2 and y1 ≥ y2 , as otherwise S can be reduced to a single point. The BoT maintains
a non-strict total order  between nodes: for two nodes π 0 = (S 0 , l0 , r0 ), π 00 = (S 00 , l00 , r00 ) ∈ Π,
with S 0 = [(x01 , y10 ), (x02 , y20 )] and S 00 = [(x001 , y100 ), (x002 , y200 )], π 0  π 00 if either π 0 and π 00 are the
same, or x02 ≤ x001 and y20 ≥ y100 . Our notation extends to node segments as well, i.e., π 0  π 00 ≡
π 0 .S  π 00 .S. Also, for any π ∈ Π, we have π.l ≺ π ≺ π.r.
All operations on the BoT must conserve this total order; as for any BST, enumerating its
sorted elements amounts to an in-order parse of the tree. Removal of a subtree from the BST
and rebalancing subtrees preserves the order [10]. Most tree operations carry over to the BoT
without change, but insertion, discussed in Section 3, is radically different: a BST insertion
increases the tree size by one, while in a BoT inserting a single node might have a large-scale
effect. For instance, an entire subtree might be deleted if the inserted segment S dominates all
nodes of the subtree. Even if S does not dominate any of the current nodes, the non-dominated
portion of S could be as many as t + 1 disjoint segments (if t nodes are stored).
This is the main point of departure with classical BSTs and other data structures (redblack trees, for instance) that have fast insertion and lookup. This also explains why other
data structures such as a list or a hash-table might be less suited for this purpose: lookup
and insertion in the list are rather expensive at O(t) if t is the number of elements in the list;
insertion of a point in a hashtable and the possible deletion of a large number of elements is
inefficient in a hash table for many reasons. One such reason is locality of the data: a good
hash function would guarantee large separation, in the hash table, between two adjacent points
or segments in the objective space. Finding all segments that are dominated by one point or
segment would prove inefficient, as it would require visiting the entire data structure.
The following notation is useful in the remainder of the paper: we partition R2 relative to the
segment π.S = [(x1 , y1 ), (x2 , y2 )] of a node π into four regions Rα (π) for α ∈ {up, dn, left, right}.
We define Rup (π) = π.S + {(x, y) ∈ R2 : x > 0, y > 0}, i.e., the set of points dominated by π;
Rdn (π) = π.S + {(x, y) ∈ R2 : x ≤ 0, y ≤ 0}; Rleft (π) = {(x, y) ∈ R2 : x ≤ x1 , y > y1 }; and
finally Rright (π) = {(x, y) ∈ R2 : x > x2 , y ≤ y2 } (see Figure 2).
Example 1. Suppose π ∈ Π is defined by the segment between (2, 5) and (3, 3). Further suppose
that π1 is the point (1, 5), π2 is the point (2, 6) and both π1 and π2 are inserted into the BoT.
Observe Figure 2(c). The point associated with node π1 weakly dominates the left-most point
of the segment associated with π and thus π1 should be stored. However, the point associated
with node π2 is weakly dominated by the segment associated with π and so π2 should not be
4

stored.
The previous example leads us to our next choice. Consider π and π1 in Figure 2(c): we
should mark the segment as open at (2, 5), i.e., π.S =](2, 5), (3, 3)] assuming no other points
dominate (3, 3). We do not memorize whether a segment π.S is open or closed on either extreme.
Verifying such information would lead to more complex algorithms. Instead, upon termination
of the BB, for any node π we check the nodes immediately to the left and to the right to
determine if π.S is (partially) open.

3

Insertion

The Insert function is described in Algorithm 1. It takes two inputs: a node π ∗ to be inserted
and a node π which is the root of the tree. Because a node π does not hold any information
of all other nodes of the subtree rooted at π, the insertion of π ∗ might have to be propagated
both to π.l and to π.r. For this reason, the Insert function is recursive. If the recursive call
inserts π ∗ in π.l = ∅ (or π.r = ∅), then π.l becomes π ∗ . The main call to Insert is done by
passing the root node of the tree, denoted as π0 , as the second argument.
The function Replace(π 0 , π 00 ) replaces π 0 ∈ Π with π 00 ∈ Π, leaving the BoT otherwise
unchanged. We instead denote with π 0 ← π 00 the process of replacing π 0 and its entire subtree
with π 00 and its entire subtree. RemoveNode(π), described in Algorithm 2, deletes π if it is
a leaf node, otherwise it replaces π with a node π 0 of its subtree that retains the total order.
For this, π 0 must be adjacent to π to the left or right, i.e., it is the left-most node of the right
subtree of π or right-most node of the left subtree of π.
Algorithm 1 Inserting a new point or segment, π ∗ , into a BoT at node π
1: function Insert(π ∗ , π)
2:
if π ∗ = ∅ then return
3:
if π = ∅ then Replace(π, π ∗ )
4:
else
5:
Define S 0 := π.S \ cl (Rup (π ∗ ))
6:
if S 0 = ∅ then
7:
RemoveNode(π)
8:
Insert(π ∗ , π)
9:
else
10:
if ∃S 00 , S 000 s.t. S 0 = S 00 ∪ S 000 ∧ cl(S 00 ) ∩ cl(S 000 ) = ∅ ∧ S 00  S 000 then
11:
Create new node π 0 = (S 000 , ∅, π.r)
12:
π.r ← π 0
13:
π.S ← S 00
14:
else π.S ← S 0
15:
Insert(π ∗ ∩ Rleft (π), π.l)
16:
Insert(π ∗ ∩ Rright (π), π.r)

We skip the trivial cases and focus on lines 5 onward in Algorithm 1. The set S 0 is obtained
by removing from π.S the set of points dominated by π ∗ . If S 0 = ∅, π is entirely dominated
by π ∗ and can be removed; the procedure is then called recursively on the new subtree. If
S 0 6= ∅, then it might be the union of at most two subsegments S 00 and S 000 . If so, S 000 becomes
the segment of a new node π 0 , which is assigned the right subtree of π, and π has its segment
restricted to S 00 . Otherwise π.S is changed to S 0 . Insertion is then called recursively on the left
and right subtrees of π.
The following property is equivalent to the total order mentioned in Section 2.
Property 1. For any π ∈ Π, all nodes in the subtree of π.l (resp. π.r) are located completely
within Rleft (π) (resp. Rright (π)).

5

Algorithm 2 Remove a node that has been shown to be dominated.
1: function RemoveNode(π)
2:
if size(π) = 1 then π ← ∅
3:
else
4:
if size(π.l) > size(π.r) then π̃ ←FindRightmostNode(π.l)
5:
else π̃ ←FindLeftmostNode(π.r)
6:
7:

Replace(π, π̃)
RemoveNode(π̃)

For a tree with t nodes at the time of an insertion, the worst-case complexity of Insert is
O(t) as the entire tree might have to be visited. For example, consider the tree containing all
points {(i, M − i), i = 1, 2, . . . , M − 1} for any M > 2. Inserting π ∗ = (0, 0), which results in
π ∗ replacing the whole tree, requires visiting all nodes of the tree.

3.1

Correctness

Proposition 1. Insert removes any portion of a currently stored node π which is dominated
by an inserted node π ∗ .
Proof. Obvious from steps 7 (if S 0 = ∅), 13 (if S 0 = S 00 ∪ S 000 ), and 14 (S 0 is a segment) of
Algorithm 1.
Proposition 2. Insert adds node π ∗ , or a portion, to the tree if and only if it is not dominated
by any node currently stored in the tree.
Proof. (If) Let S 0 be a portion of π ∗ .S not dominated by any π ∈ Π; then (S 0 , ∅, ∅) is inserted
as a leaf node after a finite number of recursive calls — see lines 15 and 16.
(Only if) We show the contrapositive. Suppose there is a portion S̃ of π ∗ .S that is dominated
by π ∈ Π. If π = π0 , then Insert(π ∗ , π) has the effect (line 5) of removing S̃ from the set of
points to be inserted, while the two recursive calls at lines 15 and 16 are made for π ∗ ∩ Rleft (π)
and π ∗ ∩ Rright (π), both excluding S̃. If π 6= π0 and π ∈ subtree(π0 .l) (resp. π ∈ subtree(π0 .r)),
the recursive call Insert(π ∗ ∩ Rleft (π0 ), π0 .l) (resp. Insert(π ∗ ∩ Rright (π0 ), π0 .r)) guarantees
that a call to Insert(π ∗ , π) will be placed, i.e., S̃ will be eliminated by subsequent recursive
calls.
According to Propositions 1 and 2, the end state of the BoT contains all and only nondominated solutions.
Proposition 3. Insert retains Property 1.
Proof. The result is trivial for the cases in lines 2 and 3 of Algorithm 1. The same holds if
S 0 = ∅ (line 6), as it is easy to prove that RemoveNode retains Property 1. If, for the node
π ∗ to be inserted, π ∗ .S ⊂ ∪π∈Π Rup (π), then π ∗ is dominated and by Proposition 2 it will not
be inserted, thereby not modifying the BoT. By the same proposition, any segment π ∗ .S or
portion that neither dominates nor is dominated by any node will be added to the BoT so as
to satisfy Property 1: Insert recursively runs lines 15 and 16 until said portion is added as a
leaf.
Assume now that π ∗ .S ∩ Rdn (π) 6= ∅ for at least one π ∈ Π. Since π ∗ is not dominated, two
cases arise: (i) π.S \ cl(Rup (π ∗ )) is a single segment S 0 ; (ii) π.S \ cl(Rup (π ∗ )) is the union of two
disjoint segments S 00 and S 000 with S 00  S 000 .
In case (i), the property holds after running line 14, as π.S is replaced by its subset S 0 . Case
(ii) is dealt with on lines 10-13: since S 00  S 000 , π̃.S  S 00 for all π̃ ∈ subtree(π.l) and S 000  π̂.S
for all π̂ ∈ subtree(π.r). Thus, replacing π.S with S 00 ensures that Property 1 is maintained for
6

π0 .r

Rleft (π ∗ )

Rleft (π0 ) Rdn (π0 )

Rdn (π ∗ )

π0
π∗

Rup (π ∗ )

π∗

Rright (π ∗ )

Rup (π0 ) Rright (π0 )

(a) Inserting (5, 11).

(b) Inserting (8, 7), (14, 3).

Figure 3: An example that shows the effect of the insertion of a segment on a set of nondominated segments.

(a) Tree after inserting (5,11).

(b) Tree after rebalancing.

(c) Final tree.

Figure 4: Rebalancing a tree upon insertion of point (5, 11).
π.l and placing π 0 := (S 000 , ∅, π.r) as the right child of π ensures that the same holds for π.r. By
construction π  π 0 , and this concludes the proof.

3.2

Illustrative example

We use the points and segments in Figure 1(a) as input to a BoT and show a few of the
nontrivial steps of developing it. Assume that these solutions are obtained from five separate
slice problems and that the Pareto sets of these slice problems are: (i) the singleton (1,19),
(ii) the piecewise linear curve connecting (1,17) and (9,13), (iii) the one connecting (6,16) and
(11,4), (iv) the singleton (5,11), and (v) the piecewise linear curve connecting (8,7) and (17,2).
The points and segments which define these Pareto sets are inserted into the BoT in the order
of (iii), (iv), (ii), (v), (i). Piecewise linear curves are inserted as individual line segments from
left to right.
The first call is on an empty tree, hence π ∗ = [(6, 16), (7, 10)] becomes the tree. The next
point is π ∗ = [(7, 10), (10, 5)]; note that π ∗ ⊂ Rright (π0 ) and should be inserted at π0 .r. Since
π0 .r = ∅, π ∗ replaces π0 .r. The insertion of [(10, 5), (11, 4)] is analogous.
Next consider Pareto set (iv). Let π ∗ ← (5, 11) and call Insert(π ∗ , π0 ). Observe Figure
3(a). Because π ∗ partially dominates π0 , we remove the dominated portion of π0 by letting
S 0 = π0 .S \ cl(Rup (π ∗ )). As a consequence, π ∗ ⊂ Rleft (S 0 ), and, since π0 .l = ∅, π ∗ becomes
the left child of π0 . Figure 4(a) shows the BoT after π ∗ has been inserted. We leave it to the
reader to consider Pareto set (ii). Rebalancing the subtree rooted at π0 .l after processing this
set yields the BoT shown in Figure 4(b).
Consider now the insertion of Pareto set (v). Let π ∗ ← [(8, 7), (14, 3)] and call Insert(π ∗ , π0 ).
Clearly π ∗ ⊂ Rright (π0 ) and is hence inserted to π0 .r. Observe from Figure 3(b) that π ∗ partially
dominates π0 .r. This time, though, the portion of π0 .r which is dominated is the center section
of the segment. This means that π0 .r must be split into two nodes π1 and π2 . Node π1 takes the
place in the tree where π0 .r originally was, and the left subtree of π0 .r becomes the left subtree of

7

π1 . Node π2 becomes the right child of π1 and the right subtree of π0 .r becomes the right subtree
of π2 . Subsequently, π ∗ ⊂ Rright (π1 ) and thus π ∗ is inserted to π2 (which is now π0 .r.r). Notice
that π0 .r.r partially dominates π ∗ and that it is the center portion of π ∗ that is dominated.
Thus the calls to Insert(π ∗ ∩ Rleft (π0 .r.r), π0 .r.r.l) and Insert(π ∗ ∩ Rright (π0 .r.r), π0 .r.r.r) each
causes a portion of π ∗ to be inserted at π0 .r.r.l and π0 .r.r.r respectively. Since π0 .r.r.l = ∅,
π ∗ ∩ Rright (π0 .r.r) becomes π.r.r.l. Since π0 .r.r.r is the segment (10,5) to (11,4), it is clear that
another portion of π ∗ needs to be removed, and then the remainder of π ∗ becomes π0 .r.r.r.r.
The remaining insertions are analogous to those that we have described. After yet another
rebalance, the final BoT is as in Figure 4(c).

4

Computational Experiments

We implemented the BoT in the C programming language and performed two tests. The first
test addresses the efficiency with which a large number of randomly generated solutions can be
stored in a BoT, using different rebalancing techniques. The second test addresses the utility a
BoT when used in the two BB algorithms for BOMILP by Belotti et al. [2] and by Adelgren and
Gupte [1]. All tests were run on Clemson University’s Palmetto Cluster. Specifically, an HP
SL250s server node with a single Intel E5-2665 CPU core with 16GB of RAM running Scientific
Linux 6.4 was used.
In all of these experiments we compare the performance of the BoT with that of a dynamic
linked list (L). Like a BoT, the linked list takes points and segments in R2 as input and stores
only the nondominated subset of all input. All segments S = (x1 , x2 , y1 , y2 ) of the linked list
are stored in increasing order of x1 , so that parsing all elements of the list produces the same
output as an in-order visit of a BoT. Inserting a point or segment S 0 consists in comparing
it with every stored point or segment in the list, until a segment S is encountered such that
S 0 ⊂ Rleft (S). During each comparison, dominated solutions are discarded. Although only a
few, if any, elements of the list might be changed with the insertion of S 0 , because we do not
know where these elements are located and do not have more sophisticated search mechanisms
on such a list, insertion has an average complexity of O(t). Such lists have been used for storing
nondominated solutions in both the pure integer [21] and mixed-integer cases [12, 22].
Maintaining a balanced tree is one of the most costly operations, as shown in the tests
below. As its only purpose is efficiency, it does not need to be applied at every step. Hence, we
decided to further consider the rebalancing operations and use an alternative strategy that is
less computationally costly, but still keeps the BoT fairly balanced.
We use the strategy of Overmars and Van Leeuwen [13]: for each non-leaf node π, the
1
subtrees of π.l and π.r must contain no more than
size(π) nodes, where δ is a pre-selected
2−δ
value in the open interval (0, 1). This causes the depth of the tree to be at most log2−δ t where
t is the number of nodes in the tree.
Overmars and Van Leeuwen [13] also suggest rebalancing by traversing the path travelled
by an inserted solution in the reverse order and checking whether or not the balance criterion
is satisfied at each of these nodes. This saves one from having to check the balance criterion at
every node in the tree since the only places where it could have been altered are at nodes along
this path. In our case, though, when a line segment is inserted into a BoT, it often does not
remain intact, but may be separated into many smaller segments, each traversing its own path
through the tree before finally being added. For this reason, rearranging the tree after insertion
is troublesome, and we experimented with a few alternative approaches:
A0 - No rebalancing is used.
A1 - Before inserting a point or segment at the root node, check the balance criterion at every
node in the tree and rebalance where necessary. This approach guarantees that the balance
8

of the tree is maintained, though at a high computational cost.
A2 - Check the balance criterion after the k-th insertion (we used k = 100 in our tests), then
check the balance criterion when the tree size increased by 101% w.r.t. the size at the
previous check. This approach significantly decreases the complexity of rebalancing, but
eliminates the balance guarantee.
A3 - Check the balance criterion at any node that is currently being inserted at. This approach
has a much lower complexity than A1, and would cause balance to be maintained at the
root node, and along any frequently travelled paths in the tree. However, again the
guarantee of balance is lost.
A4 - Combine approaches A2 and A3: check the balance criterion of the entire tree after the kth insertion (k = 100), then check the balance criterion again when the tree size increases
by 800% w.r.t. the size at the previous check. In between these checks of the entire tree,
check the balance criterion for any node that is being inserted at.
Approach A4 allows for maintaining a fairly well balanced tree by applying approach
A2 much more infrequently than if using approach A2 alone. Clearly this has a higher
complexity than approach A3, but it may be less than that of approach A2 and allow for
a more balanced tree.
We implemented each of these approaches in our first experiment, described in Section 4.1.
We utilize approach A2 when performing our second experiment, which is described in Section
4.2 because for most of our tests A2 performed comparably to A0 in terms of CPU time, but
always maintained a more balanced tree.

4.1

Insertion of large number of random points

This first test has two main purposes: (i) to compare the efficiency of a BoT with that of a
dynamic list when storing nondominated solutions, and (ii) to determine the best rebalancing
approach w.r.t. tree depth and time.
The test consists of repeating the following procedure until N insertions have been made
into a BoT or the dynamic list. First, generate a random integer i ∈ [1, 6] and a random number
r1 ∈ (0, 10). Then, if i > 1, for each j ∈ {2, . . . , i} a random number cj ∈ (0, 1) is generated
j
X
and we define rj = r1 +
c` . Next, for each j ∈ {1, . . . , i} the following are computed: (i)
`=2

(10.5 − rj )2
yj =
− k, and (ii) xj = rj + (5 − k). Here k is a dynamic value which is defined
5
µ
as 1 at the start of the test and increases by
each time the above process is repeated, and
N
µ ∈ R determines how much the solutions should “improve” over the course of the test. If i = 1,
the singleton (x1 , y1 ) is inserted into the structure, otherwise the points (x1 , y1 ), ..., (xi , yi ) are
arranged in order of increasing x values and then the line segments connecting each adjacent pair
of points are inserted into the structure. We performed this test 100 times for each combination
of the values N ∈ {104 , 105 , 106 , 107 } and µ ∈ {0, 0.001, 0.01, 0.1, 1, 10}. We used various values
for δ and found that the results were quite similar, but determined to use a value of δ = 0.3.
For each test we recorded the total insertion time for both algorithms, the final depth of a BoT,
and the final number of nodes stored in the BoT and in the list.
With µ close to zero, there is little or no separation between early generated solutions
and later generated ones, and all are likely to be Pareto. With large values of µ, there is
significant separation between early generated solutions and later generated ones, the latter
being much more likely to be Pareto. Figure 5 shows an example of solutions generated during

9

(a) µ = 0.1

(b) µ = 1

(c) µ = 10

Figure 5: Example of randomly generated solutions; N = 100.
this experiment for µ = 0.1, 1 and 10 and for N = 100. The red solutions are those that are in
the BoT at the end of the test.
The minimum, maximum, and geometric means of the CPU times and final depths of the
tree can be found in Tables 1-3. The symbols A0 – A4 and L indicate runs in which the various
rebalancing approaches of a BoT and the dynamic list were used for storing solutions. Also,
entries in Tables 1-3 which contain dashes are those for which no results are available due to the
fact that individual runs took over 12 hours to complete and were therefore terminated. The
symbols ~ and † indicates results for which, due to the large amount of time taken for each
individual run, we were unable to perform the test 100 times. For these results, each test was
instead run 5 times (for ~) and 3 (for †).
We use performance profiles [6] to show the relative effectiveness of the various rebalancing
approaches, in terms of CPU time and tree depth, in Figure 6. We omit the results of the list
implementation and rebalancing approach A1 as they performed poorly in terms of CPU time
when compared to the other approaches, and only show profiles for N = 107 and for a few values
of µ for reasons of space. For µ = 0 (Figure 6(a)), A2, shown by the curve with + symbols,
has the best time performance although it does not dominate A0 (the solid line), which in turn
is at least 30% worse than A2 in half of the instances but never worse than 40%. Algorithms
A3 and A4 perform similarly and are dominated by A0 and A2. For µ = 0.001, instead (see
Figure 6(b)), A0 dominates A2, which is, nevertheless, never more than 15% worse than the
best performance. A3 and A4 (lines with ∗ and ◦, respectively) perform worse still, and this is
confirmed for µ = 1 (see Figure 6(c)), where A4 fares slightly better than A3. This is confirmed
for µ = 10 (not shown).
While A2 and A0 perform well in general, A0 carries the risk of an unbalanced tree, as
reported in Figure 6(d), where tree depth is shown to be up to 3.5 times worse than the best.
A3 and A4 have the best performance in terms of maximum tree depth, which however reflects
in poor time performance as shown in Figure 6(b).
As shown in Tables 1–3, with approaches A0, A2, A3, and A4, the BoT is able to process
inserted solutions much more quickly than the dynamic list; A1 is more efficient than the list,
but far slower than the other approaches. The performance difference grows with N .
Also, for most values of N and µ, A0 typically performs the best in terms of running time,
followed closely by A2. On the other hand, A3 and A4 perform the best in terms of tree depth.
Because an increasing µ implies an increasing number of eliminated solutions at each insertion
(and, in general, fewer solutions stored in the data structure at any time), the time taken to
insert solutions decreases as the value of µ increases. Furthermore, the larger the value of µ, the
smaller the gap between the CPU time spent by the linked list and that the BoT. We conclude
that the BoT is more scalable and performs better than a linked list for storing randomly
generated solutions. Of all rebalancing algorithms tested, only A1 appears to be inefficient,
while no rebalancing at all (algorithm A0) seems to have a limited impact on the performance.

10

100

100

80

80

60

60

40

40

20

20

0
1.0

1.2

1.4

1.6

1.8

2.0

2.2

2.4

0
1.00

2.6

1.05

(a) Time, µ = 0
100

80

80

60

60

40

40

20

20

1.05

1.10

1.15

1.20

1.15

1.20

1.25

3.0

3.5

(b) Time, µ = 0.001

100

0
1.00

1.10

1.25

1.30

0
1.0

1.35

(c) Time, µ = 1

1.5

2.0

2.5

(d) Depth, µ = 0.001

Figure 6: Performance profiles of the rebalancing algorithms A0 (solid line), A2 (+), A3 (∗),
and A4 (◦). All profiles are w.r.t. results for N = 107 . For each algorithm A, a point (x, y) on
A’s curve indicates that for y% of the instances A’s performance is at most x times worse than
the best algorithm.

11

Table 1: Time and depth of the tree for the random points test (µ = 0, 0.001)
N
104

105

106

107

Rebal
Type
A0
A1
A2
A3
A4
L
A0
A1
A2
A3
A4
L
A0
A1
A2
A3
A4
L
A0
A1
A2
A3
A4
L

Min

Time (s)
Avg

0.08
2.22
0.16
0.11
0.11
5.65
4.52
448.54
6.31
5.83
5.69
668.19
126.01
–
124.02
137.08
136.23
–
1684.59
–
1287.45
1599.44
1611.95
–

0.09
2.31
0.20
0.16
0.16
5.94
4.85
476.75
9.91
9.81
9.77
694.63
128.91
–
143.02
168.69
165.19
–
2122.15
–
1915.42
2422.43
2413.61
–

Max
µ=0
0.10
2.55
0.35
0.38
0.39
6.27
4.94
520.94
32.54
41.62
43.83
747.21
135.84
–
254.55
328.82
306.11
–
2809.04
–
4908.04
6690.78
6880.00
–

Min
34
16
16
16
16
–
42
19
19
19
19
–
45
–
21
21
20
–
50
–
22
21
21
–

Depth
Avg
Max
42.6
16.2
17.1
17.0
17.0
–
51.3
19.2
20.2
19.8
19.7
–
54.6
–
22.4
21.0
21.0
–
57.9
–
24.4
21.3
21.3
–

53
18
18
18
18
–
62
20
22
21
21
–
70
–
24
22
22
–
68
–
26
23
23
–

Min

Time (s)
Avg

0.03
0.28
0.05
0.04
0.04
0.35
0.64
9.09
0.80
0.84
0.81
19.30
17.32
427.00
18.93
20.12
19.85
–
431.54
~39654.42
423.87
468.92
456.67
†63936.51

0.03
0.30
0.05
0.05
0.05
0.37
0.70
9.57
0.91
0.99
0.99
19.65
18.39
434.40
19.82
21.35
21.07
–
459.64
39922.79
466.23
491.24
482.73
67937.70

Max
µ = 0.001
0.04
0.36
0.08
0.1
0.09
0.41
0.79
11.02
1.12
1.30
1.31
20.73
18.79
465.09
21.71
24.55
24.2
–
485.31
40136.91
504.79
536.21
522.69
70214.80

Min
25
12
12
12
12
–
27
13
14
14
14
–
34
17
17
16
16
–
36
17
20
18
17
–

Depth
Avg
31.6
12.0
13.6
13.1
13.1
–
36.7
14.0
17.0
14.9
14.9
–
42.2
17
21.0
16.3
16.44
–
46.3
17.0
26.2
18.1
18.0
–

The results suggest that A2 seems to combine good performance in terms of time and maximum
tree depth, and is therefore the rebalancing algorithm of choice for our next tests.

4.2

Using a BoT in branch-and-bound algorithms

To test more in depth the utility of a BoT when utilized in a BB, we performed another set of
tests in which a variety of instances of BOMILP were solved using branch-and-bound. To ensure
the results were not too dependent on one solver, we ran our tests on two implementations,
described in Belotti et al. [2] and Adelgren and Gupte [1]. The latter utilizes this data structure
not only for storing found solutions, but also to check for domination of bound sets and hence,
for fathoming. In addition, it uses warm starting, i.e., it generates an initial set of points before
the BB is started. This BB was able to solve larger instances in under 8 hours and also did not
run into numerical difficulties when solving instances of type II from Boland et al. [4]. For both
BB solvers, we have used approach A2 for rebalancing.
We used three classes of BOMILP instances: two sets of instances described and used in
Belotti et al. [2] and Boland et al. [4] and one that we have created. The latter set contains
instances, which we call geometrical, that, while of rather simple structure, contain by design
a large number of Pareto points. Testing these instances forces the BB algorithms to create
numerous BB nodes and solutions, thus assessing a BoT in a more realistic, large-scale setting
where the number of solutions inserted are closer to those of our first experiment. These are
very simple BOMILPs with a large Pareto set for which a single BB node is solved very quickly.
The model is as follows:
max x
max y
s.t. y − si x ≤ bi − ai si
x − 0.1z ≤
0.025
x − 0.1z ≥ −0.025
x, y ≥ 0, z ∈ Z,
12

∀i ∈ {1, . . . , k}

(4)

Max
41
13
16
14
14
–
52
15
19
16
16
–
54
17
24
17
17
–
63
17
32
19
19
–

Table 2: Time and depth of the tree for the random points test (µ = 0.01, 0.1)
N
104

105

106

107

Rebal
Type
A0
A1
A2
A3
A4
L
A0
A1
A2
A3
A4
L
A0
A1
A2
A3
A4
L
A0
A1
A2
A3
A4
L

Min

Time (s)
Avg

0.02
0.11
0.03
0.03
0.03
0.11
0.34
3.14
0.41
0.47
0.48
4.12
6.61
91.56
6.92
8.31
8.24
211.81
94.29
1874.98
93.15
108.64
109.23
2786.57

0.02
0.11
0.03
0.03
0.03
0.12
0.36
3.22
0.43
0.50
0.50
4.27
7.07
96.47
7.37
8.83
8.72
215.19
184.30
4396.94
187.70
206.37
200.11
14687.80

Max
µ = 0.01
0.02
0.13
0.03
0.03
0.03
0.14
0.39
3.35
0.47
0.55
0.56
4.47
7.88
105.81
7.84
9.56
9.14
224.98
188.04
6018.77
191.03
210.70
207.89
15234.72

Min
14
10
10
10
10
–
18
12
13
12
12
–
21
13
16
14
14
–
23
15
18
16
16
–

Depth
Avg
Max
21.6
10.2
12.2
11.1
11.1
–
25.4
12.1
15.9
13.0
13.0
–
29.6
13.9
19.8
14.9
14.9
–
33.2
15.1
23.5
16.3
16.3
–

36
11
16
12
12
–
47
13
20
14
14
–
43
15
25
16
16
–
48
16
29
17
17
–

Min

Time (s)
Avg

0.01
0.05
0.02
0.02
0.02
0.04
0.23
1.18
0.26
0.33
0.34
1.25
3.50
32.01
3.69
4.89
4.90
–
68.06
948.30
69.08
85.63
84.15
2136.03

0.01
0.05
0.02
0.02
0.02
0.04
0.23
1.20
0.26
0.34
0.34
1.31
3.58
32.41
3.78
5.03
5.04
–
70.71
1027.48
71.76
88.87
87.15
2210.22

Max
µ = 0.1
0.02
0.05
0.02
0.02
0.02
0.06
0.24
1.30
0.27
0.36
0.37
1.37
3.76
32.85
3.92
5.25
5.21
–
74.91
1132.85
74.85
93.43
92.13
2452.43

Min
11
8
8
9
9
–
13
10
10
10
10
–
16
12
14
12
12
–
19
13
16
14
14
–

Depth
Avg
Max
12.8
8.7
10.5
9.4
9.4
–
15.1
10.1
14.2
11.1
11.1
–
18.0
12.1
17.7
13.0
13
–
20.9
13.9
20.7
14.8
14.8
–

q
−bi
where a1 = 0, ai+1 = ai + Nk for i ∈ {1, . . . , k}, bi = N 2 − a2i for i ∈ {1, . . . , k+1}, si = abi+1
i+1 −ai
for i ∈ {1, . . . , k}, and N and k are parameters.
The results from the branch-and-bound tests are given in Tables 4 to 7. We use T and L
to represent the implementations using a BoT and the dynamic list, respectively. From Belotti
et al. [2], 30 instances are available for each problem size and 5 (resp. 4) from Boland et al. [4] for
each problem size of Type I (resp. II). The BB by Belotti et al. [2] works by creating M initial
Pareto points via solving M single-objective MIPs, hence we tested using different values of M .
In Tables 4 and 5, we report geometric means of the results on instances from Belotti et al. [2],
and provide results for every instance from Boland et al. [4] (with geometric means reported
in bold). We report the total solve time, the time spent inserting solutions (Time (insert)),
the time spent doing other data structure operations such as fathoming (Time (other), only
reported for the BB by Adelgren and Gupte [1] as it is negligible otherwise), the number of BB
nodes, the number of insertions, the number of nodes in the structure at termination (#nodes)
and the depth of the BoT. Again, problem sizes are reported as the number of variables, which
in most cases also equals the number of constraints (for instances from Boland et al. [4] of Type
II, the number of constraints is slightly greater than the number of variables).
In principle, a BB algorithm is expected to follow the same path regardless of the data
structure, with the same number of BB nodes explored and of solutions stored. While this is
true for most tests, there were discrepancies when using the BB by Adelgren and Gupte [1] for
solving instances from Belotti et al. [2] and Boland et al. [4]. We show the number of BB nodes,
of insertions, and of nodes in Table 5 when these differ, in general by a small amount but up to
3% in a few cases. Extra tests suggest that these discrepancies are due to small differences in
the solutions contained in either data structure: the insertion of a solution π into a BoT and a
list that have, initially, the same set of solutions may result in different sets if, for instance, the
extremes of segment π.S are very close to previous solutions, say within a tolerance of 10−4 ,
since the operations of Algorithm 1 allow for multiple changes in a subtree of the BoT. This
effect can be amplified as it may result in one BB node to be fathomed or explored, the latter
13

16
10
14
11
11
–
21
12
18
12
12
–
21
13
20
14
14
–
24
15
23
15
15
–

Table 3: Time and depth of the tree for the random points test (µ = 1, 10)
N
104

105

106

107

Rebal
Type
A0
A1
A2
A3
A4
L
A0
A1
A2
A3
A4
L
A0
A1
A2
A3
A4
L
A0
A1
A2
A3
A4
L

Min
0.01
0.03
0.01
0.01
0.01
0.03
0.19
0.55
0.20
0.25
0.25
0.50
2.39
12.15
2.47
3.48
3.48
13.18
34.49
317.90
35.15
48.55
48.54
419.88

Time (s)
Avg
0.01
0.04
0.01
0.02
0.02
0.03
0.19
0.56
0.20
0.25
0.25
0.52
2.42
12.44
2.50
3.54
3.55
13.44
34.97
321.25
36.10
49.79
49.84
435.56

Max
µ=1
0.01
0.04
0.02
0.02
0.02
0.04
0.19
0.61
0.21
0.26
0.26
0.57
2.47
12.85
2.57
3.64
3.63
13.87
35.78
329.82
37.20
52.08
51.46
458.88

Min
9
7
8
8
8
–
11
8
9
9
9
–
14
10
13
10
10
–
16
12
16
12
12
–

Depth
Avg
Max
11.2
8.0
9.8
8.6
8.6
–
12.6
8.8
12.3
9.3
9.3
–
15.3
10.2
15.2
11.1
11.1
–
18.0
12.1
18.0
13.0
13.0
–

16
9
13
10
10
–
17
10
17
10
10
–
19
11
19
12
12
–
21
13
21
14
14
–

Min

Time (s)
Avg

0.01
0.03
0.01
0.01
0.01
0.03
0.16
1.31
0.23
0.28
0.28
2.51
1.92
5.62
1.96
2.53
2.54
5.20
23.28
121.22
24.24
34.57
35.22
131.85

0.01
0.03
0.01
0.01
0.01
0.03
0.16
1.40
0.23
0.29
0.29
2.67
1.94
5.72
1.98
2.56
2.57
5.38
23.97
124.55
24.45
35.44
35.56
134.998

Max
Min
µ = 10
0.01
9
0.03
7
0.01
7
0.01
7
0.01
7
0.04
–
0.17
12
1.49
8
0.25
9
0.31
8
0.31
8
2.91
–
1.96
11
5.89
8
2.01
10
2.61
9
2.62
9
5.54
–
24.25
13
126.14
10
24.87
13
36.21
10
36.78
10
137.2
–

Depth
Avg
10.9
7.4
8.9
8.0
8.0
–
16.7
8.53
11.1
9.0
9.0
–
12.6
8.7
12.5
9.41
9.41
–
15.23
10.1
15.2
11.2
11.2
–

Max
17
9
12
9
9
–
24
10
15
10
10
–
20
10
20
11
11
–
19
12
19
13
13
–

resulting in an entire new BB subtree being explored.
Tables 4 and 5 show that the time spent by the BoT is much less than that spent using the
linked list. The total BB time shadows this dominance as insertion time is a negligible fraction
of the total solve time. However, these results confirm those of experiment 1: even within a
BB, insertion into a linked list often takes orders of magnitude longer than for a BoT. For all
instances of the two considered classes, the number of insertions amounts to up to a few million
yet the final structure only has a few thousand solutions (see e.g. Table 4, instances by Boland
et al. [4], for size 160); this suggests a pattern similar to that with larger values of µ (see Tables
1-3).
Both solvers that we used are rather rudimentary implementations—the alternative method
by Boland et al. [4] easily outperforms the BB solver by Belotti et al. [2]. This explains why
the BB times reported can be hours even if the BB algorithms visit up to only a few thousands
of BB nodes, well below the current state-of-the-art BB algorithms, where millions, or tens of
millions, of nodes can be explored in the same time for much larger instances.
The advantages of BoT over list are more apparent on geometrical instances, which, albeit
simple, allow for a thorough stress test of both the BB solvers and the data structures. For
these instances, the time spent by the data structures is a significant portion of the total CPU
time. All BB nodes are solved very quickly, and as a result many solutions are found and many
BB nodes are explored in a short time. Inserting all of these solutions, while efficient for a
BoT, requires much more computational effort for a linked list, to the point that the amount
of time spent inserting solutions in a large linked list becomes a substantial percentage of the
total CPU time.
These results suggest that an efficient data structure will be essential when faster and more
stable BB solvers, for instance using quicker fathoming rules [3], become available: as the time
for each BB node decreases and the number of inserted solutions increases, the data structure
must be efficient enough that the insertion function only takes a small percentage of the total
CPU time.

14

Table 4: BB tests: results for algorithm of Belotti et al. [2].
Time
Size

M

T

Time (insert)
T
L

L

#BBnodes
(×102 )

#inserts
(×103 )

#nodes

tree
depth

1.790
1.155
1.838
2.729
2.046
2.988

62.6
60.0
64.1
82.9
82.1
80.6

6.3
6.6
6.4
6.9
7.0
6.9

Instances from Belotti et al. [2] (averaged)
60

80

10
25
50
10
25
50

15.0
11.6
16.4
38.0
32.6
42.6

15.1
11.6
16.1
38.2
32.9
42.9

0.007
0.005
0.012
0.011
0.005
0.011

0.007
0.004
0.007
0.009
0.006
0.008

8.11
6.32
8.22
13.55
11.42
14.11

Instances from Boland et al. [4], type 1
80

50

200

300

160

500

2000

3000

101
76
88
61
66

102
78
90
61
66

0.93
0.21
0.25
0.15
0.11

1.70
1.05
1.06
0.62
0.37

38
34
47
28
44

68
120
65
59
52

931
565
857
900
706

11
10
11
11
10

77

78

0.24

0.85

37

70

779

11

44
32
49
38
44

45
33
50
38
45

0.10
0.06
0.13
0.17
0.07

0.27
0.27
0.29
0.32
0.30

22
15
26
18
29

38
38
27
38
31

926
571
860
903
717

11
10
11
11
11

41

42

0.10

0.29

21

34

783

11

57
33
48
37
43

57
34
49
38
43

0.49
0.05
0.05
0.08
0.08

0.75
0.32
0.19
0.30
0.22

21
15
24
16
27

35
37
24
35
28

936
568
862
906
724

11
10
11
11
11

43

43

0.10

0.31

20

31

786

11

13584
15992
11721
5354
2384

13862
15790
11857
5442
2384

49.30
14.80
8.12
8.91
2.89

177.68
69.07
89.31
90.58
17.53

1502
2469
2030
819
364

3274
2807
1858
1319
572

2272
2102
2176
4600
2366

20
22
19
14
22

7987

8043

10.88

70.49

1176

1667

2575

19

10933
12505
10623
4846
2028

11088
12489
10606
5005
2062

34.37
13.33
6.35
8.66
2.28

165.50
59.33
74.90
84.26
14.83

1219
1954
1847
709
304

2484
2156
1448
958
461

2272
2111
2193
4597
2379

14
12
14
14
13

6775

6857

8.95

62.04

989

1280

2583

13

7775
11940
9872
4451
1994

7852
12051
10298
4532
2012

12.58
13.67
7.32
6.56
2.41

79.05
62.07
74.13
68.13
14.59

1193
1900
1817
696
297

2418
2090
1406
917
449

2274
2109
2195
4604
2382

13
13
13
14
13

6054

6162

7.24

51.48

968

1240

2585

13

15

Table 5: BB tests: algorithm of Adelgren and Gupte [1].
Size

Time
T

L

Time (insert)
T
L

Time (other)
T
L

#BBnodes

#inserts
T

L

#nodes
T

L

tree
depth

Instances from Belotti et al. [2] (averaged)
60
80

5
13

5
13

0.00
0.00

0.00
0.00

0.00
0.01

0.01
0.01

76
109

80

10
5
18
6
7

11
5
19
7
7

0.01
0.02
0.01
0.02
0.02

0.09
0.03
0.16
0.05
0.07

0.01
0.00
0.02
0.01
0.01

0.15
0.13
0.45
0.15
0.09

363
220
580
235
269

8

8

0.02

0.07

0.01

0.16

205
129
104
400
108

211
139
107
414
111

0.12
0.09
0.07
0.30
0.03

1.47
1.91
0.64
4.86
0.82

0.09
0.12
0.08
0.13
0.07

164

170

0.09

1.48

6266
4892
2742
5291
2404

6713
5457
2924
5629
2522

1.70
1.84
1.41
1.56
1.38

4035

4329

1.57

189
247

65
83

64

6
7

6429
5066
9491
4919
4795

943
590
885
928
737

930
583
883
920
732

11
12
10
11
10

311

5923

804

797

11

3.44
2.80
1.59
9.76
1.94

1418
997
924
2315
743

45501
41534
29895
79421
22397

2293
2160
2250
4785
2489

2285
2136
2203
4675
2408

17
13
13
17
13

0.10

3.11

1176

39850

2658

2610

14

205.34
243.26
105.24
176.53
49.21

1.16
0.74
0.30
0.57
0.43

189.91
242.09
65.32
132.42
60.80

6436
5278
3367
5925
3773

486497
354556
246820
364204
223789

487183
354343

11184
12070
12488
12863
9955

10970
11689
12138
12531
9703

48
18
15
16
18

135.49

0.58

119.31

4803

322156

322168

11664

11361

21

Instances from Boland et al. [4], type 1

160

320

363980

Instances from Boland et al. [4], type 2
800

1250

2500

1
2
4
9

1
2
4
9

0.00
0.00
0.00
0.00

0.00
0.00
0.00
0.01

0.00
0.01
0.00
0.01

0.00
0.00
0.00
0.01

39
46
98
180

254
279
589
900

54
64
90
129

128

6
7
7
7

3

3

0.00

0.00

0.00

0.00

75

440

80

79

7

9
19
19
46

9
19
19
46

0.00
0.00
0.02
0.01

0.00
0.00
0.00
0.01

0.01
0.00
0.02
0.00

0.01
0.02
0.06
0.06

147
310
302
542

867
1922
1962
3328

20

20

0.01

0.00

0.01

0.03

294

1816

514
944
1243
3185

515
945
1244
3199

0.04
0.01
0.02
0.02

0.13
0.18
0.21
0.45

0.29
0.31
0.45
0.86

1.42
2.28
2.73
6.24

2893
3831
4007
8468

7650
9409
9849
18665

1177

1180

0.02

0.22

0.43

2.73

4404

10725

16

1935

1819
9406

10724

140
200
245
281
210

201

8
8
9
9

210

8

306
370
451
386

449
385

9
9
10
9

375

374

9

Figure 7: Set of all solutions encountered by the BB method in Belotti et al. [2] with 80 variables
and 80 constraints. The red dots are the Pareto optimal solutions.
Table 6: BB tests: algorithm of Belotti et al. [2] on geometrical instances.
N

k

500

1
5
25
125

1000

1
5
25
125

2000

1
5
25
125

4000

1
5
25
125

8000

1
5
25
125

16000

1
5
25
125

Time
T

L

Time(insert)
T
L

#BBnodes
(×103 )

#inserts
(×103 )

#nodes
(×103 )

tree
depth

15
15
21
48

25
16
35
47

0.8
0.6
1.0
0.5

6.8
2.3
6.2
2.2

10
10
10
10

35
35
34
33

5
5
5
5

24
23
25
27

22

28

0.7

3.8

10

34

5

25

36
39
47
103

39
41
58
115

2.5
2.5
2.6
3.1

10.3
11.2
13.8
16.6

20
20
20
20

70
70
69
67

10
10
10
10

25
26
28
37

51

57

2.6

12.7

20

69

10

29

111
100
133
224

185
186
212
345

9.0
8.3
9.2
9.7

95.7
96.2
96.9
113.7

40
40
40
40

140
140
139
137

20
20
20
20

23
30
32
40

135

224

9.0

100.4

40

139

20

31

370
350
409
650

966
1070
1025
1308

41.9
53.0
42.6
48.4

681.9
774.3
691.1
751.8

80
80
80
80

280
280
279
277

40
40
40
40

32
31
30
27

431

1085

46.2

723.7

80

279

40

30

1952
1861
2113
3793

6275
4786
5363
6189

339.2
289.5
329.6
329.2

5185.5
3893.4
4339.8
4679.2

160
160
160
160

560
560
559
556

80
80
80
80

39
38
34
89

2323

5619

321.3

4499.8

160

559

80

46

8973
8059
12250
13464

22803
26171
23252
29552

1627.5
1638.7
1970.6
1674.1

19345.8
22958.1
20019.5
24950.9

320
320
320
320

1120
1120
1119
1116

160
160
160
160

41
41
41
118

10450

25305

1722.3

21702.8

320

1119

160

53

17

Table 7: BB tests: algorithm of Adelgren and Gupte [1] on geometrical instances.
N

k

500

1
5
25
125

1000

2000

4000

5

1
5
25
125

1
5
25
125

1
5
25
125

Time
T

L

Time (insert)
T
L

Time (other)
T
L

#BBnodes
(×103 )

#inserts
(×103 )

#nodes
(×103 )

tree
depth

12
119
131
163

56
158
160
200

1.93
1.08
0.85
0.93

16.13
11.37
9.59
13.19

0.09
0.16
0.12
0.14

23.85
21.86
18.19
20.78

10
10
10
10

20
20
20
20

5
5
5
5

16
15
15
14

75

130

1.13

12.34

0.12

21.07

10

20

5

15

39
458
511
619

273
707
762
895

5.31
3.13
3.09
3.08

90.61
60.20
66.47
69.18

0.16
0.45
0.38
0.38

104.85
133.60
135.67
149.48

20
20
20
20

40
40
40
40

10
10
10
10

16
15
15
16

273

603

3.55

70.77

0.32

129.83

20

40

10

15

133
1837
2032
2298

1346
3314
3251
3725

14.91
16.28
13.38
13.47

389.46
349.33
305.68
316.52

0.50
1.45
1.54
1.68

546.32
756.48
607.06
760.57

40
40
40
40

80
80
81
81

20
20
21
20

17
18
20
18

1034

2711

14.46

338.72

1.17

660.93

40

81

20

18

996
8530
8273
10466

6695
15352
14081
16394

80.32
106.16
99.59
91.13

1596.64
1518.61
1423.79
1386.03

3.07
8.59
5.36
7.60

2645.33
3974.04
3189.86
3239.40

80
80
80
80

160
160
162
160

40
40
42
40

18
18
18
18

5208

12411

93.79

1479.00

5.73

3228.40

80

160

40

18

Concluding remarks

We have introduced the biobjective tree, a variant of a binary tree to efficiently store sets of
nondominated solutions of BOMILPs. The BoT is equipped with an insertion procedure for
adding points and possibly eliminating several other points that are dominated by the newly
inserted one. The BoT also has the desirable property that an in-order pass produces a sorted
list of nondominated points. We tested the practical value of the BoT with two experiments.
The results show that a BoT provides a more efficient method for storing solutions to BOMILP
than a list of points. They also show that a BoT is also a very useful tool when used in BB
methods for solving BOMILPs.
It is worth noting here that we have focused on a simple BST data structure, instead
of one with better balancing properties, because we wanted to avoid the travails of studying
and implementing complicated rebalancing procedures, mixed with the already taxing duty
of maintaining other desirable properties of a BoT, i.e., the aforementioned ability to hold
nondominated points at any step.
Data structures like the BoT are preferable over lists when inserting large numbers of points
in an undefined order, such as in a BB algorithm. Because current state-of-the-art BB algorithms
for BOMILP can tackle relatively small problems, one can observe the impact of the data
structure in those classes of problems where BB node solution is fast, i.e., those problems that
admit a simple and compact structure yet contain a very large number of nondominated points.
We speculate that future implementations of a BB algorithm for BOMILP will expose even
more clearly the advantages of a BST data structure. However, algorithms that find solutions
in a non-random order might benefit from more specific, and perhaps less sophisticated, data
structures.

18

References
[1] Nathan Adelgren and Akshay Gupte. Branch-and-bound for biobjective mixed-integer
programming. Submitted for publication, 2016. URL http://www.optimization-online.
org/DB_HTML/2016/10/5676.html.
[2] Pietro Belotti, Banu Soylu, and Margaret M Wiecek. A branch-and-bound algorithm
for biobjective mixed-integer programs. Technical report, Clemson University, December 2012. URL http://www.clemson.edu/ces/math/technical_reports/belotti.
bb-bicriteria.pdf.
[3] Pietro Belotti, Banu Soylu, and Margaret M Wiecek. Fathoming rules for biobjective mixed
integer linear programs: Review and extensions. Discrete Optimization, 22:341–363, 2016.
[4] Natashia Boland, Hadi Charkhgard, and Martin Savelsbergh. The triangle splitting method
for biobjective mixed integer programming. In Jon Lee and Jens Vygen, editors, 17th International Conference on Integer Programming and Combinatorial Optimization (IPCO),
volume 8494 of Lecture Notes in Computer Science, pages 162–173. Springer International
Publishing, 2014.
[5] Jesús A De Loera, Raymond Hemmecke, and Matthias Köppe. Pareto optima of multicriteria integer linear programs. INFORMS Journal on Computing, 21(1):39–48, 2009.
[6] Elizabeth D Dolan and Jorge J Moré. Benchmarking optimization software with performance profiles. Mathematical Programming, 91(2):201–213, 2002.
[7] Matthias Ehrgott. Multicriteria optimization. Springer, 2005.
[8] Nicolas Jozefowiez, Gilbert Laporte, and Frédéric Semet. A generic branch-and-cut algorithm for multiobjective optimization problems: Application to the multilabel traveling
salesman problem. INFORMS Journal on Computing, 24(4):554–564, 2012.
[9] Gülseren Kiziltan and Erkut Yucaoğlu. An algorithm for multiobjective zero-one linear
programming. Management Science, 29(12):1444–1453, 1983.
[10] Donald Ervin Knuth. The art of computer programming: sorting and searching, volume 3.
Pearson Education, 1998.
[11] Hendrik W Lenstra Jr. Integer programming with a fixed number of variables. Mathematics
of Operations Research, 8(4):538–548, 1983.
[12] George Mavrotas and Danae Diakoulaki. Multi-criteria branch and bound: A vector maximization algorithm for mixed 0-1 multiple objective linear programming. Applied Mathematics and Computation, 171(1):53–71, 2005.
[13] Mark H Overmars and Jan Van Leeuwen. Dynamic multi-dimensional data structures
based on quad- and k-d trees. Acta Informatica, 17(3):267–285, 1982.
[14] Özgür Özpeynirci and Murat Köksalan. An exact algorithm for finding extreme supported
nondominated points of multiobjective mixed integer programs. Management Science, 56
(12):2302–2315, 2010.
[15] Anthony Przybylski, Xavier Gandibleux, and Matthias Ehrgott. A two phase method for
multi-objective integer programming and its application to the assignment problem with
three objectives. Discrete Optimization, 7(3):149 – 165, 2010. ISSN 1572-5286.

19

[16] Ted K Ralphs, Matthew J Saltzman, and Margaret M Wiecek. An improved algorithm for
solving biobjective integer programs. Annals of Operations Research, 147(1):43–70, 2006.
[17] Francis Sourd and Olivier Spanjaard. A multiobjective branch-and-bound framework: Application to the biobjective spanning tree problem. INFORMS Journal on Computing, 20
(3):472–484, 2008.
[18] Banu Soylu and Gazi Bilal Yıldız. An exact algorithm for biobjective mixed integer linear
programming problems. Computers & Operations Research, 72:204–213, 2016.
[19] Thomas Stidsen, Kim Allan Andersen, and Bernd Dammann. A branch and bound algorithm for a class of biobjective mixed integer programs. Management Science, 60(4):
1009–1032, 2014.
[20] Minghe Sun. A primogenitary linked quad tree data structure and its application to discrete
multiple criteria optimization. Annals of Operations Research, 147(1):87–107, 2006.
[21] Minghe Sun and Ralph E Steuer. Quad-trees and linear lists for identifying nondominated
criterion vectors. INFORMS Journal on Computing, 8(4):367–375, 1996.
[22] Thomas Vincent, Florian Seipp, Stefan Ruzika, Anthony Przybylski, and Xavier
Gandibleux. Multiple objective branch and bound for mixed 0-1 linear programming:
Corrections and improvements for the biobjective case. Computers & Operations Research,
40(1):498 – 509, 2013.

20

