A Spherical Cutting-plane Method With Applications In Multimedia Flow Management

Abstract

An important problem in Multimedia Flow Management of scheduling 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 permutationbased 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 partially combinatorial permutation-based problem is built, and the SCPM is generalized for solving partially combinatorial problems.

Keywords

• Scheduling
• parallel machines
• cutting plane method
• permutationbased problem
• Euclidean combinatorial problem
• spherical-located set
• well-described set

-

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, Combinatorial 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 dimension in a reasonable time [4-7]. Nevertheless, steadily increasing demands to the solutions’ 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 spherical cutting-plane method (SCPM), is offered for solving a scheduling problem for 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 generic 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 completion 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 M1, ..., M m ). No machine can handle more than one job at a time. Each job Ai is available for processing 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 jI i' iJ m , I i'  ni , i  J m be a partition of the jobs induced the schedule, where  A j  jI 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   ti , i  J m .

iJ m jI i'

It is required to determine such a partition, where T is minimized. Thus, an issue is to find the partition: where additional constraints

T  min ,

P  P , 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 referred 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 problem needs to be solved to get any of the feasible partitions [18]. ( 1 ) ( 2 ) ( 3 )

In this paper, we propose a technique for solving Problem 1, provided that an approximate solution yielding T  T ** has been found. The approach is based on embedding 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 nmin , nmax be a minimal and maximal number of the jobs scheduled on a single machine.

Without loss of generality, assume that t1  ...  tn , then n min , n max : nmin  tni1  T ** , nmin 1 t ni1  T ** ; i1 i1 nmax  ti  T ** , nmin 1 ti  T ** . i1 i1

Now, set the dimension of Euclidean space as follows – N  m  n max . After, we complement the multiset ti iJ n by N  n dummy zeros and form a multiset

G   gi iJ N  ti iJ n 0 N n  : g1  ...  g n , with exactly k different values S  G   ei iJ k : 0  e1  ...  ek .

Introduce a vector of variables

x   x11, ..., x1nmax , ..., xm1, ..., xmnmax  .

In these denotations, Problem 1 can be formulated as finding x  R N : nmax z  max  xij  min , iJ m j1

x  ENk G  , where ENk 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 becomes much easier for dealing with by its lifting into space R N 1 . For that, let us 1 N introduce an additional variable y  R0 such that y  max  xij . Now, ( 5 ) is reiJ m j1 written as – find  x, y  , z : z  y  min , ( 4 ) ( 5 ) ( 6 ) ( 7 ) subject to ( 6 ) and constraints

N  xij  y  0, i  J m .

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' .

The obtained problem ( 6 )-( 9 ), further referred to as Problem 2, is a linear constrained 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 problems:

f  x, x '   cx  c ' x '  min , 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 , x  E  R N , E   , where E  ENk G  , n'  1.

Numerous features of set ENk G  underlie various optimization methods of solving problems such as ( 10 )-( 12 ).

One of the properties is that ENk G  lies on a hyperplane and hyperspheres centered at a  ae , where a  R1 \  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   gi . It results in another peculiarity of crucial importance for us that

N i1 ENk G  coincides with a vertex set of a polytope PNk G   conv ENk G  . Such a set is called vertex-located (VLS) [22].

The class ENk G  is intensively studied the last couple of decades [4,1116,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 ( 8 ) ( 9 ) ( 10 ) ( 11 ) ( 12 ) 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 combinatorial 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 adjacent vertices to solutions of auxiliary polyhedral relaxation problems (the solutions’ neighborhood). It is caused by, generally, the exponential on N number of constraints 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 inconsiderable 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 permutation-based and partially permutation-based problems, which utilizes solutions of polyhedral relaxation problems, spherical locality of ENk G  , and properties of linear functions over the set. Our final goal is to adapt this method for solving Problem 2. 4

Cutting-plane method for linear optimization on WD-SpLSs

Consider an optimization problem of finding x such that subject to constraints

f  x   cx  min Ax  b, A R Mn , b  R M ,

x  E  S r  a   R n , E is a well-described set (WDS), ( 13 ) ( 14 ) ( 15 ) ( 16 ) ( 17 ) ( 18 ) ( 19 ) where Sr  a  – is a hypersphere centered at a  R n with a radius r  0 . The condition ( 16 ) means that the problem ( 13 ) is effectively solvable on , i.e., it is polynomially 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 problem (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 are equivalent.

Proof. Let us assume that SpLS E satisfies ( 15 ), wherefrom h  x   x  x 0 2  min

xE r 2  x  a 2  x 2  2ax  a 2 .

E Single outing x 2 from ( 18 ) and substituting it in ( 17 ) yield h  x    x  x 0  2  x 2  2xx 0   x 0  2  r 2  2ax  a 2  2xx 0   x 0  2   2  a  x 0  x   r 2  a 2   x 0 2  .

  The expression can be rewritten as follows:

h  x   cx  d , where c=2  a  x 0  , d =r 2  a 2   x 0  2 .

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 effectively 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 ), is solved (further Problem 3.l), which is equivalent to Problem 3, through its continuous relaxation. For that, the constraint ( 15 ) is replaced by ( 20 ) ( 21 ) ( 22 ) ( 23 ) Al x  bl , Al  R ml n , bl  R ml x  P  conv E  Sr  a  .

y l  PrE x l .

 r l  2   y l  x l  2 ,

By construction, y l  x l , thus there exists a sphere S l of a positive radius centered 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 r l  x l  , where because this sphere contains no points of E in an interior. So, a deep nonlinear cut of x l  E is

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

Step l. On iteration l , if x l  E, then form a cut for x l . For that, find a projection y l of the point x l onto E : 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   hl  x  , c  cl , d  d l , l  J L . 0

Corollary 2. If E is SpLS, then for any x l  R n , there exists c l  R n such that problems c l x  min and xE hl  x   x  x l 2  min are equivalent, namely,

xE hl  x   c l x  d l , where c l =2  a  x l  , d l =r 2  a 2   x l  2 .

Now, inequality ( 24 ) can be rewritten equivalently E  r l  2   x  x l  2   hl  x   c l x  d l or

E c l x  d l   r l  2 ,  x  x l  2   r l  2 , where r l is given by ( 23 ), cl , d l – by ( 25 ).

By construction, c l x l  d l   r l  2 , hence c l x  d l   r l  2 is a cutting plane for x l . Instead of ( 24 ), let us add inequality (26) to the current constraints ( 20 ) obtaining input data Al1, bl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** ), or incompatibility of Problem 4.l was proven.

Remark 1. Throughout the iterative process, a lower bound z lb on z* are constantly improved. Namely, by construction, z 0  z1  ...  z L that is why: a) initially z lb  z 0 ; b) on iteration 1, z lb  max  z1, z lb   z1 ; …; 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 ( 24 ) ( 25 )

on (26) bound is improved on iteration l , if the point ( 22 ) satisfies ( 14 ), and z ub  z  y l   cy l , wherefrom z ub  min z  y l  , z lb   z  y l  .

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 replacing formula ( 22 ) by Y l  PrE xl .

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

Al  x, y   bl , Al  R ml  N n'  , bl  R ml , (27) z.  cx.  c ' x'. , where A0   A, A '  , .l ,*,** .

Step l is reformulated as follows: on iteration l , if xl  E, then  x* , y*  , z*

  xl , y l  , z l , end. If x l  E , then find y l by ( 22 ) 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, xl  y . Matrix A0 is of the dimension 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 reduced depending on the type of values of elements in ( 4 ). Without loss of generality assume that a greatest common divisor GCD ti iJ n   1, then an initial lower  1 n  bownd will be z lb    ti  . 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 packing. An actual problem of organizing effective parallelization of a job batch is considered. This problem is modeled as linear constrained partially combinatorial. For linear constrained problems over well-described spherically-located sets, such as permutation set, Boolean set, or permutation matrices’ set, a special exact solution method is offered, 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 problems 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 combinatorial and partially combinatorial problems [36-40], where, in order to solve optimization problems globally, our method should be combined with the convex extension theory [16,17,20,23] and continuous functional representation theory [17,20,22]. 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 Applications. pp. 355–364. Cham : Springer (2019). https://doi.org/10.1007/978-3-030-218034_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 Euclidean combinatorial optimization. Dopovīdī Natsīonal′ noï Akademīï Nauk Ukraïni. Matematika. 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 optimization 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 Intelligence and Decision Making. pp. 701–711. Springer International Publishing (2020). 35. Hulianytskyi, L., Riasna, I.: Formalization and Classification of Combinatorial Optimization 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 Processing 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 Optimization 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-31968640-0_24.

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 multicast 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 - Application 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 Configurations 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 Intelligent 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 Applications . In: 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineering (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 Representations and Convex Extensions . In: Lytvynenko, V. , Babichev , S. , Wójcik , W. , Vynokurova , 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 Optimization . 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 . Yakovlev , 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 Quadratic 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. Science 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 Workshop Proceedings . pp. 33 - 40 , Kyiv ( 2016 ).