On the Application of Nonlinear Programming Techniques to Search Problems

Since the dawn of human civilization, people have continually developed methods, techniques, and technologies aimed at simplifying tasks and improving daily life. These innovations have been progressively refined and integrated into practical applications. In recent years, rapid advancements in science and technology have led to the widespread dissemination of intelligent technologies. It is evident that applied mathematics plays a crucial role in underpinning and advancing these technological developments. Most phenomena in the universe exhibit inherently nonlinear characteristics. Although numerous analytical, computational, and algorithmic methods for studying such phenomena have been developed and continue to expand, they remain insufficient in fully addressing the complexity involved. Among various application domains, mathematics plays a particularly important role in military research and analysis. Specifically, operations research methods are widely applied in military operations to address a wide range of problems that may arise at all stages of combat preparation and execution. The application of mathematical sciences to military problems provides several important benefits, including the systematic interpretation of military challenges, the simplification of complex difficulties, the ability to analyze problems from multiple perspectives, and the enhancement of logical reasoning skills. These advantages constitute the primary motivation for investigating the present topic. Within this work, the fundamental concepts of linear and nonlinear programming were reviewed based on textbooks [1, 2, 3, 4, 7], along with studies related to search and reconnaissance problems [2, 6, 8, 9]. In addition, the work presented in [5], which addresses the application of nonlinear programming methods to military problems, was examined and utilized in this study. In this paper, a military related problem formulated within the framework of nonlinear programming is considered, and several search problems are constructed and analyzed based on this formulation. The primary objective is to develop and solve search problems derived from the original military model. Accordingly, the significance of this work lies in taking a step toward applying nonlinear programming models originally used in military contexts to the solution of search and reconnaissance problems.

• 1    General Formulation of Problem

We consider allocating heterogeneous combat units to operational regions. Suppose that there are m types of combat units that must be allocated to targets located in n regions. Denote:

• •    P j : prior probability that a target is present in region j , j = 1 , 2 ,...,n;

• •    W ij : probability of detecting a target in region j if a unit of type i is sent to region j, i = 1 , 2 ,..., m;

• •    h ij G { 0 , 1 } : The allocation of combat units to the regions is represented by the control (decision) parameters h ij . (h ij = 1 if unit i is directed to region j, else 0 ).

The objective function for allocating forces to the operational regions, by selecting appropriate values of h ij , is formulated so as to maximize the overall detection probability P and is given by the following expression.

n

P = X Pj j=1

m

¹ - П( 1 - h ij W ij )

i =1

—> max .

Each unit must be assigned to exactly one region:

n

^hij = 1 , i = 1 , 2 ,...,m.                  (2)

j =i

If at most one unit is directed to any region (i.e., 5I2m=i hij — 1 for each j), then for each fixed j at most one hij equals 1, hence mm

П(1 - hijWij) = 1 - X hijWij.

i=i

Substituting (3) into (1) yields a linear objective:

nm

P = EE hij Pj Wij.

j =i i =i

Let a ij = P j W ij and A = [ a j ] . The problem reduces to a (possibly rectangular) maximum-weight assignment.

1.1    Solution Methodology and Algorithm

To solve this class of problems, we first construct the matrix

A = II P , W ij l| .

and then transform A through a sequence of equivalent transformations.

• a) . For each column of the matrix A, determine the maximum element. Subtract this maximum from all elements of the corresponding column, and form a new matrix.

• b) . For each row of the resulting matrix, determine the minimum element. Subtract this value from all elements of that row. Denote the obtained matrix by A ⁽⁰⁾ . By construction, each row and each column of A ⁽⁰⁾ contains at least one zero.

From the matrix A ⁽⁰⁾ , select an arbitrary zero in the first column and mark it with a star. Proceed to the second column, and mark a zero with a star if and only if there is no starred zero in the row containing that zero. The same rule is applied successively to the remaining columns. The starred zeros obtained in this manner are referred to as independent zeros .

The problem is then solved iteratively by a successive approximation procedure. At each iteration step, the number of independent zeros is increased by one. The algorithm terminates when the number of independent zeros becomes equal to n, at which point an optimal solution is obtained.

The iteration procedure is carried out according to the following steps:

• 1.    In the matrix A ⁽⁰⁾ (or, in the general case, in the matrix obtained at the previous iteration), mark with the symbol “ + ” all columns that contain independent zeros. The elements belonging to the marked columns are referred to as marked elements .

• 2.    Examine whether there exists at least one zero among the unmarked elements. If such a zero exists, proceed to Step 3; otherwise, go to Step 5.

• 3.    Select an arbitrary unmarked zero and denote it by 0 0 . Check whether there exists a starred zero 0 * in the same row:

• •    if a starred zero exists in that row, mark the row with the symbol “ + ” and remove (cross out) the mark from the column containing this starred zero, then return to Step 2;

• •    if no starred zero exists in that row, proceed to Step 4.

• 4.    Starting from the zero 0 0 , construct an alternating sequence (chain) of primed zeros 0 ⁰ and starred zeros 0 ^* until no further extension is possible. The transition from 0 ⁰ to 0 ^* is performed along a column, whereas the transition from 0 ^* to 0 ⁰ is performed along a row. Assign stars to the zeros in odd positions of the chain and remove stars from the zeros in even positions. As a result, the number of independent zeros increases by one. Remove all marks and signs. If the number of starred zeros is less than n, return to Step 1; otherwise, proceed to Step 6.

• 5.    Among all unmarked elements, determine the smallest element and denote it. Subtract this value from all unmarked elements, and add it to the elements located at the intersections of marked rows and marked columns. Then return to Step 2.

• 6.    Determine the optimal allocation. The optimal assignment corresponds to the positions of independent zeros in the final matrix. The sum of the values P j W ij corresponding to these positions yields the maximum value of the objective function P .

Application 1. A mathematical modeling framework for estimating the location of livestock displaced during a severe snowstorm

During a severe snowstorm, a herd of horses belonging to a herder in Altanshiree soum of Dornogovi province was displaced. It was decided that three individuals would conduct a search operation. Let the probabilities that the herd is located in Altanshiree, Urgu¨n, and Erdene soums be denoted, respectively, by

P 1 = 0 . 5 ,     P 2 = 0 . 3 ,     P 3 = 0 . 2 .

The probabilities that each searcher can locate the herd in each soum are given in Table 1 .

Table 1: Probabilities W ij of detecting the herd

Searcher ( i )	Altanshiree	Urgu¨n	Erdene
Zorigt	0.30	0.35	0.63
Ukhnaa	0.66	0.51	0.54
Bataa	0.32	0.43	0.36

The objective is to assign each of the three searchers to exactly one soum so as to maximize the overall probability P of detecting the herd.

Mathematical Formulation

The problem is formulated as

33 P = Y.P 1 - П(1 - hijWj  -^ max,         (1) j=1          i=1 subject to 3 X hij = 1,     i = 1,2,3,                       (2) j=1 where hij G {0,1} denotes whether searcher i is assigned to soum j.

Let

0 . 30 0 . 35 0 . 63

( P 1 , P 2 , P 3 ) = (0 . 5 , 0 . 3 , 0 . 2) ,       ( W ij ) = 0 . 66 0 . 51 0 . 54 .

0 . 32 0 . 43 0 . 36

Construction of the Weight Matrix

The weight matrix A = ( a ij ) with a ij = P j W ij is

5 • 30

2 • 63

10 100 10 100 10 100

To remove decimals, all elements are multiplied by 10 ³ . Applying the algorithm described in the previous section yields, after completion of the iteration process, the reduced matrix

A (0) =   0 ∗

48 0 0 ^∗

0 ^∗

where the starred zeros indicate independent zeros. The iteration terminates at this stage.

Optimal Solution

The positions of the independent zeros in A ⁽⁰⁾ determine the optimal search assignment, summarized in Table 2 .

Table 2: Optimal assignment of searchers

Searcher (i) Zorigt Ukhnaa Bataa

Altanshiree

x

Urgu¨n

x

Erdene x

Maximum Detection Probability

Using the optimal assignment, the maximum probability of detecting the herd is

P = 0 . 66 • 0 . 5 + 0 . 43 • 0 . 3 + 0 . 63 • 0 . 2 = 0 . 33 + 0 . 129 + 0 . 126 = 0 . 585 .

Hence, the optimal strategy is to assign Ukhnaa to Altanshiree soum, Bataa to Urgu¨n soum, and Zorigt to Erdene soum. Under this allocation, the probability of locating the displaced herd is P = 0 . 585 .

Application 2. Identification of Coal Deposits Using Six Geological Survey Teams Across Four Provinces

Six geological survey teams are tasked with identifying coal-bearing deposits across four provinces in southern Mongolia (m = 6 , n = 4 ). The provinces under consideration are Khentii, Dornod, Sukhbaatar, and Govisumber. The prior probabilities that coal deposits exist in these provinces are assumed as follows:

P 1 = 0 . 2 ,     P 2 = 0 . 3 ,     P 3 = 0 . 4 ,     P 4 = 0 . 1 .

The probabilities W ij that the i-th geological team can discover a coal deposit in the j-th province are presented in Table 3 .

Table 3: Probabilities W ij of identifying coal deposits

Geological team (i) Govisumber team	Khentii 0.30	Dornod 0.65	Sukhbaatar 0.32	Govisumber 0.41
Khentii team	0.66	0.51	0.19	0.34
Dornogovi team	0.32	0.17	0.39	0.36
Sukhbaatar team	0.43	0.46	0.58	0.38
Ulaanbaatar team	0.32	0.42	0.46	0.39
Dornod team	0.51	0.56	0.61	0.49

The objective is to allocate geological teams to provinces in such a way that the overall probability P of detecting coal deposits is maximized. In this problem, at most one geological team can be assigned to each province.

Problem Decomposition

Since the number of teams exceeds the number of provinces (m > n), the original problem is decomposed into subproblems by selecting four teams at a time from the six available teams. This results in ⁶ ₄ = 15 subproblems, each consisting of a one-to-one assignment between four geological teams and four provinces.

For each subproblem, the maximum detection probability was computed using the methodology described in the previous section. The resulting optimal probabilities are

0 . 595 , 0 . 598 , 0 . 610 , 0 . 547 , 0 . 607 , 0 . 609 , 0 . 530 , 0 . 542 ,

0 . 583 , 0 . 586 , 0 . 526 , 0 . 571 , 0 . 571 , 0 . 538 , 0 . 496 .

The maximum among these values is max = 0.610.

Optimal Assignment

Based on the subproblem yielding the maximum detection probability, the optimal assignment of geological teams to provinces is determined as follows:

• •    the Govisumber geological team is assigned to Dornod province,

• •    the Khentii geological team is assigned to Khentii province,

• •    the Ulaanbaatar geological team is assigned to Govisumber province,

• •    the Dornod geological team is assigned to Sukhbaatar province.

Under this allocation, the overall probability of identifying coal-bearing deposits in the four provinces attains its maximum value of

P = 0 . 610 .

Application 3. A Search Problem for Locating a Crashed Aircraft

Consider an aircraft that was operating a flight from Ulaanbaatar to Bayan-Olgii province and is assumed to have crashed. During the flight, an unavoidable natural event occurred, and communication with the aircraft was lost while it was flying over Zavkhan province. Accordingly, a search operation is to be conducted across four provinces: Zavkhan, Uvs, Khovd, and Bayan-Olgii. The ob jective is to optimally allocate three different types of search teams to these regions.

Let the probabilities that the aircraft crashed within the territory of the four provinces be

P1 = 0.1,     P2 = 0.3,     P3 = 0.4,     P4 = 0.2, corresponding to Zavkhan, Uvs, Khovd, and Bayan-Olgii, respectively.

The probabilities W ij that each search team can locate the aircraft within each province are provided in Table 4 .

Table 4: Probabilities W ij of locating the crashed aircraft

Search team (i)	Zavkhan	Uvs	Khovd	Bayan-Olgii
Vehicle-based team	0.15	0.11	0.32	0.18
Helicopter-based team	0.26	0.15	0.19	0.16
Motorcycle-based team	0.18	0.17	0.21	0.13

The aim is to assign each search team to exactly one search region so that the overall probability P of locating the crashed aircraft is maximized.

Problem Decomposition

Since the number of search regions exceeds the number of available teams, the problem is decomposed into four subproblems, each corresponding to the selection of three out of the four possible regions. Each subproblem thus involves an equal number of search teams and regions, allowing the application of the assignment methodology described earlier.

Optimal Assignment and Result

After solving all four subproblems and comparing their outcomes, the maximum overall detection probability is obtained as

P = 0 . 211 .

The optimal allocation achieving this value is as follows:

• •    the vehicle-based search team is assigned to Khovd province,

• •    the helicopter-based search team is assigned to Bayan-Olgii province,

• •    the motorcycle-based search team is assigned to Uvs province.

Under this optimal strategy, no search team is allocated to Zavkhan province, indicating that searching in that region is not required to maximize the overall detection probability.

Conclusion

The main objective of this study was to adapt a problem originally formulated for allocating combat assets to targets and apply it to search and reconnaissance problems. Based on the obtained results, it can be concluded that this objective has been successfully achieved. Within this framework, three representative search problems were formulated and solved, thereby demonstrating the applicability of the proposed approach.

While classical algorithms are typically designed for cases in which the number of assets and the number of targets are equal, this study addressed more general situations in which these quantities differ. In particular, Applications 2 and 3 illustrated practical solution strategies for such unequal cases by decomposing the original problem into suitable subproblems and applying the developed methodology.

Future work will focus on developing a software implementation that can be directly applied to similar search and reconnaissance problems considered in this paper. Such a tool would enhance the practical usability of the proposed approach in real-world applications.