16 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2019. № 1
ОПОВІДІ
НАЦІОНАЛЬНОЇ 
АКАДЕМІЇ  НАУК
УКРАЇНИ
Partial/quasi order optimization is a research field, which studies optimization problems in-
volving order relations. Classical examples of such problems are given by the multiobjective opti-
mization [1—4]. Various applications of the partial/quasi order optimization are considered in [5]. 
Related works include the optimization with dominance constraints [6, 7] and set-valued opti-
mization [8].
In the present paper, we consider a problem of finding the optimal (nondominated) elements 
(with respect to some partial/quasi order) on a discrete feasible set of elements defined by means 
of some other partial/quasi orders. A similar problem setting was considered in [9]. In practical 
problems, the feasible set may contain a huge number of elements, so the enumerative search is 
questionable. We develop a branch and bound (B&B) method for this problem and prove its con-
vergence. The method subdivides the original problem into a sequence of subproblems, selects 
subproblems containing optimal elements, and proceeds until such subproblems become trivial. 
Acceleration with respect to the enumerative search is achieved due to the group evaluation of 
© V.I. Norkin, 2019
doi: https://doi.org/10.15407/dopovidi2019.01.016
UDC 519.6
V.I. Norkin
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kiev
NTU of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”
E-mail: vladimir.norkin@gmail.com
B&B method for discrete partial order 
and quasiorder optimizations
Presented by Corresponding Member of the NAS of Ukraine P.S. Knopov
The paper extends the Branch and Bound (B&B) method to find all nondominated points in a partially or quasior-
dered space. The B&B method is applied to the so-called constrained partial/quasi order optimization problem, 
where the feasible set is defined by a family of partial/quasi order constraints. The framework of the generalized 
B&B method is standard, it includes partition, estimation, and pruning steps, but bounds are different, they are set-
valued. For bounding, the method uses a set ordering in the following sense. One set is ''less or equal'' than the other 
set if, for any element of the first set, there is a ''greater or equal'' element in the second one. In the B&B method, 
the partitioning is applied to the parts of the original space with nondominated upper bounds. Parts with small upper 
bounds (less than some lower bound) are pruned. Convergence of the method to the set of all nondominated points 
is established. The acceleration with respect to the enumerative search is achieved through the group evaluation of 
elements of the original space.
Keywords: quasiorder, partial order, nondominated solutions, discrete optimization, branch and bound method. 
ІНФОРМАТИКА ТА КІБЕРНЕТИКА
17ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2019. № 1
B&B method for discrete partial order and quasiorder optimizations
feasible elements, by using lower and upper bounds (with respect to the partial/quasi orders) 
for groups. In the present work, we use set-valued bounds for the fathoming of subproblems within 
the B&B framework and provide general convergence results. Remark that these set-valued 
bounds are particularly simple for the bi-objective linear optimization problems and are just 
pie cewise linear concave curves [10]. The method generalizes particular B&B schemes used in 
the Pareto optimization [9—11].
1. Quasiorders and partial orders [3, 8].
Definition 1 (Quasiorders and partial orders). A binary relation   on a set ℵ  is called a qua-
siorder iff
for any x∈ℵ , it holds x x  (reflectivity);
for any { , , }x y z∈ℵ , the relations x y  and y z  imply x z  (transitivity).
A quasiorder   on ℵ  is called a partial order iff, for any { , }x y∈ℵ , the relations x y  
and y x  imply x y=  (antisymmetry).
By definition, the relation x y;  means x y  and x y≠ ; the relation x y  means y x ; 
the relation x y;  means y x; .
A set ℵ  with a quasiorder (partial order) binary relation   on ℵ  is called a quasiorder 
(partial order) set/space.
Definition 2 (Optimality). A subset *X X⊂  of a quasiorder set X ⊆ℵ  is called ; -non-
dominated ((Pareto) optimal) if, for any x X∗ ∗∈ , there is no x X∈  such that x x∗; .
We now consider the space 2ℵ of all subsets of ℵ and introduce the order relations , ; in 2ℵ 
[1,8,12,13].
Definition 3 (Quasiorders and partial orders in the space of sets). Subsets ,A B⊂ℵ  satisfy 
the set relation A B  iff, for any b B∈ , there is an element a A∈  such that a b .
Subsets ,A B⊂ℵ  satisfy the set relation A B;  iff, for any b B∈ , there is an element a A∈  
such that a b; .
The notation A B , A B≺  means B A , B A; , respectively.
Lemma 1. Let the relation   be a quasiorder in ℵ . Then the corresponding set relation   is a 
quasiorder in the space of subsets of ℵ .
Let the relation   be a partial order in ℵ . Then the corresponding set relation   is a par-
tial order in the space of subsets of ℵ , consisting of mutually nondominated elements.
Example 1 (Violation of the “antisymmetry” property for the set relation ). Let 1 2a a≺  
and 1 2{ , }A a a= , 2{ }B a= . Then A B  and A B , but A B≠ .
Example 2 ({0,1}-string ordering). Let us consider a collection of {0,1} -strings S  and the 
following majority ordering “” in it:
1 2S s s S∈  , if the number of ones in 1s  is not less than the number of ones in 2s ;
1 2s s; , if the number of ones in 1s  is greater than the number of ones in 2s .
Such kind of ordering appears in maximum satisfiability problems, where the quality of a 
solution is measured by the number of conditions (e.g., inequalities) satisfied. This ordering 
is a quasiorder, but not a partial order (the antisymmetry requirement is not fulfilled). Howe-
ver, the reinforced transitivity property is fulfilled: if 1 2 2 3( , )s s s s; ; , or 1 2 2 3( , )s s s s; , or 
1 2 2 3( , )s s s s;  , then 1 3s s; .
Remark 1. If the underlying quasiorder   in ℵ  has the extended transitivity property, 
i.e., from ( , )x y y z;  or ( , )x y y z;  , it follows x z; , then the induced set relation   in 2ℵ  
18 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2019. № 1
V.I. Norkin
has a similar property. Namely, for any subsets , ,A B C ⊂ℵ , it holds true: if ( , )A B B C; ; , or 
( , )A B B C; , or ;( , )A B B C , then A C; . A similar reinforced transitivity property holds 
for the {0,1}-string ordering of Example 2.
2. Branch and Bound (B&B) method for discrete partial/quasi order optimization. In this 
section, we consider a branch and bound algorithm for finding all ; -nondominated elements 
cX
∗  of a subset cX ⊂ℵ  defined by some other quasiorders in the space ℵ . The B&B method 
treats elements of the optimization space ℵ in groups by the lower and upper boundings of jointly 
all elements in the groups. Thus, it works with a smaller number of objects than the total number 
of elements in the space. This B&B method generalizes a number of specific B&B algorithms 
(see [9—11]) for solving the vector (Pareto) optimization problems, ( ) M xR am v Vf v ∈→ , to a 
more general objective (quasiorder) space ( )f vℵ .
Assumption A. Let   be a quasiorder in a space ℵ  with the following extended transitivity 
property: for , ,x y z∈ℵ , if ( , )x y y z;  or ( , )x y y z;  , then x z; .
If the relation   is a partial order, then Assumption A is fulfilled automatically.
Assumption B. Let   be the quasiorder relation on subsets of ℵ induced (in the sense of De fi-
nition 3) by a quasiorder relation  on elements of ℵ. Assume that there are mappings , : 2 2L U ℵ ℵ→  
such that
B1: For any X ⊆ℵ , it holds true ( ) ( )L X X U X  ;
B2: If a set X ⊂ℵ  is a singleton, then ( ) ( )L X X U X= = .
Remark 2. Standard (and often poor) bounds in the vector optimization are the so-called 
ideal and nadir points [10, 11], i.e., single-valued bounds. The bounds ( )L X  and ( )U X  in as-
sumption (B1) may be sets, i.e., for any element ( )l L X∈ , there is an element x X∈  such that 
l x , and, for any element x X′∈ , there is an element ( )u U X∈  such that x u′ . Due to the 
reflexivity of the relation  , it is admissible that ( )L X X⊂ .
Example 3 (Lower set-valued bounds in vector optimization). For a vector (Pareto) opti-
mi zation problem: 1( ) [ ( )] Max ,
m
i i v Vf v f v = ∈= →  as an upper bound ( )U X  of the image set 
{ ( ) : }X f v v V= ∈ , one can take the ideal point 1( ) {max ( )} .
m
v V i iI X f v∈ ==  As a lower bound 
( )L X , one can take the set of values { ( ), }f vλ λ∈Λ  for a number of solutions { , }vλ λ∈Λ  of the 
scalarized problems: 
1
( ) maxm i i v Vi f v ∈= λ →∑ , 10 ( , , ) mm R+≠ λ = λ λ ∈Λ ⊂… .
Example 4 (Set-valued bounds in discrete problems). Consider a vector discrete optimi za-
tion problem: 1 {0,1}( ) [ ( )] Max ,n
m
i i v V
f v f v
= ∈ ⊂
= →  Standard vector bounds for the image set ( )f v =
{ ( ), }f v v V= ∈  are nadir and ideal points: 1 1( ( )) {min ( )} ( ( )) {max ( )} .,
m m
v V i i v V i iN f v f v I f v f v∈ = ∈ == =
Set-valued bounds can be constructed in the following way. Let us fix some components 
1j
v  
and 
2j
v  of v at their possible values 0 or 1 and construct lower ( ( ))L f V  and upper ( ( ))U f V  bounds 
satisfying assumption B as follows. The set-valued bound ( ( ))L f V  consists of two points: 
1 1
{ : 0} 1 { : 1} 1{min ( )} , {min ( )} .j j
m m
v V v i i v V v i if v f v∈ = = ∈ = =  (If only one set 1{ : 0}jv V v∈ =  or 1{ : 1}jv V v∈ =  
is nonempty, then only one point is used).
Similarly, the set-valued bound ( ( ))U f V  consists of the following points: 
2
{ : 0} 1{max ( )} ,j
m
v V v i if v∈ = =
2
{ : 1} 1{max ( )} .j
m
v V v i if v∈ = =
To get better bounds, one can fix more components 1,jv j J∈  and 2,jv j J∈  of v on their all 
possible values. In this case, the bounds ( ( ))L f V  and ( ( ))U f V  consist of 1| |2 J  and 2| |2 J  points, 
respectively. What variables to fix to get good bounds is a (research) question.
19ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2019. № 1
B&B method for discrete partial order and quasiorder optimizations
Example 5 (Multiattribute optimization). The problem is to find nondominated multiattri-
bute entries in big data sets. It is assumed that separate attributes take on values in completely 
ordered sets. This problem can be solved by both an enumerative pairwise comparison algorithm 
and by the B&B algorithm. The latter algorithm firstly finds an interval for the data, e.g., nadir 
and ideal points, subdivides it into smaller subintervals and finds nadir/feasible and ideal points 
for these subintervals, refines the family of subintervals from empty and dominated ones, and 
continues the subdivision and refinement procedures until the nondominated subintervals be-
come singletons.
Example 6. Let { : ( ) }( ) { ( ), } Max k K k kM j v V g v cF v f v j M ∈∪ ∈= ∈ →   be a multicriteria optimi za-
tion problem with finite or infinite sets M , K  of criteria and constraints. By defining ( )KG v =
{ ( ), }kg v k K= ∈ , { }K k K kC c∈= ∪ , the latter problem can be rewritten in the form ( )MF v →
{ : ( ) }Max K Kv V G v C∈→  , i.e., by means of the quasiorder set relation “ ”.
Example 7 (Multilevel multicriteria and multilevel partial/quasi order optimization prob-
lems). A multicriteria (or partial order) optimization problem 1Max ( )v V F v∈  usually singles out 
a whole Pareto-optimal set of nondominated solutions ∗ ⊂V V  and the corresponding effi-
cient frontier 1( )F V
∗ , e.g., an efficient frontier in the financial portfolio analysis. The second step 
in analyzing the problem is to define the second mapping (partial order relation) 2 2: ( )F V F V→  
to select a narrower subset of nondominated solutions, and so on.
Suppose we have found an approximation C  of the Pareto-efficient set 1( )F V
∗ , for exam-
ple, consisting of a finite collection of elements, 1{ , , }nC c c= … . Then the second stage prob-
 lem may have the form: 
1{ , ( ) } 2
Max ( )v V F v C F v∈  , i.e., is given by means of the quasiorder set 
re lation “ ”.
Problem setting. Suppose there are several quasiorders i , 0, , ,i n= …  defined on the same 
(objective) space ℵ . Define the relations ix y;  as ix y  and x y≠ . Corresponding set rela-
tions i  and i;  for subsets of ℵ  are defined in Definition 3.
Define the feasible set { : , 1, , }c i i i iX x X C x D i n= ∈ ⊆ℵ = …  , where iC ⊂ℵ , iD ⊂ℵ, 
1, , ,i n= … . Remark that the condition i iC x  means { : }ic C ix x x c∈∈ ∈ℵ′ ′∩   and i ix D  
means { : }
id D i
x x x d∈∈ ∈ℵ′ ′∪  .
The problem is to check if cX ≠ ∅  and, in the latter case, to find the set cX∗  of 0; -nondo-
minated elements in cX . The set cX  can be (very) large, so the enumerative search may be ques-
tionable. The following B&B algorithm solves the problem by means of lower ( )iL ⋅  and upper 
( )iU ⋅  bounds of subsets of ℵ . We assume that these bounds satisfy Assumptions A, B. The ac-
celeration of the search is due to a group evaluation of elements of ℵ . The following B&B al-
gorithm solves the set problem.
Constrained Branch and Bound algorithm (CBB-algorithm).
Step 0 (Initialization). Form an initial finite partition 0 { : 1, 2, }
pP X p= ⊂ℵ = …  such that 
p
pX X⊆ ∪ . Calculate bounds ( )piL X  and ( )piU X  for all 0pX P∈ , 0,1, , ,i n= … . Set 0k = .
Step 1 (Remove infeasible partition sets). Clean the partitions kP  from certainly infeasible 
sets, i.e., put : { : , or ( ), or ( )  for some }.p p p pk k k i i i iP P X P X X C U X L X D i= ∈ =∅ / /∩5  
Step 2 (Remove non-optimal partition sets). Clean the partitions kP  from sets not containing 
optimal points, i.e., put = ∈ ∈≺0 0 0: { : ( ) ( ) for some singleton }.p p q qk k k kP P X P U X L X X P5
Step 3 (Look for partition sets with nondominated upper bounds). Find all 0U -nondominated 
partition sets p kY P∈  such that there is no other partition set k
qX P∈  with 0 0( ) ( )
q pU X U Y; .
20 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2019. № 1
V.I. Norkin
Step 4 (Check for the stopping conditions). If the partition kP  is empty or all 0U -non-
dominated partition sets p kY P∈  are singletons, then Stop.
Step 5 (Partitioning). If there is an 0U -nondominated non-singleton partition set 
p
kY P∈ , then 
form a partition of this set ( ) { , 1, 2, }k kk iP Y Y i′′ = ≠ ∅ = …  such that k ki iY Y= ∪  and k ki i jY Y =∅∩  
for , ( ),k k ki j kY Y P Y i j′′∈ ≠ . Define the new full partition : ( ) ( ).
k k
k k kP P Y P Y′′= ∪5  Elements of 
kP  will also be denoted as 
pX .
Step 6 (Estimation of bounds). For all new subsets p k kX P P′′∈ ⊂ , calculate lower ( )
p
iL X  
and upper ( )piU X  bounds, 0,1, , ,i n= … ; for other subsets p kY P∈ , bounds remain the same. Put 
: 1k k= +  and go to Step 1.
Theorem (Convergence of the CBB-algorithm). Assume that the lower and upper bounds ,i iL U  
satisfy conditions A, B for each 1, , ,i n= … . Then the following statements regarding the CBB-
algorithm hold true.
(a) If the space ℵ  is finite and the feasible set cX  is empty, then the CBB-algorithm stops 
after a finite number k′  of iterations with the empty partition kP ′ ≠ ∅ .
(b) If cX ≠ ∅  and cX  is finite, then the optimal ( 0; -nondominated) set cX∗ ≠ ∅ , and no ele-
ment of the cX
∗  is deleted in the course of iterations of the CBB-algorithm.
(c)  If in the course of iterations the CBB-algorithm generates a singleton 0U -nondiminated 
partition set ∈p kY P , i.e., such a singleton set that there is no other partition set k
qX P∈  such that 
0 0 0( ) ( )
q pU X U Y; , then p cY X∗∈ .
(d) If the space ℵ  is finite, then the CBB-algorithm stops after a finite number of iterations k′. 
In this case, the set of singleton 0U -nondominated partition sets 
p
kY P ′∈  generated by the CBB-
al gorithm coincides with the optimal set cX
∗ .
Proof. (a) If the space ℵ  is finite, then the CBB-algorithm stops after a finite number of 
iterations k′ , since there may be only a finite number of partition steps. Suppose cX =∅ , but 
kP ′ ≠ ∅ . The partition kP ′  contains singleton sets pY y= ; otherwise, the algorithm did not stop 
at iteration k′ . Since the algorithm passed Step 1 before stopping, pY y X= ∈ , ( )pi i iC U Y , and 
( )pi i iL Y D  for all i . By assumption (B2), ( ) ( )
p p
i iy L Y U Y= =  for all i . Hence, cy X∈ ≠∅ . 
We get a contradiction.
(b) Suppose the opposite: at some iteration k′ , a point cx X
∗ ∗∈  is deleted. It can be deleted 
only at Step 2 of the CBB-algorithm. This means that there are partition sets ,p q kX X P ′∈  such 
that px X∗ ∈  and 0 0( ) ( )
p qU X L X;  for some singleton q q kX x P ′= ∈ . Since the algorithm passed 
Step 1, qx X∈ , ( ) qqi i iC U X x= , ( )
q
i
q
ix L X D=   for all i , and, hence, q cx X∈ . Since, by (B1), 
0( )
p pX U X , for px X∗ ∈ , there is an element 0( )
ppu U X∈  such that px u∗  . For 0( )
ppu U X∈ , 
by the definition of the dominance relation 0≺  and (B2), from 0 0 0( ) ( )p q qU X L X x=≺ , it follows 
that 0
p qu x≺ . By the transitivity of the relations 0≺ , 0 , we obtain * 0 0p qx u x≺ . Hence, 
0 c
qx x X∗ ∈≺ , which means that x∗ is not an 0; -nondominated element of cX , a contradiction.
(c) Suppose the opposite that, at some iteration k , there is a singleton 0U -nondiminated 
partition set k
kY Py= ∈  such that k cY X
∗∉ . Then there is an element cx X∈  such that 0x y; . 
Moreover, due to the theorem assumptions, there is an element cx X
∗ ∗∈  such that * 0 0x x y; . By 
(b), the element x∗ is not deleted, so there is a partition set p kX P∈  such that 
px X∗ ∈ . By (B1), 
(B2), the following relation holds true: *0 0 0 0( ) ( )
p kU X x y U Y=; , i.e., 0 0( ) ( )p kU X y U Y=; , 
which means that kY  is not an 0U -nondominated partition set in kP , a contradiction.
21ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2019. № 1
B&B method for discrete partial order and quasiorder optimizations
(d) Due to the finiteness of the number of elements in X , there can be only a finite number 
of iterations with the partitioning of sets. So, there exists an iteration k′  such that all 0U -non-
dominated partition sets become singletons, k kY y′ ′= , and the CBB-algorithm stops. Then, 
by (c), all such sets k k cY y X
′ ′ ∗
= ∈ .
Let the algorithm stoped at the iteration k′  and let some ˆ cx X
∗∈ . By (b), xˆ  was not removed 
in the course of iterations. Hence, there exists a partition set ˆ k kX P
′
′
∈  such that ˆˆ kx X ′∈  and, by 
(B1), 0 0 ˆˆ ( )
kx U X ′ . Let us show that the set ˆ kX ′ cannot be 0U -dominated. Suppose the opposite. 
Then there is a finite sequence of partition sets 1{ }
k I
i k iX P
′
′ =
∈  such that 0 0 0 1ˆ( ) ( )
k kU X U X′ ′≺ , 
0 0 0 1
ˆ( ) ( )k kiU X U X
′ ′
+≺ , 0 0 0 ˆ( ) ( )k kIU X U Y′ ′≺ , and ˆk kY P′ ′∈  is 0U -nondominated. Hence, the set ˆˆk ky Y′ ′=  
is a singleton and, by (c), it belongs to cX
∗. Thus, 0 0 0 0ˆ ˆˆ ˆ( ) ( )
k k kx U X U Y y′ ′ ′=≺  and, hence, 
*
0ˆ ˆ
k
cx y X
′
∈≺ , which means that ˆ cx X∗∉ , a con tradiction. Hence, the set ˆ ˆkX x′ ∋  is 0U -nondomi-
nated. Then ˆ kX ′  is a singleton and ˆˆ k kx X P
′
′
= ∈ . On the other hand, by (c), all 0U -nondominated 
singleton partition sets p kX P ′∈  belong to cX
∗ . The proof is completed.
3. Conclusions. We have analyzed a general framework for the discrete branch and bound 
(B&B) methods designed to find optimal (i.e. nondominated) elements in a partial order or qua-
siorder (with certain extended transitivity property) space. The framework generalizes particu-
lar B&B schemes from the vector optimization to more general objective spaces. For example, the 
space may be an infinite-dimensional vector space, space of strings with ordered components, 
space of sets with a defined partial or quasiorder relation. We have also considered the so-called 
constrained quasiorder optimization problems involving several partial/quasi orders. Solutions 
of the problems are understood as nondominated points of the feasible or objective set. A non-
standard element of the considered B&B framework is that it exploits set-valued (including sin-
gle-valued) lower and upper bounds for subsets generated by the algorithm. As a lower bound, any 
subset of feasible points may be used. For a finite discrete feasible set, the B&B algorithm either 
finds all optimal elements or discover that the feasible set is empty.
Thus, the paper extends horizons of optimization theory to general spaces, not necessary lin-
ear or metric, only the order is important. The further research may be devoted to the exploration 
of the efficiency of the developed B&B method on particular classes of problems and to its exten-
sion to the continuous case.
REFERENCES
  1. Eichfelder, G. & Jahn, J. (2012). Vector optimization problems and their solution concepts. In Ansari, Q.H. 
& Yao, J.-C. (Eds.). Recent Developments in Vector Optimization (pp. 1-27). Berlin: Springer.
  2. Ehrgott, M. (2005). Multicriteria Optimization. 2nd ed. Berlin, Heidelberg: Springer.
  3. Gorohovik, V.V. (1990). Convex and nonsmooth problems of vector optimization. Minsk: Navuka i tehnika 
(in Russian).
  4. Sawaragi, S., Nakayama, H. & Tanino, T. (1985). Theory of multiobjective optimization. Orlando: Academic Press.
  5. Fattore, M. & Bruggemann, R. (Eds.) (2017). Partial order concepts in applied sciences. Cham: Springer 
International Publishing AG.
  6. Dentcheva, D. & Ruszczyński, A. (2003). Optimization with stochastic dominance constraints. SIAM J. 
Optim., 14, pp. 548-566. doi: https://doi.org/10.1137/S1052623402420528
  7. De Simone V., Marino, M. & Toraldo, G. (2009). Isotonic regression problems. In Floudas, C.A. & Pardalos, 
P.M. (Eds.). Encyclopedia of optimization. 2nd ed. (pp. 1774-1777). Boston, MA: Springer.
  8. Khan, A. A., Tammer, C. & Zălinescu, C. (2015). Set-valued optimization. An introduction with applica-
tions. Berlin, Heidelberg: Springer.
22 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2019. № 1
V.I. Norkin
  9. Gavanelli, M. (2001). Partially ordered constraint optimization problems. In: Walsh, T. (eds.). Principles and 
practice of constraint programming — CP 2001. CP 2001. Lecture Notes in Computer Science, Vol. 2239. 
Berlin, Heidelberg: Springer. doi: https://doi.org/10.1007/3-540-45578-7_64
10. Przybylski, P. & Gandibleux, X. (2017). Multi-objective Branch and Bound. Eur. J. Oper. Res. 260, Iss. 3, 
pp. 856-872. doi: https://doi.org/10.1016/j.ejor.2017.01.032
11. Norkin, V. I. (2017). B&B solution technique for multicriteria stochastic optimization problems. In Butenko, 
S., Pardalos, P. & Shylo V. (Eds.). Optimization methods and applications (pp. 345-378). Cham: Springer. 
doi: https://doi.org/10.1007/978-3-319-68640-0_17
12. Nishnianidze, Z. G. (1984). Fixed points of monotone multivalued operators. Soobshch. Akad. Nauk Gruzin. 
SSR, 114, No. 3, pp. 489-491.
13. Yang, X. Q. (1992). A Hahn—Banach theorem in ordered linear spaces and its applications. Optimization. 25, 
No. 1, pp. 1-9.
Received 18.10.2018
В.I.Норкiн
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ
НТУ України “Київський політехнічний інститут ім. Ігоря Сікорського”
E-mail: vladimir.norkin@gmail.com
МЕТОД ГIЛОК ТА МЕЖ ДЛЯ ДИСКРЕТНОЇ ОПТИМІЗАЦIЇ 
В ЧАСТКОВИХ АБО КВАЗIПОРЯДКАХ
У роботi метод гiлок i меж/оцiнок (B&B-метод) поширюється на задачi пошуку недомiнованих елементiв 
у частково або квазiупорядкованій множині. B&B-метод застосовується до задач оптимiзацiї, де допусти-
ма множина сама визначається сiмейством квазiпорядкiв. Структура узагальненого B&B-методу є стан-
дартною: вiн включає в себе розбиття на пiдзадачi, оцiнювання пiдзадач i вiдбраковування пiдзадач, але 
оцiнки пiдзадач вiдрiзняються, вони можуть бути множинами. Для оцiнювання пiдзадач метод викорис-
товує впорядкування множин у такому сенсi. Одна множина “менша або дорiвнює” iншій, якщо для будь-
якого елемента першої множини iснує “бiльший або рiвний” елемент у другiй. У B&B-методi розбиття за-
стосовується до пiдзадач з недомiнованими верхнiми оцiнками. Пiдзадачi з малими верхнiми оцiнками 
(менше деякої нижньої оцiнки) видаляються. Встановлено збiжнiсть методу до множини всiх недомiнованих 
елементiв. Прискорення по вiдношенню до переборного пошуку досягається за рахунок групової оцiнки 
елементiв вихiдного простору.
Ключові слова: квазіпорядок, частковий порядок, недоміновані розв’язки, дискретна оптимізація, метод 
гілок та меж.
В.И.Норкин
Институт кибернетики им. В.М. Глушкова НАН Украины, Киев
НТУ Украины “Киевский политехнический институт им. Игоря Сикорского”
E-mail: vladimir.norkin@gmail.com
МЕТОД ВЕТВЕЙ И ГРАНИЦ ДЛЯ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ 
В ЧАСТИЧНЫХ ИЛИ КВАЗИПОРЯДКАХ
В работе метод ветвей и границ (B&B-метод) распространяется на задачи поиска недоминируемых точек 
в частично или квазиупорядоченном множестве. B&B-метод применяется к задачам оптимизации, где до-
пустимое множество само определяется семейством квазипорядков. Структура обобщенного B&B-метода 
является стандартной: он включает в себя разбиение на подзадачи, оценки подзадач и отбраковку подзадач, 
но оценочные границы отличаются, они могут быть множествами. Для оценивания подзадач метод 
использует упорядочение множеств в следующем смысле. Одно множество “меньше или равно” другому, 
если для любого элемента первого множества существует “больший или равный” элемент во втором. В 
B&B-методе разбиение применяется к подзадачам с недоминируемыми верхними границами. Подзадачи 
с малыми верхними границами (меньше некоторой нижней границы) удаляются. Установлена сходимость 
метода к множеству всех недоминированных точек. Ускорение по отношению к переборному поиску 
достигается за счет групповой оценки элементов исходного пространства.
Ключевые слова: квазипорядок, частичный порядок, недоминируемые решения, дискретная оптимизация, 
метод ветвей и границ.