=Paper=
{{Paper
|id=Vol-2533/paper8
|storemode=property
|title=A Spherical Cutting-plane Method with Applications in Multimedia Flow Management
|pdfUrl=https://ceur-ws.org/Vol-2533/paper8.pdf
|volume=Vol-2533
|authors=Oksana Pichugina,Nadezhda Muravyova
|dblpUrl=https://dblp.org/rec/conf/dcsmart/PichuginaM19
}}
==A Spherical Cutting-plane Method with Applications in Multimedia Flow Management==
https://ceur-ws.org/Vol-2533/paper8.pdf
A Spherical Cutting-plane Method With Applications In
Multimedia Flow Management
Oksana Pichugina1,2[0000-0002-7099-8967] and Nadezhda Muravyova3[0000-0002-8307-2290]
1 National Aerospace University "Kharkiv Aviation Institute", 17 Chkalova Street, 61070
Kharkiv, Ukraine
2 Brock University, 1812 Sir Isaac Brock Way, St. Catharines, ON L2S 3A1, Canada
o.pichugina@khai.edu, op13ci@brocku.ca
3
South Ural State University, 76 Lenin Av., 454080 Chelyabinsk, Russia
muravevanv@susu.ru
Abstract. An important problem in Multimedia Flow Management of schedul-
ing jobs on identical parallel machines aiming to minimize total completion
time is studied. Based on the problem peculiarities, the prominence of applying
cutting-plane approaches is justified. A new such approach called a spherical
cutting-plane method (SСPM) is developed for solving linear permutation-
based problems. It uses a fundamentally new way to construct cutting planes for
sets inscribed into a hypersphere, and it is superior to existing methods of the
optimization problems’ class. The generic SCPM is adapted to the scheduling
problem under consideration. For that, the problem’s statement as a linear par-
tially combinatorial permutation-based problem is built, and the SCPM is gen-
eralized for solving partially combinatorial problems.
Keywords: Scheduling, parallel machines, cutting plane method, permutation-
based problem, Euclidean combinatorial problem, spherical-located set,
well-described set.
1 Introduction
In the Smart Multimedia field, minimizing the completion time of jobs on parallel
machines and solving other scheduling problems are inevitable components of
efficient Multimedia Flow Management [1]. Most of the problems belong to a class of
combinatorial or partially combinatorial optimization problems resulting in their
higher computational complexity [1-3]. As a field of Optimization Theory, Combina-
torial Optimization offers a variety of methods and algorithms to solve the problems
of lower dimension exactly or get an approximate solution of the ones of high dimen-
sion in a reasonable time [4-7]. Nevertheless, steadily increasing demands to the solu-
tions’ accuracy along with a reduction in the time of their obtaining results in a need
to develop new optimization approaches for both generic and special statements of the
problems [1-3,8,9].
In this paper, a new method of partial combinatorial optimization, called a spheri-
cal cutting-plane method (SCPM), is offered for solving a scheduling problem for
Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0)
2019 DCSMart Workshop.
jobs with non-identical job sizes processed on parallel machines having the same
capacity, which aims to minimize total completion time. For that, a new mathematical
model of the problem as a linear partial permutation-based program is built, the ge-
neric SCPM is justified and then is adapted to solving the scheduling problem.
2 Problem Statement
The problem of scheduling jobs on identical parallel machines to minimize total com-
pletion time may be stated as follows [8-10]. Each of n jobs (numbered A1 , ..., An ) is
to be processed on one of m identical parallel machines (numbered M 1 ,..., M m ). No
machine can handle more than one job at a time. Each job Ai is available for pro-
cessing at time zero and requires a positive integer processing time t j on the machine
to which it is assigned ( j J n 1, , n ). The objective is to find a schedule that
minimizes the completion time of all these jobs.
Let P j jI '
i
iJ m
, I i' ni , i J m be a partition of the jobs induced the
schedule, where A j jI i" are jobs completed at the machine M i ( i J m ).
The completion time T is a maximum of completion time in each of the machines.
Thus,
T max Ti , where Ti t i , i J m . (1)
iJ m
jI i'
It is required to determine such a partition, where T is minimized. Thus, an issue
is to find the partition:
T min , (2)
where additional constraints
PP , (3)
are satisfied, where P is a set of admissible partitions.
Due to the presence of max(.) in the formulation of the problem (1)-(3) (further re-
ferred to as Problem 1), this one is a nonlinear partially combinatorial problem given
in the form of its combinatorial statement. Here, the real-valued variable is T . The
statement is suitable for algorithmization if (3) is missing, and heuristics based on
generating the partitions are applied [11-15]. The situation gets worse if additional
constraints are present, which is a typical case in practical applications [11,16,17].
Therefore, it is often not so easy to find the required number of feasible partitions to
apply these heuristics and metaheuristics. Moreover, in many cases, a feasibility prob-
lem needs to be solved to get any of the feasible partitions [18].
In this paper, we propose a technique for solving Problem 1, provided that an ap-
proximate solution yielding T T ** has been found. The approach is based on em-
bedding Problem 1 in Euclidean space and then treating it as a linear partially discrete
optimization problem.
First, examine Problem 1 in order to reformulate it as a linear permutation-based
optimization problem [12,13]. For that, at first, define a dimension of Euclidean space
for the embedding. Let n min , n max be a minimal and maximal number of the jobs
scheduled on a single machine.
Without loss of generality, assume that t1 ... t n , then
n min n min 1 n max n min 1
n min , n max : t ni 1 T ** , t ni 1 T ** ; t i T ** , t i T ** .
i 1 i 1 i 1 i 1
Now, set the dimension of Euclidean space as follows – N m n . After, we max
complement the multiset t i iJ by N n dummy zeros and form a multiset
n
G g i iJ
N
t i iJ 0 N n : g1 ... g n ,
n
(4)
with exactly k different values S G ei iJ : 0 e1 ... e k .
k
Introduce a vector of variables
x x11 ,..., x
1n max
,..., x m1 ,..., x
mn max .
In these denotations, Problem 1 can be formulated as finding x R N :
n max
z max xij min , (5)
iJ m j 1
x E Nk G , (6)
where E Nk G – is a basic generalized set of Euclidean permutation configurations
(the generalized permutation b -set) induced by G [19,20]. The problem (5), (6) – is
a nonlinear nondifferentiable Euclidean combinatorial problem [19,21], which be-
comes much easier for dealing with by its lifting into space R N 1 . For that, let us
N
introduce an additional variable y R10 such that y max x ij . Now, (5) is re-
iJ m j 1
written as – find x, y , z :
z y min , (7)
subject to (6) and constraints
N
xij y 0, i J m . (8)
j 1
Assume that, if constraints (3) are present, then after the embedding, they become
linear and are of the form:
A" x b" 0, A" R m' N , b" R m' . (9)
The obtained problem (6)-(9), further referred to as Problem 2, is a linear con-
strained partially permutation-based problem with a single real-valued variable y .
3 The relevance of developing a cutting-plain approach to
Problem 2
Problem 2 belongs to such a class of Euclidean linear partially combinatorial prob-
lems:
f x, x' cx c' x' min , (10)
subject to c R N , c' R n' ,
Ax A' x' b, where A R M N , A' R M n' , b R M , M m' m , (11)
xE RN , E , (12)
where E E Nk G , n' 1 .
Numerous features of set E Nk G underlie various optimization methods of solv-
ing problems such as (10)-(12).
One of the properties is that E Nk G lies on a hyperplane and hyperspheres cen-
tered at a a e , where a R 1 \ is a parameter, e is a vector of units [14]. In the
family is a circumsphere of minimal radius corresponding to the parameter
1 N
a g i . It results in another peculiarity of crucial importance for us that
N i 1
E Nk G coincides with a vertex set of a polytope PNk G conv E Nk G . Such
a set is called vertex-located (VLS) [22].
The class E Nk G is intensively studied the last couple of decades [4,11-
16,19-25] in various directions, most of which concern optimization. Here, we outline
the main approaches to solving linear permutation-based problems based on utilizing
the above properties. First, there is a method of tightening constraints presented in
[21] for solving linear combinatorial programs. Let us formulate its generalization for
partially combinatorial linear programs. First, additional constraints (11) need to be
replaced by Ax A' x ' b , where R M is chosen in a specific way. Then the
original partially combinatorial problem is replaced by a polyhedral relaxation of the
new problem. Finally, the relaxation’ solution x 0 , x' 0 is rounded combinatorially
thus yielding a point y 0 , y' 0 , where y 0 E . depends on E and is chosen such,
that y 0 , y ' 0 is an admissible solution, i.e., x** , x'** y 0 , y ' 0 . The method of
tightening constraints is approximate, which can be effectively combined with exact
approaches. One of the exact techniques is a polyhedral-spherical method [23], which
is a Branch&Bound approach exploiting simultaneously polyhedral-sphericity of E ,
its decomposition into generalized permutation b -sets of lower dimension lying in
parallel hyperplanes [23]. In [26], some graph-theoretic approaches to solving such
optimization problems, both exact and approximate, are offered. They explore an
equivalent statement of these problems as optimization ones on a node-set of graphs
extracted from a transposition graph [27]. One more important group of methods is
cutting-plane ones [28-31]. Among them are a combinatorial cutting method [29,30],
combinatorial polytope cutting method [31], surface cutting method [31]. They are
based on the absence of admissible solutions in an interior of faces on any dimension,
as well as on most of circumsphere. All the exact methods are intended to solve com-
binatorial programs only. Thus, they require developing relevant generalization to the
partially combinatorial case. The only exception is the combinatorial cutting method,
which has been reformulated for partially combinatorial programs in [29]. An issue of
applying the listed cutting-plane techniques is that they require finding a set of adja-
cent vertices to solutions of auxiliary polyhedral relaxation problems (the solutions’
neighborhood). It is caused by, generally, the exponential on N number of con-
straints in an H-representation of PNk G making impossible processing the whole
collection of PNk G -constraints. It turns out that it is sufficient to involve incon-
siderable part of the H-representation [21]. However, in this case, to extract the
above-mentioned neighborhood becomes problematic. Therefore, in this paper, we
aim to develop a new cutting-plane method SCPM for solution linear constraint per-
mutation-based and partially permutation-based problems, which utilizes solutions of
polyhedral relaxation problems, spherical locality of E Nk G , and properties of
linear functions over the set. Our final goal is to adapt this method for solving Prob-
lem 2.
4 Cutting-plane method for linear optimization on WD-SpLSs
Consider an optimization problem of finding x such that
f x cx min (13)
subject to constraints
Ax b, A R M n , b R M , (14)
x E Sr a Rn , (15)
E is a well-described set (WDS), (16)
where S r a – is a hypersphere centered at a R n with a radius r 0 . The condi-
tion (16) means that the problem (13) is effectively solvable on , i.e., it is polynomi-
ally solvable [32]. The condition (15) implies that is a spherically-located set (SpLS)
[16,17]. Thus, the problem (13)-(16) is a general linear constraint optimization prob-
lem (further Problem 3) on SpLS and WDS E (further WD-SpLS). The conditions
(15), (16) allow using specifics of WD-SpLS in optimization, in particular, when
cutting-plane optimization schemes are developed.
Theorem 1. If E is SpLS, then for any x 0 R n , there exists c R n such that
problems (13) and
2
h x x x0 min (17)
xE
are equivalent.
Proof. Let us assume that SpLS E satisfies (15), wherefrom
2
r2 xa x 2 2ax a 2 . (18)
E
Single outing x 2 from (18) and substituting it in (17) yield
x 2 2xx 0 x 0 r 2 2ax a 2 2xx 0 x 0
2 2 2
h x x x0
2 a x0 x r 2 a2 x0 .
2
The expression can be rewritten as follows:
.
2
h x cx d , where c =2 a x 0 , d = r 2 a 2 x 0 (19)
In (19), d is a constant; hence the projection problem (17) has been reduced to a
minimization of linear function cx d , which is equivalent to the problem (13),
where c is found from (19).
Corollary 1. If E is WD-SpLS, then, for any x 0 R n , the projection problem
(17) is polynomially solvable.
Indeed, in this case, (17) is reducible to a linear program over E , which is effec-
tively solvable by definition of WDS.
4.1 SCPM outline
The spherical cutting-plane method (SCPM) is an iterative approach, and it will be
stated in terms of a single iteration.
Let l J L0 J L 0 be an iteration number, where an iteration numbered 0 is
initial, while the one numbered L is last. On iteration l , a linear program (13) under
constraints (15), (16),
l l
Al x b l , Al R m n , b l R m (20)
is solved (further Problem 3.l), which is equivalent to Problem 3, through its contin-
uous relaxation. For that, the constraint (15) is replaced by
x P conv E S r a . (21)
For instance, if E is finite, P will be a polytope, respectively, the problem (13),
(16), (20), (21) (further Problem 4.l) is a polyhedral relaxation of Problem 3.l.
Let a solution of Problem 3 be denoted x* , z * x* ,cx* , of Problem 4.l –
x l , z l x l , cx l .
Step 0. On initial iteration l 0, A0 A, b 0 b, m 0 M .
Step l. On iteration l , if x l E, then x* , z * x l , z l , end. If x l E , we
form a cut for x l . For that, find a projection y l of the point x l onto E :
y l Pr E x l . (22)
By construction, y l x l , thus there exists a sphere S l of a positive radius cen-
tered at x l having no points in common with E , which can be cut off from a feasible
domain of the Problem 4.l. Choose S l S l x l , where
r
r l yl xl ,
2 2
(23)
because this sphere contains no points of E in an interior. So, a deep nonlinear cut of
x l E is
x xl r l ,
2 2
(24)
which can be added to the current constraints. An issue is that the constraint (24) is
nonlinear. Moreover, it is concave. Therefore, the utilization of (24) makes a new
problem harder than it was. Meanwhile, it is easy to see that the cut is not unique, and
it is possible to find a linear constraint cutting off x l and the relevant cutting plane.
Let us construct the cutting plane based on Theorem 1. Preliminarily, the theorem
will be generalized as follows, 0 l, h x h l x , c c l , d d l , l J L0 .
Corollary 2. If E is SpLS, then for any x l R n , there exists c l R n such that
2
problems c l x min and hl x x xl min are equivalent, namely,
xE xE
.
2
h l x c l x d l , where c l =2 a x l , d l = r 2 a 2 x l (25)
Now, inequality (24) can be rewritten equivalently on
E r x x h x E c x d or
l 2 l 2 l l l
,
2
cl x d l r l (26)
where r l is given by (23), c l , d l – by (25).
, hence c l x d l r l is a cutting plane for
2 2
By construction, c l x l d l r l
x l . Instead of (24), let us add inequality (26) to the current constraints (20) obtaining
input data Al 1 , b l 1 for Problem 3.(l+1).
Set l l 1, ml ml 1 1 . Go to solving Problem 3.l through Problem 4.l. Repeat
until the method terminates, which can occur, if the maximal number of iteration has
been reached, x* was found, the current lower and upper bound coincide (then
x* , z * x** , z ** ), or incompatibility of Problem 4.l was proven.
Remark 1. Throughout the iterative process, a lower bound z lb on z * are con-
stantly improved. Namely, by construction, z 0 z 1 ... z L that is why: a) initially
z lb z 0 ; b) on iteration 1, z lb max z 1 , z lb z 1 ; …; c) on iteration L
z Lb max z L , z Lb z L . In order to reduce a search domain, it makes sense to
solve a feasibility problem of finding admissible point x ** of Problem 3 and then to
monitor improving the initial upper bound z ub z ** cx** . The current upper
bound is improved on iteration l , if the point (22) satisfies (14), and
z ub
cy , wherefrom z min z y l , z lb z y l .
z y l l ub
For the increasing probability of improving the upper bound in such a way, it is
worthful to explore a whole projection PrE x l of x l onto E , which implies replac-
ing formula (22) by Y l PrE x l . Now, if Y l E , there is a chance to
improve the current lower bound if the whole neighborhood is examined.
5 Adaptation SCPM to Problem 2
Let us adjust the SCPM to solving the general linear partially combinatorial problem
(10) (12). The following substitution will be made in the SCPM and formulations of
.
. ' .
Problems 3.l, 4.1: n N , x x , x , c c,c' ; (20) should be replaced
by
m l N n' l
A l x, y b l , A l R , bl R m , (27)
z cx c ' x , where A 0 A, A' , . l,*,** .
. . ' .
Step l is reformulated as follows: on iteration l, if
x l E, then x* , y* , z* x l , y l , z l , end. If x E , then find y l by (22)
l
and form a cut for x l in accordance to (26).
To the generalization of the SCPM (further referred to as a generalized SCPM
(GSСPM)). It is directly applicable to solving Problem 2. For that, constraints (8), (9)
are presented in the form of (11), where n' 1, x l y . Matrix A 0 is of the dimen-
sion m 0 m m ' by N 1 , the objective function vector in (10) is c,c' 0,1 ,
where 0 R N is a zero-vector.
Remark 2. When solving Problem 2 by the GSCPM, a search domain can be re-
duced depending on the type of values of elements in (4). Without loss of generality
assume that a greatest common divisor GCD t i iJ n
1, then an initial lower
1 n
bownd will be z lb t i . At the same time, an initial upper bound can be
m i 1
found by a well-known heuristic, where the least filled bin associated with a machine
is filled first, while jobs are considered in random order. Then the initial bin packing
may be improved by adjacent transposition of a vector x ** associated with this pack-
ing.
Conclusion
An actual problem of organizing effective parallelization of a job batch is considered.
This problem is modeled as linear constrained partially combinatorial. For linear con-
strained problems over well-described spherically-located sets, such as permutation
set, Boolean set, or permutation matrices’ set, a special exact solution method is of-
fered, called a spherical cutting-plane method (SСPM).
The SСPM is generalized to solving partially combinatorial problems resulting in
the generalized SСPM (GSСPM) and is adapted for the scheduling problem under
consideration. SСPM and GSСPM can be applied to a wide class of real-world prob-
lems in which combinatorial structures are singled out, such as permutations and
Boolean vectors [2-13,23-26,33-35]. It can also be generalized to nonlinear combina-
torial and partially combinatorial problems [36-40], where, in order to solve optimiza-
tion problems globally, our method should be combined with the convex extension
theory [16,17,20,23] and continuous functional representation theory [17,20,22].
References
1. Basu, A., Berretti, S. eds: Smart Multimedia: First International Conference, ICSM 2018,
Toulon, France, August 24–26, 2018, Revised Selected Papers. Springer (2018).
2. Oliveira, C.A.S., Pardalos, P.M.: A survey of combinatorial optimization problems in mul-
ticast routing. Computers & Operations Research. 32, 1953–1981 (2005).
https://doi.org/10.1016/j.cor.2003.12.007.
3. Szkaliczki, T.: Combinatorial Optimization Problems in Multimedia Delivery. Handbook
of Research on Emergent Applications of Optimization Algorithms. 67–92 (2018).
https://doi.org/10.4018/978-1-5225-2990-3.ch004.
4. Yemelichev, V.A., Kovalëv, M.M., Kravtsov, M.K.: Polytopes, graphs and optimisation.
Cambridge University Press, Cambridge (1984).
5. Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer Science &
Business Media (2002).
6. Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. Springer, New
York, NY (2018).
7. Sergienko, I.V., Shilo, V.P.: Discrete Optimization Problems: Issues, Solution Methods,
and Investigations. Naukova Dumka, Kyiv (2003).
8. Cheng, B., Yang, S., Hu, X., Chen, B.: Minimizing makespan and total completion time
for parallel batch processing machines with non-identical job sizes. Applied Mathematical
Modelling. 36, 3161–3167 (2012). https://doi.org/10.1016/j.apm.2011.09.061.
9. Low, C., Lin, W.-Y.: Minimizing the total completion time in a single-machine scheduling
problem with a learning effect. Applied Mathematical Modelling. 35, 1946–1951 (2011).
https://doi.org/10.1016/j.apm.2010.11.006.
10. Belouadah, H., Potts, C.N.: Scheduling identical parallel machines to minimize total
weighted completion time. Discrete Applied Mathematics. 48, 201–218 (1994).
https://doi.org/10.1016/0166-218X(92)00176-M.
11. Butenko, S., Pardalos, P.M., Shylo, V. eds: Optimization Methods and Applications : In
Honor of Ivan V. Sergienko’s 80th Birthday. Springer International Publishing, Cham
(2017).
12. Gmys, J.: Heterogeneous cluster computing for many-task exact optimization - Applica-
tion to permutation problems, https://hal.inria.fr/tel-01652000/document, (2017).
13. Mehdi, M.: Parallel Hybrid Optimization Methods for permutation based problems,
https://tel.archives-ouvertes.fr/tel-00841962/document, (2011).
14. Yakovlev, S., Kartashov, O., Pichugina, O., Korobchynskyi, K.: Genetic Algorithms for
Solving Combinatorial Mass Balancing Problem. In: 2019 IEEE 1st Ukraine Conference
on Electrical and Computer Engineering, UKRCON 2019 - Proceedings. pp. 1061-1064,
Lviv (2019). https://doi.org/10.1109/UKRCON.2019.8879938
15. Yakovlev, S., Kartashov, O., Pichugina, O.: Optimization on Combinatorial Configura-
tions Using Genetic Algorithms. In: Proceedings of the Second International Workshop on
Computer Modeling and Intelligent Systems (CMIS-2019). pp. 28–40. CEUR Vol-2353
urn:nbn:de:0074-2353-0, Zaporizhzhia, Ukraine (2019).
16. Yakovlev, S., Pichugina, O.: On Constrained Optimization of Polynomials on Permutation
Set. In: Proceedings of the Second International Workshop on Computer Modeling and In-
telligent Systems (CMIS-2019). pp. 570–580. CEUR Vol-2353 urn:nbn:de:0074-2353-0,
Zaporizhzhia, Ukraine (2019).
17. Pichugina, O., Yakovlev, S.: Quadratic Optimization Models and Convex Extensions on
Permutation Matrix Set. In: Shakhovska, N. and Medykovskyy, M.O. (eds.) Advances in
Intelligent Systems and Computing IV. pp. 231–246. Springer International Publishing
(2020). https://doi.org/10.1007/978-3-030-33695-0_17.
18. Hwang, F.K., Rothblum, U.G., Chen, H.-B.: Partitions-optimality and clustering. Vol II.
Multi-parameter. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ (2013).
19. Pichugina, O., Yakovlev, S.: Euclidean Combinatorial Configurations: Typology and Ap-
plications. In: 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineer-
ing (UKRCON 2019) Conference Proceedings. pp. 1065–1070, Lviv (2019).
https://doi.org/ 10.1109/UKRCON.2019.8879912.
20. Pichugina, O., Yakovlev, S.: Euclidean Combinatorial Configurations: Continuous Repre-
sentations and Convex Extensions. In: Lytvynenko, V., Babichev, S., Wójcik, W., Vyno-
kurova, O., Vyshemyrskaya, S., and Radetskaya, S. (eds.) Lecture Notes in Computational
Intelligence and Decision Making. pp. 65–80. Cham : Springer, Zalizniy Port, Ukraine
(2019).
21. Stoyan, Y.G. Yemets, O.O. Theory and Methods of Euclidean Combinatorial Optimiza-
tion. ISSE, Kyiv (1993) (in Ukrainian)
22. Yakovlev, S.V.: The theory of convex continuations of functions on vertices of convex
polyhedra. Comp. Math. and Math. Phys. 34, 1112–1119 (1994). Stoyan, Y.G., 23. Ya-
kovlev, S.V., Parshin, O.V.: Quadratic optimization on combinatorial sets in Rn. Cybern.
Syst. Anal. 27, 561–567 (1991). https://doi.org/10.1007/BF01130367.
23. Pichugina, O., Yakovlev, S.: Continuous Approaches to the Unconstrained Binary Quad-
ratic Problems. In: Bélair, J., Frigaard, I., Kunze, H., Makarov, R., Melnik, R., and Spiteri,
R.J. (eds.) Mathematical and Computational Approaches in Advancing Modern Science
and Engineering. pp. 689–700. Springer International Publishing (2016).
https://doi.org/10.1007/978-3-319-30379-6_62.
24. Pichugina, O.: Placement problems in chip design: Modeling and optimization. In: 2017
4th International Scientific-Practical Conference Problems of Infocommunications. Sci-
ence and Technology (PIC& S T). pp. 465–473 (2017).
https://doi.org/10.1109/INFOCOMMST.2017.8246440.
25. Pichugina, O., Farzad, B.: A Human Communication Network Model. In: CEUR Work-
shop Proceedings. pp. 33–40, Kyiv (2016).
26. Koliechkina, L., Pichugina, O.: A Horizontal Method of Localizing Values of a Linear
Function in Permutation-Based Optimization. In: Le Thi, H.A., Le, H.M., and Pham Dinh,
T. (eds.) Optimization of Complex Systems: Theory, Models, Algorithms and Applica-
tions. pp. 355–364. Cham : Springer (2019). https://doi.org/10.1007/978-3-030-21803-
4_36.
27. Chase, P.: Transposition Graphs. SIAM J. Comput. 2, 128–133 (1973).
https://doi.org/10.1137/0202011.
28. Yakovlev, S.V., Valuiskaya, O.A.: Optimization of linear functions at the vertices of a
permutation polyhedron with additional linear constraints. Ukr. Math. J. 53, 1535–1545
(2001). https://doi.org/10.1023/A:1014374926840.
29. Ēmets′, O.O., Ēmets′, Ē.M.: Cut-off in linear partially combinatorial problems of Euclide-
an combinatorial optimization. Dopovīdī Natsīonal′ noï Akademīï Nauk Ukraïni. Matemat-
ika. Prirodoznavstvo. Tekhnīchnī Nauki. 105–109 (2000).
30. Yemets, O.A., Yemets, Y.M.: A modification of the method of combinatorial truncation in
optimization problems over vertex-located sets. Cybern. Syst. Anal. 45, 785–791 (2009).
https://doi.org/10.1007/s10559-009-9147-8.
31. Pichugina, O.S.: Surface and combinatorial cuttings in Euclidean combinatorial optimiza-
tion problems. Math. and Comp. Model., Ser. Phys. and Math. 1, pp. 144-160 (2016). (in
Russian)
32. Berstein, Y., Lee, J., Onn, S., Weismantel, R.: Parametric nonlinear discrete optimization
over well-described sets and matroid intersections. Math. Program. 124, 233–253 (2010).
https://doi.org/10.1007/s10107-010-0358-6.
33. Crama, Y., Hammer, P.L. eds: Boolean Models and Methods in Mathematics, Computer
Science, and Engineering. Cambridge University Press (2010).
34. Kirichenko, L., Radivilova, T., Bulakh, V.: Binary Classification of Fractal Time Series by
Machine Learning Methods. In: Lytvynenko, V., Babichev, S., Wójcik, W., Vynokurova,
O., Vyshemyrskaya, S., and Radetskaya, S. (eds.) Lecture Notes in Computational Intelli-
gence and Decision Making. pp. 701–711. Springer International Publishing (2020).
35. Hulianytskyi, L., Riasna, I.: Formalization and Classification of Combinatorial Optimiza-
tion Problems. In: Optimization Methods and Applications. pp. 239–250. Springer, Cham
(2017). https://doi.org/10.1007/978-3-319-68640-0_11.
36. Dolgui, A., Kotov, V., Nekrashevich, A., Quilliot, A.: General parametric scheme for the
online uniform machine scheduling problem with two different speeds. Information Pro-
cessing Letters. 134, 18–23 (2018). https://doi.org/10.1016/j.ipl.2018.01.009.
37. Grebennik, I.V., Kovalenko, A.A., Romanova, T.E., Urniaieva, I.A., Shekhovtsov, S.B.:
Combinatorial Configurations in Balance Layout Optimization Problems. Cybern Syst
Anal. 54, 221–231 (2018). https://doi.org/10.1007/s10559-018-0023-2.
38. Kozin, I.V., Maksyshko, N.K., Perepelitsa, V.A.: Fragmentary Structures in Discrete Op-
timization Problems. Cybern Syst Anal. 53, 931–936 (2017).
https://doi.org/10.1007/s10559-017-9995-6.
39. Stoyan, Y.G., Patsuk, V. N.: A method of optimal lattice packing of congruent oriented
polygons in the plane. European Journal of Operational Research. 204–216 (2000).
https://doi.org/10.1016/S0377-2217(99)00115-0.
40. Stetsyuk, P.I.: Shor’s r-Algorithms: Theory and Practice. In: Optimization Methods and
Applications. pp. 495–520. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-
68640-0_24.