On the Solution of Linear Programming
Problems in the Age of Big Data

arXiv:1706.10030v2 [] 3 Jul 2017

Irina Sokolinskaya and Leonid B. Sokolinsky

⋆

South Ural State University
76 Lenin prospekt, Chelyabinsk, Russia, 454080
Irina.Sokolinskaya@susu.ru, Leonid.Sokolinsky@susu.ru

Abstract. The Big Data phenomenon has spawned large-scale linear
programming problems. In many cases, these problems are non-stationary. In this paper, we describe a new scalable algorithm called NSLP
for solving high-dimensional, non-stationary linear programming problems on modern cluster computing systems. The algorithm consists of
two phases: Quest and Targeting. The Quest phase calculates a solution
of the system of inequalities defining the constraint system of the linear programming problem under the condition of dynamic changes in
input data. To this end, the apparatus of Fejer mappings is used. The
Targeting phase forms a special system of points having the shape of an
n-dimensional axisymmetric cross. The cross moves in the n-dimensional
space in such a way that the solution of the linear programming problem
is located all the time in an ε-vicinity of the central point of the cross.
Keywords: NSLP algorithm · non-stationary linear programming problem · large-scale linear programming · Fejer mapping.

1

Introduction

The Big Data phenomenon has spawned large-scale linear programming (LP)
problems [1]. Such problems arise in many different fields. In [2], the following
large-scale industrial optimization problems are presented within the context of
big data:
– schedule crews for 3400 daily flights in 40 countries;
– buy ads in 10–15 local publications across 40 000 zip codes;
– pick one of 742 trillion choices in creating the US National Football League
schedule;
– select 5 offers out of 1000 for each of 25 000 000 customers of an online store;
– place 1000 stock keeping units on dozens of shelves in 2000 stores;
⋆

The reported study has been partially supported by the RFBR according to research
project No. 17-07-00352-a, by the Government of the Russian Federation according
to Act 211 (contract No. 02.A03.21.0011.) and by the Ministry of Education and
Science of the Russian Federation (government order 1.9624.2017/7.8).

2

Irina Sokolinskaya et al.

– decide among 200 000 000 maintenance routing options.
Each of these problems uses Big Data from the subject field. Such a problem is
formalized as a linear programming problem involving up to tens of millions of
constraints and up to hundreds of millions of decision variables.
Gondzio [3] presents a certain class of large-scale optimization problems arising in quantum information science and related to Bell’s theorem. These problems are two-level optimization problems. The higher-level problem is a non-convex non-linear optimization task. It requires solving hundreds of linear programming problems, each of which can contain millions of constraints and millions of
variables.
Mathematical modeling in economics is another source of large-scale LP
problems. In many cases, LP problems arising in mathematical economy are
non-stationary (dynamic). For example, Sodhi [4] describes a dynamic LP task
for asset-liability management. This task involves 1.7 billion constraints and 5.1
billion variables. Algorithmic trading is another area that generates large-scale
non-stationary linear programming problems [5,6,7]. In such problems, the number of variables and inequalities in the constraint system formed by using Big
Data can reach tens and even hundreds of thousands, and the period of input
data change is within the range of hundredths of a second.
Until now, one of the most popular methods for solving LP problems is the
class of algorithms proposed and designed by Dantzig on the basis of the simplex
method [8]. The simplex method has proved to be effective in solving a large class
of LP problems. However, Klee and Minty [9] gave an example showing that the
worst-case complexity of the simplex method is exponential time. Nevertheless,
Khaciyan [10] proved that the LP problem can be solved in polynomial time by
a variant of an iterative ellipsoidal algorithm developed by Shor [11]. Attempts
to apply the ellipsoidal algorithm in practice have been unsuccessful so far. In
most cases, this algorithm demonstrated much worse efficiency than the simplex
method did. Karmarkar [12] proposed the interior-point method, which runs in
polynomial time and is also very efficient in practice.
The simplex method and the interior-point method remain today the main
methods for solving the LP problem. However, these methods may prove ineffective in the case of large-scale LP problems with rapidly changing and (or)
incomplete input data. The authors described in [13] a parallel algorithm for
solving LP problems with non-formalized constraints. The main idea of the proposed approach is to combine linear programming and discriminant analysis
methods. Discriminant analysis requires two sets of patterns M and N . The
first set must satisfy the non-formalized constraints, while the second must not.
To obtain representative patterns, methods of data mining [14] and time series
analysis can be used [15]. To overcome the problem of non-stationary input data,
the authors proposed in [16,17] the pursuit algorithm for solving non-stationary
LP problems on cluster computing systems. The pursuit algorithm uses Fejer
mappings (see [18]) to build a pseudo-projection onto a convex bounded set.
The pseudo-projection operator is similar to a projection, but in contrast to the
last, it is stable to dynamic changes in input data. In [19], the authors inves-

Linear Programming in the Age of Big Data

3

tigated the efficiency of using Intel Xeon Phi multi-core processors to calculate
the pseudo-projections.
In this paper, we describe the new NSLP (Non-Stationary Linear Programming) algorithm for solving large-scale non-stationary LP problems on cluster
computing systems. The NSLP algorithm is more efficient than the pursuit algorithm, since it uses a compute-intensive pseudo-projection operation only once
(the pursuit algorithm computes pseudo-projections K times at each iteration,
K being the number of processor nodes). The rest of the paper is organized as
follows. Section 2 gives a formal statement of an LP problem and presents the
definitions of the Fejer process and the pseudo-projection onto a polytope. Section 3 describes the new NSLP algorithm. Section 4 summarizes the obtained
results and proposes directions for future research.

2

Problem statement

Let a non-stationary LP problem be given in the vector space Rn :
max {hct , xi |At x ≤ bt , x ≥ 0} ,

(1)

where the matrix At has m rows. The non-stationarity of the problem means
that the values of the elements of the matrix At and the vectors bt , ct depend
on time t ∈ R≥0 . We assume that the value of t = 0 corresponds to the initial
time:
A0 = A, b0 = b, c0 = c.
(2)
Let us define the map ϕt : Rn → Rn as follows:
m

ϕt (x) = x −

λ X max {hati , xi − bti , 0}
· ati ,
m i=1
kati k2

(3)

where ati is the i-th row of the matrix At , and bt1 , . . . , btm are the elements of
the column bt . Let us denote
m

ϕ (x) = ϕ0 (x) = x −

λ X max {hai , xi − bi , 0}
· ai .
2
m i=1
kai k

(4)

Let Mt be the polytope defined by the constraints of the non-stationary LP
problem (1). Such a polytope is always convex. It is known (see [18]) that ϕt is
a continuous single-valued Mt -fejerian1 map for the relaxation factor 0 < λ < 2.
1

A single-valued map ϕ : Rn → Rn is said to be fejerian relatively to a set M (or
briefly, M -fejerian) if
ϕ (y) = y, ∀y ∈ M ;
kϕ(x) − yk < kx − yk , ∀x ∈
/ M, ∀y ∈ M.

4

Irina Sokolinskaya et al.

By definition, put
ϕst (x) = ϕt . . . ϕt (x) .
{z
}
|

(5)

s

The Fejer process generated by the map ϕt for an arbitrary initial approx+∞
imation x0 ∈ Rn is the sequence {ϕst (x0 )}s=0 . It is known (see Lemma 39.1
in [20]) that the Fejer process for a fixed t converges to a point belonging to the
polytope Mt :
+∞
{ϕst (x0 )}s=0 → x̄ ∈ Mt .
(6)
Let us consider the simplest non-stationary case, which is a translation of
the polytope M = M0 by the fixed vector d ∈ Rn in one unit of time. In this
case, At = A, ct = c, and the non-stationary problem (1) takes the form
max {hc, xi |A(x − td) ≤ b, x ≥ 0} ,

(7)

which is equivalent to
max {hc, xi |Ax ≤ b + Atd, x ≥ 0} .
Comparing this with (1), we obtain bt = b + Atd. In this case, the Mt -fejerian
map (3) is converted to the following:
m

ϕt (x) = x −

λ X max {hai , xi − (bi + hai , tdi) , 0}
· ai ,
2
m i=1
kai k

which is equivalent to
m

ϕt (x) = x −

λ X max {hai , x − tdi − bi , 0}
· ai
2
m i=1
kai k

(8)

The ϕ-projection (pseudo-projection) of the point x ∈ Rn on the polytope M
ϕ
is the map πM
(x) = lims→∞ ϕs (x).

3

The NSLP algorithm

The NSLP (Non-Stationary Linear Programming) algorithm is designed to solve
large-scale non-stationary LP problems on cluster computing systems. It consists
of two phases: Quest and Targeting. The Quest phase calculates a solution of the
system of inequalities defining the constraint system of the linear programming
problem under the condition of dynamic changes in input data. To this end,
the apparatus of Fejer mappings is used. The Targeting phase forms a special
system of points having the shape of an n-dimensional axisymmetric cross. The
cross moves in the n-dimensional space in such a way that the solution of the LP
problem remains permanently in an ε-vicinity of the central point of the cross.
Let us describe both phases of the algorithm in more detail.

Linear Programming in the Age of Big Data

3.1

5

The Quest phase

Without loss of generality, we can assume that all the calculations are performed
in the region of positive coordinates. At the beginning, we choose an arbitrary
point z0 ∈ Rn≥0 with non-negative coordinates. This point plays the role of initial
approximation for the problem (1). Then we organize an iterative Fejer process
of the form (6). During this process, the Fejer approximations are consecutively
calculated by using the Fejer mapping (3). This process converges to a point
located on the polytope Mt . Owing to the non-stationary nature of the problem (1), the polytope Mt can change its position and shape during the calculation
of the pseudo-projection. An input data update is performed every L iterations,
L being some fixed positive integer that is a parameter of the algorithm. Let us
denote by t0 , t1 , . . . , tk , . . . sequential time points corresponding to the instants
of input data update. Without loss of generality, we can assume that
t0 = 0, t1 = L, t2 = 2L, . . . , tk = kL, . . . .

(9)

This corresponds to the case when one unit of time is equal to the time spent
by the computer to calculate one value of the Fejer mapping using equation (3).
Let the polytope Mt take shapes and locations
M0 , M1 , . . . , Mk , . . .
at time points (9). Let
ϕ0 , ϕ1 , . . . , ϕk , . . .
be the Fejer mappings determined by equation (3) taking into account the
changes in input data of problem (1) at time points (9). In the Quest phase,
the iterative process calculates the following sequence of points (see Fig. 1):
L
L
{z1 = ϕL
0 (z0 ), z2 = ϕ1 (z1 ), . . . , zk = ϕk−1 (zk−1 ), . . .}.

Let us briefly denote this iterative process as
 L
+∞
ϕk (z0 ) k=0 .
It terminates when2

(10)


dist ϕL
k (zk−1 ), Mk < ε,

where ε > 0 is a positive real number being a parameter of the algorithm. One
of the most important issues is the convergence of the iterative process (10). In
the general case, this issue remains open. However, the following theorem holds
for the non-stationary problem (7).
Theorem 1. Let a non-stationary LP problem be given by (7). Let the Fejer
mappings ϕ0 , ϕ1 , . . . , ϕk , . . . be defined by the equation
m

ϕk (x) = x −
2

λ X max {hai , x − kLdi − bi , 0}
· ai .
2
m i=1
kai k

Here dist(z, M ) = inf {kz − xk : x ∈ M }.

(11)

6

Irina Sokolinskaya et al.

Fig. 1. The iterative process in the Quest phase for problem (7)

This equation is derived using (8) and (9). By definition, put
zk = ϕL
k−1 (zk−1 )

(12)

lim dist(zk , Mk ) = 0

(13)

where k = 1, 2, . . .. Then
k→∞

under the following condition:

∀x ∈ Rn \M kLdk < dist(x, M ) − dist(ϕL (x), M ) .

(14)

The Theorem 1 gives a sufficient condition for the convergence of the iterative process shown in Fig. 1. To prove this theorem, we will need the following
auxiliary lemma.
Lemma 1. Under the conditions of Theorem 1, we have
v − u = pLd ⇒ ϕlp (v) − ϕl (u) = pLd

(15)

for any p = 0, 1, 2, . . ., l = 1, 2, 3, . . . and u, v ∈ Rn .
Proof. The proof is by induction on l.
Induction base. Let l = 1, then the following condition holds:
v − u = pLd.

(16)

Linear Programming in the Age of Big Data

7

Fig. 2. Illustration to the proof of Lemma 1

Then using (16), (11) and (4), we get
ϕp (v) − ϕ(u) = ϕp (u + pLd) − ϕ(u) =
m
λ X max {hai , ui − bi , 0}
· ai − ϕ(u) =
= u + pLd −
2
m i=1
kai k
m

= u + pLd −

λ X max {hai , ui − bi , 0}
· ai −
2
m i=1
kai k
m

−u+

λ X max {hai , ui − bi , 0}
· ai = pLd.
2
m i=1
kai k

Thus, (15) holds if l = 1 (see Fig. 2).
Inductive step. Assume that condition (16) is true. Using the induction hypothesis, we get
ϕpl−1 (v) − ϕl−1 (u) = pLd.
(17)
Then, combining (5), (17), (11) and (4), we obtain
ϕlp (v) − ϕl (u) = ϕp (ϕpl−1 (v)) − ϕ(ϕl−1 (u)) =
= ϕp (ϕl−1 (u) + pLd) − ϕ(ϕl−1 (u)) =

m
λ X max ai , ϕl−1 (u) − bi , 0
l−1
= ϕ (u) + pLd −
· ai − ϕ(ϕl−1 (u)) =
2
m i=1
kai k

m
λ X max ai , ϕl−1 (u) − bi , 0
= ϕl−1 (u) + pLd −
· ai −
m i=1
kai k2

m
λ X max ai , ϕl−1 (u) − bi , 0
l−1
− ϕ (u) +
· ai = pLd.
2
m i=1
kai k
This completes the proof of Lemma 1.

8

Irina Sokolinskaya et al.

Fig. 3. The process defined by (18)

Proof (of Theorem 1). Let us fix an arbitrary point z0 ∈ Rn \M . Let the map
ψ : Rn → Rn be given by
ψ (x) = ϕL (x) − Ld, ∀x ∈
/ M;
ψ (x) = x, ∀x ∈ M.

(18)

By definition, put
y0 = z0

(19)

yk = ψ(yk−1 )

(20)

and
for k = 1, 2, . . . (see Fig. 3).
Now let us show by induction on k that
zk − yk = kLd

(21)

for k = 0, 1, 2, . . . (see Fig. 4).
Induction base. Equation (21) holds for k = 0. Taking into account (19), we
see that the equation
z0 − y0 = 0 · Ld
holds.
Inductive step. Suppose that
zk−1 − yk−1 = (k − 1)Ld

(22)

for k > 0. Substituting u = yk−1 , v = zk−1 , l = L, p = k − 1 in Lemma 1, and
using (15), we obtain
L
zk−1 − yk−1 = (k − 1)Ld ⇒ ϕL
k−1 (zk−1 ) − ϕ (yk−1 ) = (k − 1)Ld.

Linear Programming in the Age of Big Data

9

Fig. 4. Illustration to equation (21)

Comparing this with (22), we have
L
ϕL
k−1 (zk−1 ) − ϕ (yk−1 ) = (k − 1)Ld.

(23)

Combining (20), (18), (12) and (23), we get
zk − yk = zk − ψ(yk−1 ) = zk − ϕL (yk−1 ) + Ld =
L
= ϕL
k−1 (zk−1 ) − ϕ (yk−1 ) + Ld = (k − 1)Ld + Ld = kLd.

Thus, equation (21) holds.
Now we show that
dist(zk , Mk ) = dist(yk , M )

(24)

for all k = 0, 1, 2, . . .. Let us choose a point ŷ ∈ M that satisfies the following
condition:
kŷ − yk k = dist(yk , M ).
(25)
Such a point exists and is unique since the polytope M is a bounded, closed
and convex set. The polytope Mk is the result of translating the polytope M by
the vector kLd (see Fig. 5). Since ŷ ∈ M , it follows that the point ẑ = ŷ + kLd
belongs to the polytope Mk . Taking into account (21), we conclude that the
points {yk , zk , ẑ, ŷ} are the vertices of a parallelogram. Therefore,
kẑ − zk k = kŷ − yk k .

(26)

kẑ − zk k = dist(zk , Mk ).

(27)

Let us show that

10

Irina Sokolinskaya et al.

Fig. 5. Illustration to equation (24)

Assume for a contradiction that ∃z ′ ∈ Mk such that
kz ′ − zk k < kẑ − zk k .

(28)

Since z ′ ∈ Mk , it follows that the point y ′ = z ′ − kLd belongs to the polytope M .
Now, if we recall that the points {yk , zk , ẑ, ŷ} are the vertices of a parallelogram,
we get
ky ′ − yk k = kz ′ − zk k .
Combining this with (28), (26) and (25), we obtain
ky ′ − yk k = kz ′ − zk k < kẑ − zk k = kŷ − yk k = dist(yk , M ).
It follows that
∃y ′ ∈ M (ky ′ − yk k < dist(yk , M )) .
This contradicts the definition of the distance between a point and a set. Therefore, equation (27) holds. Combining (25), (26) and (27), we get that equation (24) also holds.
Further, the map ψ defined by equation (18) is single-valued and continuous
(this follows from the fact that ϕ is a single-valued and continuous map). Let
us show that the map ψ is M -fejerian. Let x ∈ Rn \M be an arbitrary point not
belonging to the polytope M . Let us choose a point x̂ ∈ M that satisfies the
following condition
ϕL (x) − x̂ = dist(ϕL (x), M ).
(29)
Such a point exists and is unique because the polytope M is a bounded, closed
and convex set. Combining the dist definition, equation (18), the triangle inequality for the norm and equations (29) and (14), we get
dist(ψ(x), M ) ≤ kψ(x) − x̂k = ϕL (x) − Ld − x̂ ≤
≤ kLdk + ϕL (x) − x̂ = kLdk + dist(ϕL (x), M ) < dist(x, M ).

Linear Programming in the Age of Big Data

11

It follows that ψ is M -fejerian. Therefore,
 k
ψ (y0 )

+∞
k=0

→ ȳ ∈ M.

This means that lim dist(yk , M ) = 0. Taking into account (24), we conclude
k→∞

that lim dist(zk , Mk ) = 0. This completes the proof of the theorem.
k→∞

From a non-formal point of view, Theorem 1 states that the Fejer process
must converge faster than the polytope M “runs away”. Manycore processors
can be used to increase the Fejer mapping calculation speed. In [19], the authors
investigated this issue on Intel Xeon Phi multi-core coprocessors with MIC architecture [21]. It was shown that the Intel Xeon Phi may be used efficiently for
solving large-scale problems.
3.2

The Targeting phase

The Targeting phase begins after the Quest phase. At the Targeting phase, an
n-dimensional axisymmetric cross is formed. An n-dimensional axisymmetric
cross is a finite set G = {g0 , . . . , gP } ⊂ Rn . The cardinality of G equals P + 1,
where P is a multiple of n ≥ 2. The point g0 is singled out from the point set G.
This point is called the central point of the cross. Initially, the central point is
assigned the coordinates of the point zk calculated in the Quest phase by using
the iterative process (10).
The set G\{g0 } is divided into n disjoint subsets Ci (i = 0, . . . , n − 1) called
the cohorts:
n−1
[
Ci ,
G\{g0 } =
i=0

where n is the dimension of the space. Each cohort Ci consists of
K=

P
n

(30)

points lying on the straight line that is parallel to the i-th coordinate axis and
passes through the central point g0 . By itself, the central point does not belong
to any cohort. The distance between any two neighbor points of the set Ci ∪ {g0 }
is equal to a constant s. An example of a two-dimensional cross is shown in Fig. 6.
The number of points in one dimension, excluding the central point, is equal to
K. The symmetry of the cross supposes that K takes only even values greater
than or equal to 2. Using equation (30), we obtain the following equation for the
total number of points contained in the cross:
P + 1 = nK + 1.

(31)

Since K can take only even values greater than or equal to 2 and n ≥ 2, it follows
from equation (31) that P can also take only even values, and P ≥ 4. In Fig. 6,
we have n = 2, K = 6, P = 12.

12

Irina Sokolinskaya et al.

Each point of the cross G is uniquely identified by a marker being a pair of
integer numbers (χ, η) such that 0 ≤ χ < n, |η| ≤ K/2. Informally, χ specifies
the number of the cohort, and η specifies the sequential number of the point
in the cohort Cχ counted from the central point. The corresponding marking of
points in the two-dimensional case is given in Fig. 6 (a). The coordinates of the
point x(χ,η) having the marker (χ, η) can be reconstructed as follows:
x(χ,η) = g0 + (0, . . . , 0, η · s , 0, . . . , 0).
|{z}

(32)

χ

The vector being added to g0 in the right part of equation (32) has a single
non-zero coordinate in position χ. This coordinate equals η · s, where s is the
distance between neighbor points in a cohort.
The Targeting phase includes the following steps.
1. Build the n-dimensional axisymmetric cross G that has K points in each
cohort, the distance between neighbor points equaling s, and the center at
point g0 = zk , where zk is obtained in the Quest phase.
2. Calculate G′ = G ∩ Mk .
3. Calculate Cχ′ = Cχ ∩ G′ for χ = 0, . . . , n − 1.
n−1
S
4. Calculate Q =
{arg max {hck , gi | g ∈ C ′ χ , C ′ χ 6= ∅}}.
χ=0

5. If g0 ∈ Mk and hck , g0 i ≥ max hck , qi, then k := k + 1, and go to step 2.
P

q∈Q

q

q∈Q

6. g0 := |Q| .
7. k := k + 1.
8. Go to step 2.

a) with markers (χ, η)

b) sequential numbering

Fig. 6. A two-dimensional cross

Thus, in the Targeting phase, the steps 2–7 form a perpetual loop in which
the approximate solution of the non-stationary LP problem is permanently recalculated. From a non-formal point of view, in Step 2, we determine which points

Linear Programming in the Age of Big Data

13

of the cross G belong to the polytope Mk . To do this, we check the condition
Ak g ≤ bk for each point g ∈ G. Such checks can be executed in parallel by different processor nodes of a cluster computing system. For this goal to be achieved,
P MPI-processes can be exploited, where P is defined by equation (31). We use
sequential numbering for distributing the cross points among the MPI-processes.
Each point of the cross is assigned a unique number α ∈ {0, . . . , P − 1}. The sequential number α can be converted to a marker (χ, η) by means of the following
equations3 :
χ = ||α − K| − 1| ÷ (K/2);
η = sgn (α − K) · (((|α − K| − 1) mod (K/2)) + 1) .
The backward conversion can be performed by means of the equation
χ
α = η + sgn(η) K + K.
2
Fig. 6 (b) demonstrates the sequential numbering of points that corresponds to
the marking in Fig. 6 (a).

4

Conclusion

In this paper, a new NSLP algorithm for solving non-stationary linear programming problems of large dimension has been described. This algorithm is oriented
to cluster computing systems with manycore processors. The algorithm consists
of two phases: Quest and Targeting. The Quest phase calculates a solution of the
system of inequalities defining the constraint system of the linear programming
problem under the condition of input data dynamic changes. To do this, we organize a Fejer process that computes a pseudo-projection onto the polytope M
defined by the constraints of the LP problem. In this case, input data changes
occur during calculation of the pseudo-projection. A convergence theorem for the
described iterative process is proved in the case of translation of the polytope
M . The Targeting phase forms a special system of points having the shape of an
n-dimensional axisymmetric cross. The cross moves in the n-dimensional space
in such a way that the solution of the linear programming problem is located all
the time in an ε-vicinity of the central point of the cross. A formal description of
the Targeting phase is presented in the form of a sequence of steps. Our future
goal is a parallel implementation of the NSLP algorithm in the C++ language
using the MPI library, as well as the development of computational experiments
on a cluster computing system using synthetic and real LP problems.

References
1. Chung, W.: Applying large-scale linear programming in business analytics. In:
Proceedings of the 2015 IEEE International Conference on Industrial Engineering
and Engineering Management (IEEM), pp. 1860-1864. IEEE (2015)
3

The symbol ÷ denotes integer division.

14

Irina Sokolinskaya et al.

2. Tipi,
H.:
Solving
super-size
problems
with
optimization.
Presentation
at
the
meeting
of
the
2010
INFORMS
Conference
on
O.R.
Practice.
Orlando,
Florida.
April
2010.
http://nymetro.chapter.informs.org/prac cor pubs/06-10%20Horia%20Tipi%20SolvingLargeScaleXpress.pdf
(accessed 07.05.2017).
3. Gondzio, J. et al.: Solving large-scale optimization problems related to Bells Theorem. Journal of Computational and Applied Mathematics, vol. 263, pp. 392-404.
(2014)
4. Sodhi, M.S.: LP modeling for asset-liability management: A survey of choices and
simplifications. Operations Research, vol. 53, no. 2, pp. 181-196. (2005)
5. Dyshaev, M.M., Sokolinskaya, I.M.: Predstavlenie torgovykh signalov na osnove
adaptivnoy skol’zyashchey sredney Kaufmana v vide sistemy lineynykh neravenstv
[Representation of trading signals based Kaufman adaptive moving average as a
system of linear inequalities]. Vestnik Yuzhno-Ural’skogo gosudarstvennogo universiteta. Seriya: Vychislitel’naya matematika i informatika [Bulletin of South Ural
State University. Series: Computational Mathematics and Software Engineering],
vol. 2, no. 4, pp. 103-108. (2013)
6. Ananchenko, I.V., Musaev, A.A.: Torgovye roboty i upravlenie v khaoticheskikh
sredakh: obzor i kriticheskiy analiz [Trading robots and management in chaotic
environments: an overview and critical analysis]. Trudy SPIIRAN [SPIIRAS Proceedings], no. 3(34), pp. 178-203. (2014)
7. Radenkov, S.P., Gavryushin, S.S., Sokolyanskiy, V.V.: Avtomatizirovannyye torgovyye sistemy i ikh installyatsiya v rynochnuyu sredu (chast’ 1) [Automated trading systems and their installation in the market environment (Part 1)]. Voprosy
ekonomicheskikh nauk [Problems of Economics], no. 6 (76), pp. 70-74. (2015)
8. Dantzig, G.: Linear programming and extensions. 656 pp. Princeton, N.J., Princeton university press. (1998)
9. Klee, V., Minty, G.J.: How good is the simplex algorithm? In: Proceedings of the
Third Symposium on Inequalities (University of California, Los Angeles, Calif.,
September 1–9, 1969, dedicated to the memory of Theodore S. Motzkin), pp. 159–
175. New York-London, Academic Press. (1972)
10. Khachiyan, L.: G. Polynomial algorithms in linear programming. USSR Computational Mathematics and Mathematical Physics, vol. 20, no. 1, pp. 53-72. (1980)
11. Shor, N.Z.: Cut-off method with space extension in convex programming problems.
Cybernetics and Systems Analysis, vol. 13, 1, pp. 94–96. (1977)
12. Karmarkar, N.: A new polynomial-time algorithm for linear programming. In:
Proceedings of the sixteenth annual ACM symposium on Theory of computing,
pp. 302-311. ACM. (1984)
13. Sokolinskaya, I.M., Sokolinskii, L.B.: Parallel algorithm for solving linear programming problem under conditions of incomplete data. Automation and Remote Control, vol. 71, no. 7, pp. 1452-1460. (2010)
14. Rechkalov, T.V., Zymbler, M.L.: Accelerating medoids-based clustering with the
Intel many integrated core architecture. In: Proceedings of the 9th International
Conference on Application of Information and Communication Technologies (October 14–16, 2015, Rostov-on-Don, Russia), pp. 413–417. IEEE. (2015)
15. Zymbler, M.L.: Best-match time series subsequence search on the Intel many integrated core architecture. In: Proceedings of the 19th East-European Conference on
Advances in Databases and Information Systems, ADBIS 2015 (Poitiers, France,
September 8–11, 2015). Lecture Notes in Computer Science, vol. 9282, pp. 275–286.
Springer. (2015)

Linear Programming in the Age of Big Data

15

16. Sokolinskaya, I.M., Sokolinsky, L.B.: Implementation of parallel pursuit algorithm
for solving unstable linear programming problems. Bulletin of the South Ural State
University. Series: Computational Mathematics and Software Engineering, vol. 5,
no. 2, pp. 15–29. (in Russian) (2016). DOI: 10.14529/cmse160202
17. Sokolinskaya, I., Sokolinsky, L.: Solving unstable linear programming problems of
high dimension on cluster computing systems. In: Proceedings of the 1st Russian Conference on Supercomputing - Supercomputing Days 2015 (Moscow, Russian Federation, September 28-29, 2015). CEUR Workshop Proceedings, vol. 1482,
pp. 420-427. CEUR-WS.org. (2015)
18. Eremin, I.I.: Fejerovskie metody dlya zadach linejnoj i vypukloj optimizatsii [Fejer
Methods for Problems of Convex and Linear Optimization]. 200 pp. Chelyabinsk,
Publishing of the South Ural State University. (2009)
19. Sokolinskaya, I., Sokolinsky, L.B.: Revised Pursuit Algorithm for Solving NonStationary Linear Programming Problems on Modern Computing Clusters with
Manycore Accelerators. In: Proceedings of the RuSCDays 2016. Communications in Computer and Information Science, vol. 687, pp. 212-223. (2016).
DOI: 10.1007/978-3-319-55669-7 17
20. Eremin, I.I.: Teoriya lineynoy optimizatsii [The theory of linear optimization].
312 pp. Ekaterinburg, Publishing House of the ”Yekaterinburg”. (1999)
21. Thiagarajan, S.U., Congdon C., Naik S., Nguyen L.Q.: Intel Xeon Phi
coprocessor developers quick start guide. White Paper. Intel. (2013).
https://software.intel.com/sites/default/files/managed/ee/4e/intel-xeon-phi-coprocessor-quick-start-developers-gu
(accessed 07.05.2017).

