Int. J. Anal. Appl. (2023), 21:72

The Security Assignment Problem and Its Solution

Paul Ryan A. Longhas∗, Alsafat M. Abdul, Edcon B. Baccay

Department of Mathematics and Statistics, College of Science, Polytechnic University of the

Philippines, Manila, 1008, Philippines

∗Corresponding author: pralonghas@pup.edu.ph

Abstract. In this paper we derived a new method for finding the optimal solution to security assignment

problems using projection onto a convex set. This study will help communities find the optimal number

of assigned and reserved personnels in designating security officers to an area. This study is applicable

as well to CCTV assignment problems. The main goal of this study is to give a new method that

can be applied in solving security assignment problems. We used some of the known properties of the

convex optimization in proving the properties of the optimal solution, such as the concept of proximity

operator, projection onto the convex set, and primal and dual problem. In addition to that, we used

some basic knowledge in graph theory to answer our real-life application of this study. The main

results of this paper showed that we found instances when the optimal solution to a security problem

exists and when the solutions exist, we can determine the answer to the problem explicitly. Also, we

proved that there always exists a Pseudo-solution in security assignment problems, and if the solution

exists, then the Pseudo-solution will coincide with it. The most important aspect of this paper is the

introduction of the application of convex optimization in the security problem.

1. Introduction

There are many optimizations problem in optimization theory such as assignment problems, linear

optimization problems, and convex optimization problems that are applicable in a real-life situation.

For instance, linear programming is applicable in assignment problems [1–3] diet problems [4–6], and

business problems in minimization of cost [7].

Received: May 9, 2023.

2020 Mathematics Subject Classification. 46N10, 47N10, 46C99.
Key words and phrases. security problem; assignment problem; convex optimization; proximity operator; projection

onto set.

https://doi.org/10.28924/2291-8639-21-2023-72
ISSN: 2291-8639

© 2023 the author(s).

https://doi.org/10.28924/2291-8639-21-2023-72


2 Int. J. Anal. Appl. (2023), 21:72

The assignment problem is a problem so that there are n workers and m jobs where m ≤ n. Any
worker can be assigned to perform any job, with some costs that may vary depending on the workers-

job assignment. It is required to perform a job by assigning at most one worker to each job and at

most one job to each worker, in such a way that the total cost of the assignment is minimized. The

assignment problem is a special type of {0,1}-linear programming [8,9].
In this paper, we will propose a model and solution to security assignment problems, CCTV assign-

ment problems, and any related problem.

In the security assignment problem, if we let G be the map of the city, E be the major road, V be

the intersection of the major road, w(e) be the criminal rate of the certain major road e ∈ E and π(e)
be the time needed to travel the road e, then the goal is to assign a percentage of security personnel

τ(e) ∈ [a,b] ⊆ [0,1] in any major road e ∈ E such that the crime will minimize. Furthermore, we
want to maximize the reserved personnel that we will assigned to the strategic location of the city.

The crime will minimize in the road e ∈ E if the crime rate w(e) and the percentage of assigned
personnel τ(e) to that road has small distance. Thus, the goal is to find τ : E → [a,b] such that the
crime in G will minimize, that is, τ satisfy the following equation

min
γ:E→[a,b]

∑
e∈E
(w(e)−γ(e))2 =

∑
e∈E
(w(e)−τ(e))2. (1.1)

In addition, we want to have a reserved personnel that we will assign to the center of Gπ =(V,E,π)

so that the total percentage of reserved personnel is maximized, and it is at least 1− s but not more
than 1− r where r,s ∈ [0,1] and r < s. The quantity r and s are the lower bound and upper bound
for the percentage of assigned personnel, respectively. For instance, if we want to avoid the case that

the total percentage of reserved is at least 20% and it is at most the total percentage of assigned,

then we set r =0.5 and s =0.8. This assumption can be formulated as

0≤ r ≤
∑
e∈E

τ(e)≤ s ≤ 1 (1.2)

and

max
γ:E→[a,b]

(
1−

∑
e∈E

γ(e)

)
=1−

∑
e∈E

τ(e) (1.3)

where
∑
e∈E τ(e) is the percentage of assigned personnel and 1−

∑
e∈E τ(e) is the percentage of

reserved personnel. We will assigned the total reserved to the central point u ∈ V of the graph Gπ,
that is, the vertex u where the greatest distance dGπ(u,v) to other vertices v is minimal. If there are

more than one central points in the graph Gπ, then we will divide the number of reserved personnel

to the number of central points. Thus, we will have

τ∗(v)=

{
1−

∑
e∈E τ(e)

|C(Gπ)| if v ∈ C(Gπ)
0 if v /∈ C(Gπ).

(1.4)



Int. J. Anal. Appl. (2023), 21:72 3

Here, the set C(Gπ) is the set of all central points of the graph Gπ, that is, the set of all vertices u

where the greatest distance dGπ(u,v) to other vertices v is minimal.

Let Gw =(V,E,w) and Gπ(V,E,π) be a weighted graphs with weight function w : E → [0,1] and
π : E →R, respectively. Set

Y (E, [a,b], [r,s])=

{
w : E → [a,b] | r ≤

∑
e∈E

w(e)≤ s
}
.

Summarizing the equation in (1.1) to (1.4), then we will obtain the problem:

Find τ : E → [a,b] satisying the four condition: . (1.5)

1. 0≤ r ≤
∑
e∈E τ(e)≤ s ≤ 1

2. max
γ∈Y (E,[a,b],[r,s])

(
1−

∑
e∈E

γ(e)

)
=1−

∑
e∈E

τ(e)

3. min
γ∈Y (E,[a,b],[r,s])

∑
e∈E
(w(e)−γ(e))2 =

∑
e∈E
(w(e)−τ(e))2

4. τ∗(v)=

{
1−

∑
e∈E τ(e)

|C(Gπ)| if v ∈ C(Gπ)
0 if v /∈ C(Gπ)

where r,s,a,b ∈ [0,1] such that a < b and r < s.

The following definition is taken from [14].

Definition 1.1. Let G = (V,E,w) be a weighted graph where V is the vertex set and E is the edge

set of G. Then, the center of the graph G, denoted by C(G), is the set of all vertices u ∈ V where
the greatest distance d(u,v) to other vertices v is minimal.

The main objective of this study is to address the problem in definition 1.2.

Definition 1.2. Let Gw = (V,E,w) and Gπ = (V,E,π) be a weighted graph with weight function

w : E → [0,1] and π : E →R, respectively. Let r,s,a,b ∈ [0,1] such that r < s and a < b. Set

Y (E, [a,b], [r,s])= {w : E → [a,b] | r ≤
∑
e∈E

w(e)≤ s}.

The (r,s,a,b)-security assignment problem of G is a problem of finding (τ,τ∗) where τ : E → [a,b]
and τ∗ : V → [0,1] such that
1. r ≤

∑
e∈E τ(e)≤ s ≤ 1

2. max
γ∈Y (E,[a,b],[r,s])

(
1−

∑
e∈E

γ(e)

)
=1−

∑
e∈E

τ(e)

3. min
γ∈Y (E,[a,b],[r,s])

∑
e∈E
(w(e)−γ(e))2 =

∑
e∈E
(w(e)−τ(e))2

4. τ∗(v)=

{
1−

∑
e∈E τ(e)

|C(Gπ)| if v ∈ C(Gπ)
0 if v /∈ C(Gπ)



4 Int. J. Anal. Appl. (2023), 21:72

where C(Gπ) is the center of the graph Gπ. The solution to the security assignment problem is the

ordered pair (τ,τ∗).

The paper is organized as follows. In section 2, we proved a necessary and sufficient condition

when the security assignment problem has a solution. Furthermore, we give an explicit formula for

the solution to the security assignment problem in terms of projection onto the convex set if it has

a solution. In section 3, we record some important properties of the pseudo-solution or solution to

the security assignment problem. Finally, in section 4 we discussed the real-life application of security

assignment problems such as security, CCTV assignment problems, and military assignment problems.

In this study, || · || and 〈·, ·〉 are the standard norm and standard inner product in Rn, respectively.

2. Existence of Solution to the Security Assignment Problem

First, we recall some terminology in convex analysis. The function f : Rn → (−∞,+∞] is convex if
and only if

f (αx +(1−α)y)≤ αf (x)+(1−α)f (y)

for all x,y ∈Rn and for all α ∈ [0,1]. We say that f is proper if and only if f 6≡+∞. In this paper,
the function f :Rn → (−∞,+∞] is always convex, continuous and proper function.

The following definition taken from [10,11] is vital in this paper.

Definition 2.1. Let f : Rn → (−∞,+∞] be a convex, continuous and proper function and u ∈ Rn.
The proximity of u in f is the unique point Proxf (u)∈Rn such that

Proxf (u)= arg min
x∈Rn

(
1

2
||x −u||2 + f (x)

)
. (2.1)

In particular, if C is closed and convex set and f = ιC where ιC(x)= 0 if x ∈ C and +∞, otherwise,
then Proxf (u)= PC(u) where x0 =PC(u) is a unique point in C such that inf

x∈C
||x −u||= ||x0 −u||.

It is well-known that if g = f + α
2
|| · −u||2 + 〈·,v〉 + β where α ≥ 0 and β ∈ R, then

Proxg(x) =Prox(α+1)−1f
(
(α+1)−1(x +(αu − v))

)
(see Proposition 24.8 of [10]). Consequently, if

α =0, f = ιC, then Proxg(x)=PC(x −v) where C is closed and convex set.

The following lemma solves a minimization problem that can be apply in the security assignment

problem.

Lemma 2.1. Let u1,u2, . . . ,un ∈R and let r,s,a,b ∈ [0,1] such that r < s and a < b. Consider the
problem:

min
x1,x2,...,xn∈R

( n∑
i=1

(ui −xi)2 +
n∑
i=1

xi

)
(2.2)



Int. J. Anal. Appl. (2023), 21:72 5

subject to

1. a ≤ xi ≤ b

2. r ≤
n∑
i=1

xi ≤ s

If C = {(x1,x2, . . . ,xn) : a ≤ xi ≤ b and 0 ≤ r ≤
n∑
i=1

xi ≤ s ≤ 1} is nonempty, then the problem

above has exactly one solution. Furthermore, PC(u − 12v) = (x
∗
1,x
∗
2, . . . ,x

∗
n) is the solution to the

problem in (2.2).

Proof. Let x =(x1,x2, . . . ,xn),u ∈ (u1,u2, . . . ,un)and v =(1,1,1, . . . ,1). Let x∗ =(x∗1,x
∗
2, . . . ,x

∗
n)

be the solution to the problem in (2.2). Set

C =

{
(x1,x2, . . . ,xn) : a ≤ xi ≤ b and 0≤ r ≤

n∑
i=1

xi ≤ s ≤ 1
}
. (2.3)

Then, the problem in (2.2) can be written as

min
x∈Rn

(
1

2
||x −u||2 +

1

2
〈x,v〉+ ιC(x)

)
. (2.4)

Since C = [a,b]n ∩{(x1,x2, . . . ,xn) : 0 ≤ r ≤
n∑
i=1

xi ≤ s ≤ 1} is the intersection of two closed and

convex sets, then C is closed and convex. Therefore, the definition 2.1 guaranty that the problem in

(2.2) has a unique solution

Proxg(u)= arg min
x∈Rn

(
1

2
||x −u||2 + 〈x,

1

2
v〉+ ιC(x)

)
(2.5)

where g(x) = 1
2
〈x,v〉+ ιC(x). Furthermore, applying proposition 24.8 of [10] by setting α = 0 and

f = ιC, then we have

Proxg(u)=ProxιC

(
u −
1

2
v

)
=PC

(
u −
1

2
v

)
as desired. �

The following theorem gives an explicit form of the solution to the security assignment problem in

terms of projection onto a convex set if it is existing.

Theorem 2.1. The (r,s,a,b)-security assignment problem of G has at most one solution

(τ,τ∗). Furthermore, if it has a solution (τ,τ∗), then τ(ei) = 〈PD(u − 12v),ui〉 where ui =
(0,0,0, . . . ,0,1,0, . . . ,0) is the vector where the ith coordinate is 1, and 0 elsewhere where

i ∈{1,2, . . . , |E|} and

D =

{
(x1,x2, ...,x|E|)∈R

|E| : 0≤ xi ≤ 1 and r ≤
|E|∑
i=1

xi ≤ s
}
. (2.6)



6 Int. J. Anal. Appl. (2023), 21:72

Proof. If the (r,s,a,b)-security assignment problem of G has a solution (τ,τ∗) and (γ,γ∗), then(
τ(e1),τ(e2), ...,τ(e|E|)

)
and

(
γ(e1),γ(e2), ...,γ(e|E|)

)
are the solution to the problem

min
x1,x2,...,x|E|∈R

( |E|∑
i=1

(w(ei)−xi)2 +
|E|∑
i=1

xi

)
(2.7)

subject to

1. a ≤ xi ≤ b
2. r ≤

∑|E|
i=1

xi ≤ s

Applying lemma 2.1, then
(
τ(e1),τ(e2), ...,τ(e|E|)

)
=
(
γ(e1),γ(e2), ...,γ(e|E|)

)
, and therefore, τ = γ

and τ∗ = γ∗. Furthermore, if the solution (τ,τ∗) to the security assignment problem exists, then

lemma 2.1 implies that
(
τ(e1),τ(e2), ...,τ(e|E|)

)
= PD

(
u−1

2
v
)
where u =

(
w(e1),w(e2), ...,w(e|E|)

)
and v = (1,1,1, ...,1). Thus, for all i = 1,2, ..., |E|, we obtain τ(ei) = 〈PD

(
u − 1

2
v
)
,ui〉, as

desired. �

Lemma 2.1 gives the following definition.

Definition 2.2. Suppose D =
{
(x1,x2, ...,x|V |)∈R|E| : 0≤ xi ≤ 1 and 0≤ r ≤

∑|E|
i=1

xi ≤ s ≤ 1
}
6=

φ. The pseudo-solution of the (r,s,a,b)-security assignment problem of G is the unique ordered pair

(θ,θ∗) where θ : E → [a,b] and θ∗ : V → [0,1] such that
1. 0≤ r ≤

∑
e∈E θ(e)≤ s ≤ 1.

2. min
γ∈Y (E,[a,b],[r,s])

(∑
e∈E
(w(e)−γ(e))2 +

∑
e∈E

γ(e)

)
=
∑
e∈E
(w(e)−θ(e))2 +

∑
e∈E

θ(e).

3. θ∗(v)=

{
1−

∑
e∈E θ(e)

|C(Gπ)| if v ∈ C(Gπ)
0 if v /∈ C(Gπ)

The vector solution to the (r,s,a,b)-security assignment problem is the vector

(θ(e1),θ(e2), . . . ,θ(e|E|)).

Remark 2.1. If the (r,s,a,b)-security assignment problem of G has a solution (τ,τ∗), then it is

unique, and its solution is its pseudo-solution (θ,θ∗).

Corollary 2.1. Let (θ,θ∗) be the pseudo-solution of (r,s,a,b)-security assignment problem of G.

Then, the (r,s,a,b)-security assignment problem of G has a solution if and only if

1. max
γ∈Y (E,[a,b],[r,s])

(
1−

∑
e∈E

γ(e)

)
=1−

∑
e∈E

θ(e).

2. min
γ∈Y (E,[a,b],[r,s])

∑
e∈E
(w(e)−γ(e))2 =

∑
e∈E
(w(e)−θ(e))2.

Example 2.1: Given the crime rate and distance of the road ei where i =1,2,3, ...,8 in the graph G

below (see figure 2.1), determine the percentage of the number of assigned personnel for each road so

that the crime will minimize. Furthermore, we want that the total percentage of assigned personnel is



Int. J. Anal. Appl. (2023), 21:72 7

at most 90% and at least 85%, while the percentage of assigned personnel for each road is at most

25% and at least 5%.

5 km 15%
e1

2 km

10%

e2

3 km

10%

e3

3 km 10%
e4

7 km

25%
e5

6 km

7%
e6 3 km

15%
e7

2 km 8%
e8

Figure 2.1: The Graph G

Solution: We want to solve the (0.85,0.9,0.05,0.25)− security assignment problem, that is, we
want to find τ : E → [0.05,0.25] satisfying the four condition:
1. 0.85≤

∑
e∈E τ(e)≤ 0.90≤ 1

2. max
γ∈Y (E,[0.05,0.25],[0.85,0.9])

(
1−

∑
e∈E

γ(e)

)
=1−

∑
e∈E

τ(e)

3. min
γ∈Y (E,[0.05,0.25],[0.85,0.9])

∑
e∈E
(w(e)−γ(e))2 =

∑
e∈E
(w(e)−τ(e))2

4. τ∗(v)=

{
1−

∑
e∈E τ(e)

|C(Gπ)| if v ∈ C(Gπ)
0 if v /∈ C(Gπ)

where π(ei) is the length of the road ei (in km). Let xi = τ(ei). Then, from lemma 2.1 and theorem

2.1, (x1,x2,x3...,x8) is the solution to the minimization problem:

min
x1,x2,...,x8∈R

( 8∑
i=1

(w(ei)−xi)2 +
8∑
i=1

xi

)
subject to

1. 0.05≤ xi ≤ 0.25
2. 0.85≤

∑8
i=1xi ≤ 0.9.

Applying Lagrange Multiplier using MATLAB, then we obtain the solution

(x1,x2,x3,x4,x5,x6,x7,x8) ≈ (0.135, 0.08, 0.08, 0.08, 0.23, 0.05, 0.135, 0.06). Thus, the
total percentage of assigned security personnel is x1+x2+ ...+x8 =85% and the total percentage of

reserved personnel is 15%. The following table discussed the optimal percentage of assigned security

personnel for each road.



8 Int. J. Anal. Appl. (2023), 21:72

Table 2.1: Percentage of Assigned Number of Personnel per Road
Road Crime Rate Percentage of assigned number of Personnel

e1 15% 13.5%

e2 10% 8%

e3 10% 8%

e4 10% 8%

e5 25% 23%

e6 7% 5%

e7 15% 13.5%

e8 8% 6%

We assigned 15% of the total security personnel to the center of the graph Gπ where the center of

Gπ is the intersection of the road e5,e6 and e7.

3. Properties of the Pseudo-Solution

In this section, we record some important properties of the pseudo-solution that can be help

in solving the security assignment problem. In this section, u = (w(e1),w(e2), . . . ,w(e|E|)),v =

(1,1,1, . . . ,1) and

D =

{
(x1,x2, . . . ,x|E|)∈R

|E| : 0≤ xi ≤ 1 and0≤ r ≤
|E|∑
i=1

xi ≤ s ≤ 1
}
. (3.1)

Theorem 3.1. Suppose D 6= φ. The pseudo-solution (θ,θ∗) to the (r,s,a,b)-security assignment
problem is a solution to the minimization problem: Find θ : E → [a,b] such that

min
γ∈Y (E,[a,b],[r,s])

∑
e∈E
(w(e)−γ(e)+0.5)2 =

∑
e∈E
(w(e)−θ(e)+0.5)2 (3.2)

subject to

0≤ r ≤
∑
e∈E

θ(e)≤ s ≤ 1. (3.3)

Thus, if (x1,x2, . . . ,x|E|) is the solution to the minimization problem, then we have

min
y1,y2,. . . ,y|E|∈R

|E|∑
i=1

(w(ei)−yi +0.5)2 =
|E|∑
i=1

(w(ei)−xi +0.5)2 (3.4)

and

1. a ≤ xi ≤ b
2. 0≤ r ≤

∑|E|
i=1

xi ≤ s ≤ 1.

Proof. By lemma 2.1, x0 is a solution to the problem

min
x∈R|E|

(
1

2
||x −u||2 + 〈x,

1

2
(1,1,1, ...,1)+ ιD(x)

)
(3.5)

if and only if PD(u − 12v)= x0 if and only if



Int. J. Anal. Appl. (2023), 21:72 9

inf
x∈D

1

2

∣∣∣∣
∣∣∣∣x − (u − 12v)

∣∣∣∣
∣∣∣∣2 = 12

∣∣∣∣
∣∣∣∣x0 − (u − 12v)

∣∣∣∣
∣∣∣∣2. (3.6)

Thus, x0 =(θ(e1),θ(e2), . . . ,θ(e|E|)) if and only if

min
γ∈Y (E,[a,b],[r,s])

∑
e∈E

(
w(e)−γ(e)+0.5

)2
=
∑
e∈E

(
w(e)−θ(e)+0.5

)2
(3.7)

subject to

0≤ r ≤
∑
e∈E

θ(e)≤ s ≤ 1. (3.8)

as desired. �

The projection theorem state that x0 = PC(x) if and only if x0 ∈ C and 〈p − y,p − x〉 ≤ 0 for all
y ∈ C (See theorem 3.16 in [10]). Thus, the following corollary directly holds.

Corollary 3.1. Suppose D 6= φ. The point x0 ∈R|E| is the solution to

min
x∈R|E|

{
1

2
||x −u||2 + 〈x,

1

2
v〉+ ιD(x)

}
. (3.9)

if and only if x0 ∈ D and for all y ∈ D, we have

〈x0 −y,x0 −u +
1

2
v〉≤ 0. (3.10)

Proof. The point x0 is a solution to

min
x∈R|E|

{
1

2
||x −u||2 + 〈x,

1

2
v〉+ ιD(x)

}
(3.11)

if and only if PD
(
u − 1

2
v
)
= x0. Thus, the projection theorem implies that PD

(
u − 1

2
v
)
= x0 if and

only if x0 ∈ D and for all y ∈ D, we have

〈x0 −u +
1

2
v,x0 −y〉≤ 0 (3.12)

as desired. �

The following definition taken from [10] state the notion of Fenchel conjugate and Gateaux-

differentiable of a function which is important in the next result.

Definition 3.1. Let f :Rn → (−∞,+∞] be a convex, continuous and proper function. The Fenchel
conjugate f ∗ of f is a function defined by

f ∗ = sup
x∈Rn
(〈x, ·〉− f (x)).

Definition 3.2. Let f :Rn → (−∞,+∞] be a convex, continuous and proper function. The function
f is said to be Gateaux differentiable at x0 if and only if the limit below exists for all u ∈Rn.

Duf (x0)= lim
α→0+

1

α
(f (x0 +αu)+ f (x0)).

The function D :Rn →R : u 7→ Duf (x0) is called the Gateaux derivative of f . The Gateaux gradient
of f is the unique vector 5f (x) satisfying the equation Duf (x)= 〈u,5f (x)〉.



10 Int. J. Anal. Appl. (2023), 21:72

The next results give a characterization of the pseudo-solution in terms of the solution to the dual

problem of the primal problem

min
x∈R|E|

{
1

2
||x −u||2 + 〈x,

1

2
v〉+ ιD(x)

}
. (3.13)

Theorem 3.2. Suppose D 6= φ. Let x0 = (τ(e1),τ(e2), . . . ,τ(e|E|)) be the vector solution to the
(r,s,a,b)-security assignment problem, let u = (w(e1),w(e2), . . . ,w(e|E|)) and v = (1,1,1, . . . ,1).

Then, the problem

min
x∈R|E|

{
1

2
||y||2 −〈y,u〉+sup

x∈D
〈x,y −

1

2
v〉
}

(3.14)

has a unique solution u −x0. In addition, Proxh(u)= x0 where h(y)= sup
x∈D
〈x,y −

1

2
v〉.

Proof. Consider the primal problem

min
x∈R|E|

{
1

2
||x −u||2 + 〈x,

1

2
v〉+ ιD(x)

}
. (3.15)

Then, x0 is the solution to the primal problem above. Let f (x)=
1
2
||x−u||2 and g(x)= 〈x, 1

2
v〉+ιD(x).

Then, f ∗(a)= 1
2
||a||2 + 〈a,u〉 and

g∗(a)= sup
x∈R|E|

{〈x,a−
1

2
v〉− ιD(x)}= sup

x∈D
〈x,a−

1

2
v〉. (3.16)

Thus, the dual problem of the primal problem in (3.15) is

min
x∈R|E|

{
1

2
||y||2 + 〈y,u〉+sup

x∈D
〈x,y −

1

2
v〉
}
. (3.17)

Since y is the solution to the dual problem, x0 is the solution to the primal problem and f ∗ is Gateaux

differentiable everywhere, then by proposition 19.4 of [10], x0 =5f ∗(−y), and thus, x0 =5f ∗(−y)=
−y +u, as desired. �

4. Some Real-Life Application

In this section, we present some real-life application of security assignment problem.

a. Security Assignment Problem for a Road

Let G represent the whole map of a city, E be the set of all roads (or major roads) of the city, V

be the set of the intersection of roads. Let w(e) be the criminal rate (or population rate, number of

houses, etc.) of the road e ∈ E and π(e) be the time needed to travel the road e (or length of the
road, the volume of a vehicle in the road, etc.). Then, the (r,s,a,b)-security assignment problem is

a problem of finding the percentage of security personnel τ(e) that will assign in road e and finding

the percentage of number of reserved security personnel τ∗(e) that will assign to the center of the

city C(Gπ) so that the total percentage of reserved security personnel is at most 1− r and at least
1−s where r,s ∈ [0,1] and r < s. We want to find τ : E → [a,b] where a,b ∈ [0,1] and a < b such



Int. J. Anal. Appl. (2023), 21:72 11

that if we assign 100τ(e) percent of security personnel to road e, for all e ∈ E, then the crime will
minimize, that is, we want to solve the problem of finding τ : E → [a,b] such that

min
γ∈Y (E,[a,b],[r,s])

∑
e∈E
(w(e)−γ(e))2 =

∑
e∈E
(w(e)−τ(e))2. (4.1)

In addition to that, we want to maximize the total percentage of reserved security personnel, that is,

we have

max
γ∈Y (E,[a,b],[r,s])

(
1−

∑
e∈E

γ(e)

)
=1−

∑
e∈E

τ(e). (4.2)

Since the total percentage of reserved security personnel is at-most 1− r and at least 1− s where
r,s ∈ [0,1] and r < s, then we have

0≤ r ≤
∑
e∈E

τ(e)≤ s ≤ 1. (4.3)

Summarizing equation (4.1) to (4.3), then we recover the problem in definition 1.2.

Note that the security assignment problem can be applied in assigning security personnel for

the checkpoint or any related problem. If the (r,s,a,b)-security assignment problem has no so-

lution, then the strategic solution is the pseudo-solution of the (r,s,a,b)-security assignment problem.

b. CCTV Assignment Problem for a Road

Let G represent the whole map of a certain town, E be the set of all roads (or major roads) of the

town, V be the set of the intersection of roads. Let w(e) be the criminal rate (or population rate,

number of houses, etc.) of the road e ∈ E and π(e) be the length the road e (or population, number
of establishments, the volume of vehicle in the road, etc.). Then, the (r,s,a,b)-security assignment

problem for CCTV installation is a problem of finding the percentage of number of CCTV τ(e)∈ [a,b]
that will install in road e and finding the percentage of number of CCTV τ∗(e) that will install to

the center of the city C(Gπ) so that the total percentage of CCTV that will assign to the center of

the city C(G) is at-most 1− r and at least 1− s where r,s ∈ [0,1] and r < s. We want to find
τ : E → [a,b] where a,b ∈ [0,1] and a < b such that if we install 100τ(e) percent of CCTV to road
e, for all e ∈ E, then this is the best strategic installation, that is, we want to solve the problem of
finding τ : E → [a,b] such that

min
γ∈Y (E,[a,b],[r,s])

∑
e∈E
(w(e)−γ(e))2 =

∑
e∈E
(w(e)−τ(e))2. (4.4)

In addition to that, we want to maximize the total percentage of CCTV that will assign to the center

of the city C(Gπ), that is, we have

max
γ∈Y (E,[a,b],[r,s])

(
1−

∑
e∈E

γ(e)

)
=1−

∑
e∈E

τ(e). (4.5)



12 Int. J. Anal. Appl. (2023), 21:72

Since the total percentage of CCTV that will assign to the center of the city C(G) is at most 1− r
and at least 1− s where r,s ∈ [0,1] and r < s, then we have

0≤ r ≤
∑
e∈E

τ(e)≤ s ≤ 1. (4.6)

Summarizing the equation (4.4) to (4.6), then we obtain the problem in definition 1.2. If the

(r,s,a,b)-security assignment problem has no solution, then the strategic solution is the pseudo-

solution of (r,s,a,b)-security assignment problem.

c. Security Assignment Problem for a Planar Map

Before we discuss the application of this study in planar graph, we recall first the definition of line

graph L(G) of a graph G and planar graph.

Definition 4.1. Let G be a graph. The line graph L(G) of G is a graph such that each vertex of L(G)

represents an edge of G and two vertices of L(G) are adjacent if and only if their corresponding edges

share a common endpoint in G.

Definition 4.2. Let H be a map with region U1,U2, ...,Un. The planar graph of H is the graph G

where the vertex of G represent the region of H and two vertices in G are adjacent if and only if their

corresponding region are adjacent.

Consider the map with regions U1,U2, . . . ,Un and let G = (V,E) be a planar graph of the map

where V = {u1,u2, . . . ,un}. Let µ(Ui) be the criminal rate (or population rate, number of houses,
etc.) of the region Ui. Let L(G) = (L(V ),L(E)) be the line graph of G and set w : L(E) → [0,1]
such that w(ui,j,ui,k)=

µ(Ui)(
degui
2

) where
(
degui
2

)
=

degui!

(degui!−2)2!
=
degui(degui −1)

2
. (4.7)

Set π = τ. The (r,s,a,b)-security assignment problem is a problem of finding the percentage of

number of security personnel τ(e) that will assign in the edge e and finding the percentage of number

of reserved security personnel τ∗(e) that will assign to the center of the graph L(G) so that the total

percentage of reserved security personnel is at most 1− r and at least 1− s where r,s ∈ [0,1] and
r < s. We want to find τ : E → [a,b] such that if we assign 100τ(e) percent of security personnel
to edge e, for all e ∈ L(E), then the crime will minimize, that is, we want to solve the problem of
finding τ : E → [0,1] such that

min
γ∈Y (L(E),[a,b],[r,s])

∑
e∈L(E)

(w(e)−γ(e))2 =
∑

e∈L(E)

(w(e)−τ(e))2. (4.8)

In addition to that, we want to maximize the total percentage of reserved security personnel, that is,

we have



Int. J. Anal. Appl. (2023), 21:72 13

max
γ∈Y (L(E),[a,b],[r,s])

(
1−

∑
e∈L(E)

γ(e)

)
=1−

∑
e∈L(E)

τ(e). (4.9)

Since the total percentage of reserved security personnel is at most 1− r and at least 1− s where
r,s ∈ [0,1] and r < s, then we have

0≤ r ≤
∑

e∈L(E)

τ(e)≤ s ≤ 1. (4.10)

The percentage of assigned security personnel in region Ui is∑
j ∈ 1,2, ..., |V |
ui,jui,k ∈ L(E)

τ(ui,jui,k). (4.11)

If the (r,s,a,b)-security assignment problem has no solution, then the strategic solution is the

pseudo-solution of (r,s,a,b)-security assignment problem.

Example 4.1: Consider the map below, which shows the crime rate of each region. We need to

determine the best strategic assignment of security personnel from region 1 to region 5 in order to

minimize crime. However, we must ensure that we assign a maximum of 30% of security personnel

for each e ∈ L(G). Additionally, we want to ensure that the reserve security personnel make up at
least 5%.

40% 

15% 

15% 

10% 

20% 

 

 

 

 

 

   

 

 

 

 

 

Figure 4.1 The Planar Region

Constructing the planar graph G of the map, then we obtain

40% 

15% 

15% 

10% 
20% 

 

 

 

 

 

   

 

 

 

 

 

Figure 4.2: The Planar Graph and Planar Region

By constructing the line graph of the planar graph G, then we obtain L(G)



14 Int. J. Anal. Appl. (2023), 21:72

u1

u2

u4
u3

u5

u1,2

u1,4

u1,5 u4,5

u2,4 u2,3

u3,4

Figure 4.3: The Line Graph and Planar Graph

Set w : L(E)→ [0,1] such that w(ui,jui,k)=
µ(Ui)(
degui
2

) where µ(Ui) is the crime rate of region Ui and
(
degui
2

)
=

degui!

(degui!−2)2!
=
degui(degui −1)

2
. (4.12)

Thus, we obtain

w(u1,2u1,4)= w(u1,2u1,5)= w(u1,4u1,5)=
20%

3
=
1

15

w(u2,4u1,2)= w(u2,4u2,3)= w(u1,2u2,3)=
15%

3
=
1

15

w(u2,3u3,4)=
10%

1
=
1

10

w(u1,4u2,4)= w(u2,4u3,4)= w(u3,4u4,5)= w(u1,4u4,5)

= w(u2,4u4,5)= w(u1,4u3,4)=
40%

6
=
1

15

w(u1,5u4,5)=
15%

1
=
3

20

1
15

1
20

1
20

1
15

1
15

1
15

1
15

1
15

3
20

1
15

1
20

1
15

1
15

1
10

u1,2

u1,4

u1,5 u4,5

u2,4 u2,3

u3,4

Figure 4.4: Weighted Line Graph

The problem wants to solve the (r,s,a,b)-security assignment problem of L(G) where r = 0,

s =0.95, a =0 and b =0.3. The (0,0.95,0,0.3)-security assignment problem of L(G) is a problem

of finding τ : L(E)→ [0,0.3] such that
1. min

γ:L(E)→[0,0.3]

∑
e∈L(E)

(
w(e)−γ(e)

)2
=

∑
e∈L(E)

(
w(e)−τ(e)

)2
.



Int. J. Anal. Appl. (2023), 21:72 15

2. max
γ:L(E)→[0,0.3]

(
1−

∑
e∈L(E)

γ(e)
)
=1−

∑
e∈L(E)

τ(e).

3. 0≤ r ≤
∑
e∈L(E)τ(e)≤ s ≤ 1.

From theorem 3.1, we can obtain the vector solution of the (r,s,a,b)-security assignment problem

of L(G) by finding the solution (x∗1,x
∗
2, . . . ,x

∗
14) of the problem

min
x1,x2,. . . ,x14∈R

( 14∑
i=1

(xi −w(ei)−0.5
)2

(4.13)

subject to

1. 0≤ xi ≤ 0.3.
2. 0≤

∑|L(E)|
i=1

xi ≤ 0.95.
Thus, we have

min
x1,x2,. . . ,x14∈R

((
x1 −

17

30

)2
+

(
x2 −

17

30

)2
+

(
x3 −

17

30

)2
+

(
x4 −

11

20

)2
+

(
x5 −

11

20

)2
+

(
x6 −

11

20

)2
+

(
x7 −

3

5

)2
+

(
x8 −

17

30

)2
+

(
x9 −

17

30

)2
+

(
x10 −

17

30

)2
+

(
x11 −

17

30

)2
+

(
x12 −

17

30

)2
+

(
x13 −

17

30

)2
+

(
x14 −

13

20

)2)
subject to

1. 0≤ xi ≤ 0.3.
2. 0≤

∑|L(E)|
i=1

xi ≤ 0.95.

Applying Lagrange multiplier, then we obtain the approximate solution (0.0631, 0.0631, 0.0631,

0.0464, 0.0464, 0.0464, 0.0964, 0.0631, 0.0631, 0.0631, 0.0631, 0.0631, 0.0631, 0.1464). Thus,

we have the following:

Percentage of Assigned Number of Personnel per Region
Table 5.1: Region Crime Rate Percentage of assigned number of Personnel

1 20% 0.0631+0.0631+0.0631=0.1893 (18.93%)

2 15% 0.0464+0.0464,+0.0464=0.13.92 (13.92%)

3 10% 0.0964 (9.64%)

4 40% 0.0631+0.0631+0.0631+0.0631+0.0631+0.0631=0.3786(37.86%)

5 15% 0.1464 (14.64%)

Therefore, by considering the graph and weight of the region, the optimal percentage of total assigned

security personnel is 95% and the percentage of reserved security personnel is 5%.

5. Conclusions

This study proved that the (r,s,a,b)-security assignment problem of G has at most one so-

lution (τ,τ∗). Furthermore, if it has a solution (τ,τ∗), then τ(ei) = 〈PD(u − 12v),ui〉 where



16 Int. J. Anal. Appl. (2023), 21:72

ui = (0,0,0, . . . ,0,1,0, . . . ,0) is the vector where the ith coordinate is 1, and 0 elsewhere where

i ∈{1,2, . . . , |E|} and

D =

{
(x1,x2, ...,x|E|)∈R

|E| : 0≤ xi ≤ 1 and0 ≤ r ≤
|E|∑
i=1

xi ≤ s ≤ 1
}

In addition, we proved that if (θ,θ∗) is the pseudo-solution of (r,s,a,b)-security assignment problem

of G, then the (r,s,a,b)-security assignment problem of G has a solution if and only if

1. max
γ∈Y (E,[a,b],[r,s])

(
1−

∑
e∈E

γ(e)

)
=1−

∑
e∈E

θ(e).

2. min
γ∈Y (E,[a,b],[r,s])

∑
e∈E
(w(e)−γ(e))2 =

∑
e∈E
(w(e)−θ(e))2.

The model is applicable in security assignment problem and CCTV assignment problem.

Conflicts of Interest: The authors declare that there are no conflicts of interest regarding the publi-

cation of this paper.

References

[1] Z. Ghazali, M.A.A. Majid, M. Shazwani, Optimal Solution of Transportation Problem Using Linear Programming:

A Case of a Malaysian Trading Company, J. Appl. Sci. 12 (2012), 2430-2435. https://doi.org/10.3923/jas.

2012.2430.2435.

[2] A.J. Mehta, A.K. Rifai, Goal Programming Application to Assignment Problem in Marketing, J. Acad. Market. Sci.

7 (1979), 108-116. https://doi.org/10.1007/bf02721918.

[3] J.A. Breslaw, A Linear Programming Solution to the Faculty Assignment Problem, Socio-Econ. Plan. Sci. 10 (1976),

227-230. https://doi.org/10.1016/0038-0121(76)90008-2.

[4] C. van Dooren, A Review of the Use of Linear Programming to Optimize Diets, Nutritiously, Economically and

Environmentally, Front. Nutr. 5 (2018), 48. https://doi.org/10.3389/fnut.2018.00048.

[5] J. Foytik, Very Low-Cost Nutritious Diet Plans Designed by Linear Programming, J. Nutr. Educ. 13 (1981), 63-66.

https://doi.org/10.1016/s0022-3182(81)80098-2.

[6] A. Briend, N. Darmon, Determining Limiting Nutrients by Linear Programming: A New Approach to Predict

Insufficient Intakes From Complementary Foods, Pediatrics. 106 (2000), 1288-1289. https://doi.org/10.1542/

peds.106.s4.1288.

[7] A. Briend, E. Ferguson, N. Darmon, Local Food Price Analysis by Linear Programming: A New Approach to Assess

the Economic Value of Fortified Food Supplements, Food Nutr. Bull. 22 (2001), 184-189. https://doi.org/10.

1177/156482650102200210.

[8] D.H. Stimson, R.P. Thompson, Linear Programming, Busing and Educational Administration, Socio-Econ. Plan.

Sci. 8 (1974), 195-206. https://doi.org/10.1016/0038-0121(74)90043-3.

[9] J. Reeb, S. Leavengood, Using Duality and Sensitivity Analysis to Interpret Linear Programming Solutions, Oregon

State University, 2000. http://hdl.handle.net/1957/20129.

[10] H.H. Bauschke, P.L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer,

Cham, 2017. https://doi.org/10.1007/978-3-319-48311-5.

[11] Y.L. Yu, The Proximity Operators, (2014). https://www.cs.cmu.edu/~suvrit/teach/yaoliang_proximity.pdf.

[12] J. Dattorro, Convex Optimization in Euclidean Distance Geometry, (2005). https://ccrma.stanford.edu/

/~dattorro/0976401304.pdf.

[13] S.P. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004.

https://doi.org/10.3923/jas.2012.2430.2435
https://doi.org/10.3923/jas.2012.2430.2435
https://doi.org/10.1007/bf02721918
https://doi.org/10.1016/0038-0121(76)90008-2
https://doi.org/10.3389/fnut.2018.00048
https://doi.org/10.1016/s0022-3182(81)80098-2
https://doi.org/10.1542/peds.106.s4.1288
https://doi.org/10.1542/peds.106.s4.1288
https://doi.org/10.1177/156482650102200210
https://doi.org/10.1177/156482650102200210
https://doi.org/10.1016/0038-0121(74)90043-3
http://hdl.handle.net/1957/20129
https://doi.org/10.1007/978-3-319-48311-5
https://www.cs.cmu.edu/~suvrit/teach/yaoliang_proximity.pdf
https://ccrma.stanford.edu//~dattorro/0976401304.pdf
https://ccrma.stanford.edu//~dattorro/0976401304.pdf


Int. J. Anal. Appl. (2023), 21:72 17

[14] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, Elsevier, New York, (1976).

[15] B. Nag, Business Applications of Operations Research, Business Expert Press, New York, 2014.


	1. Introduction
	2. Existence of Solution to the Security Assignment Problem
	3. Properties of the Pseudo-Solution
	4. Some Real-Life Application
	5. Conclusions
	References