Abstract
The aim of this paper is twofold: first, to extend the area of applications of tropical optimization by solving new constrained location problems, and second, to offer new closed-form solutions to general problems that are of interest to location analysis. We consider a constrained minimax single-facility location problem with addends on the plane with rectilinear distance. The solution commences with the representation of the problem in a standard form, and then in terms of tropical mathematics, as a constrained optimization problem. We use a transformation technique, which can act as a template to handle optimization problems in other application areas, and hence is of independent interest. To solve the constrained optimization problem, we apply methods and results of tropical optimization, which provide direct, explicit solutions. The results obtained serve to derive new solutions of the location problem, and of its special cases with reduced sets of constraints, in a closed form, ready for practical implementation and immediate computation. As illustrations, numerical solutions of example problems and their graphical representation are given. We conclude with an application of the results to optimal location of the central monitoring facility in an indoor video surveillance system in a multi-floor building environment.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Tropical (idempotent) mathematics, originated in the middle of the last century as the theory and applications of semirings with idempotent addition, finds use in a variety of fields, from operations research to algebraic geometry. The significant advances, achieved in the area of tropical mathematics in the last decades, are reported in several monographs, including recent ones by Golan (2003), Heidergott et al. (2006), McEneaney (2006), Itenberg et al. (2007), Gondran and Minoux (2008), and Maclagan and Sturmfels (2015), and in a wide range of research papers.
Optimization problems that are formulated and solved in terms of tropical mathematics are a matter of concern for tropical optimization, which presents an important research domain, with the focus on new solutions to old and fresh problems in operations research and management science. Applications of tropical optimization include real-world problems in project scheduling, location analysis, transportation networks, discrete event dynamic systems, decision making, and in other fields.
Location problems constitute one of the classical areas in optimization, which dates back to the XVII century. A variety of approaches and techniques exists to solve location problems in different settings, including methods of mathematical programming, and of discrete, combinatorial and graph optimization (see, e.g., Sule 2001; Klamroth 2002; Farahani and Hekmatfar 2009; Eiselt and Marianov 2011; Laporte et al. 2015, for the current state of the art in the area).
There are certain location problems that have solutions obtained in the framework of tropical optimization. Specifically, a solution in terms of tropical mathematics is proposed by Cuninghame-Green (1991, 1994) to one-dimensional minimax location problems defined on graphs. Furthermore, several constrained minimax location problems are examined by Zimmermann (1992a, b), Hudec and Zimmermann (1993, 1999), and Tharwat and Zimmermann (2010) in the context of the theory of max-separable functions, which is closely related to the tropical mathematics approach. Finally, methods of tropical optimization are applied to solve unconstrained and constrained minimax single-facility location problems with Chebyshev and rectilinear distances (Krivulin 2011a, b, 2012; Krivulin and Zimmermann 2013; Krivulin 2014; Krivulin and Plotnikov 2015).
The aim of this paper is twofold: first, to develop new applications of tropical optimization by solving new location problems, and second, to offer new closed-form solutions to rather general problems that are of interest to location analysis. We consider a constrained minimax single-facility location problem with addends on the plane with rectilinear distance, which can be referred to as a constrained Rawls location problem or a constrained messenger boy problem. The solution commences with the representation of the problem, first formulated in a standard form, in terms of tropical mathematics as a constrained optimization problem. We use a transformation technique, which can act as a template to handle optimization problems in other application areas, and hence is of independent interest. To solve the constrained optimization problem, we apply methods and results of tropical optimization (Krivulin 2014, 2015a, b, 2017), which provide direct, explicit solutions of the problem and of its special cases with reduced sets of constraints. We further develop the methods to extend the solution of the unconstrained problem provided by Krivulin (2011b), and Krivulin and Plotnikov (2015) to the constrained problems of interest. The results are obtained in a closed form, ready for immediate computation, and can serve to complement and supplement known solutions of the location problems under examination. To illustrate application of the results, we describe a direct solution to the problem of optimal location of the central monitoring facility in an indoor closed-circuit television (CCTV) video surveillance system in a multi-floor building environment.
The rest of the paper is organized as follows. We begin with Sect. 2, where the location problem of interest is formulated in a standard way. Section 3 includes an overview of the definitions and notation of idempotent algebra to be used in the subsequent sections. In Sect. 4, we consider several tropical optimization problems and describe their solutions. Section 5 offers the main result of the paper. First, we represent the location problem under consideration as a constrained tropical optimization problem, and then solve this optimization problem using the results of the previous section. As a consequence, solutions are obtained to some special cases of the problem with reduced sets of constraints. We use the results given in terms of tropical mathematics to derive solutions of the location problems in the standard form. In Sect. 6, we present numerical examples and offer graphical illustrations. We conclude with an application to an optimal location problem, arising in the deployment of an indoor CCTV video surveillance system, in Sect. 7, and make some final observations and comments in Sect. 8.
2 Constrained minimax rectilinear single-facility location problem
We start with a brief outline of the optimization problem, which is drawn from location analysis to motivate the present study. A comprehensive overview of various location problems, their solutions and application examples is provided by a series of surveys published at different times, including Francis et al. (1983), Brandeau and Chiu (1989), ReVelle and Eiselt (2005), Brimberg and Wesolowsky (2009), and Chhajed et al. (2013). Further details can be found in monographs and collections of studies, such as recent books by Sule (2001), Klamroth (2002), Farahani and Hekmatfar (2009), Eiselt and Marianov (2011), and Laporte et al. (2015).
We consider a quite general problem to locate a new point (a facility center) on the plane to minimize the maximum of rectilinear distances to given points (demand centers), each of which can be modified by adding a constant called the addend. The optimal location is subject to constraints that impose upper bounds on distances from each given point to the new point, and define a strip-shaped feasible location region.
The rectilinear metric (also known as the rectangular, Manhattan, right-angle, city-block, taxicab or \(L_{1}\) metric) arises in location analysis in various applied contexts. Examples include locating a public or commercial facility in an urban area with a grid of rectangular streets, an industrial facility within a plant or warehouse with a system of perpendicular transport aisles, and an electronic component on an integrated circuit with orthogonal mesh of wires. The addends can represent an additional cost or distance required to reach each demand point, such as vertical distance when the rectilinear metric is defined on the horizontal plane.
Constrained minimax location problems appear in a range of application areas from urban planning to industrial and electrical engineering. A typical example is the optimal location of emergency service facilities (hospitals, police and fire stations, emergency shelters) in urban design, under constraints on the travel distances prescribed by emergency service standards and rules set by federal, state or municipal agencies. Since the minimax objectives in locating public facilities can well be interpreted in the framework of the theory of justice of John Rawls, these problems are frequently referred to as the Rawls location problems (Hansen et al. 1981; Hansen and Thisse 1981). In addition, minimax single-facility location problems with and without addends are sometimes called the messenger boy problems and the delivery boy problems, respectively (Elzinga and Hearn 1972).
We now represent the location problem under study in a formal way. First note that the rectilinear distance between vectors \(\varvec{a}=(a_{1},a_{2})^{T}\) and \(\varvec{b}=(b_{1},b_{2})^{T}\) in the real plane \(\mathbb {R}^{2}\) is calculated as
Suppose there is a set of \(m\ge 1\) given points, denoted by \(\varvec{r}_{j}=(r_{1j},r_{2j})^{T}\in \mathbb {R}^{2}\) for all \(j=1,\ldots ,m\). Let \(w_{j}\in \mathbb {R}\) be the addend, associated with point j, and \(d_{j}\in \mathbb {R}\), where \(d_{j}\ge 0\), be the upper bound on the distance to point j. Let \(s,t\in \mathbb {R}\), where \(s\le t\), be the left and right boundary of the vertical strip, representing the feasible location area.
Then, the problem of interest, which can be referred to as the constrained minimax rectilinear single-facility location problem with addends, is formulated to find points \(\varvec{x}=(x_{1},x_{2})^{T}\in \mathbb {R}^{2}\) that
After rewriting the rectilinear distance \(\rho \) in coordinate form, the problem becomes
Consider the constraints in the problem. For each \(j=1,\ldots ,m\), the inequality \(|x_{1}-r_{1j}|+|x_{2}-r_{2j}|\le d_{j}\) defines on the plane a square rotated by \(45^{\circ }\) around its center at the point \(\varvec{r}_{j}=(r_{1j},r_{2j})^{T}\), which is often called the diamond. The common area of all inequalities, if it exists, takes the form of a rectangle tilted \(45^{\circ }\) to the axes. The feasible location region is the intersection of this rectangle with the strip area given by the inequality \(s\le x_{1}\le t\), provided that the intersection is not empty.
Both special cases and extensions of the rectilinear single-facility location problem are thoroughly examined in the literature. For some unconstrained versions of the problem, direct solutions are obtained in a closed form, whereas, in other cases, the problems have solutions given by iterative computational algorithms, which find a solution, if it exists, or indicate that there are no solutions. Specifically, the unconstrained problem is considered without addends in Francis (1972), Elzinga and Hearn (1972), and with addends in Elzinga and Hearn (1972), where closed-form solutions are derived based on geometric arguments.
An algorithmic solution is proposed by Dearing (1972) for a weighted extension of the problem, in which the distances appear in the objective function with non-negative weights, and for a weighted multi-facility problem. A weighted multi-facility problem without constraints is solved by means of linear programming computational schemes in Wesolowsky (1972), and Elzinga and Hearn (1973), whereas the constrained problem is by a network flow algorithm in Dearing and Francis (1974). An interactive computer graphical technique is developed in Brady and Rosenthal (1980) to solve single-facility location problems with non-convex feasible regions.
An algebraic approach, which uses results of tropical optimization, is applied in Krivulin (2011b), and Krivulin and Plotnikov (2015) to the problem under consideration when all constraints are removed. The approach offers a direct, explicit solution based on a straightforward algebraic technique, rather than on geometric considerations in the classical works (Francis 1972; Elzinga and Hearn 1972).
Below, we further develop the algebraic approach to extend methods of tropical optimization to the constrained location problem with rectilinear distance. Based on this approach, we derive closed-form solutions for the location problem of interest, as well as for its special cases with reduced sets of constraints. To the best of our knowledge, no direct solutions to the location problem have been previously reported.
To handle the problem, we first transform it into a tropical optimization problem examined in Krivulin (2014) in the context of constrained location with Chebyshev distances (\(L_{\infty }\) metric) to exploit the complete solution derived therein. Note that, from the geometrical point of view, the location problems on the plane with rectilinear and Chebyshev distances are known to convert into each other by rotation of the coordinate axes (see, e.g. Farahani and Hekmatfar 2009), which can serve as additional intuition and evidence in support of the algebraic technique proposed for the transformation. Next, we further develop and refine obtained results to provide complete solutions of the location problems of interest, which are then represented both in terms of tropical mathematics and in the conventional form.
To conclude this section, we observe that it is not difficult to represent the problem under study as a linear program, and then to solve it using methods and computational techniques of linear programming. However, these methods normally offer algorithmic solutions, and do not guarantee a direct solution in a closed form.
3 Preliminary algebraic definitions and notation
We now present a concise overview of the definitions and notation of idempotent algebra from Krivulin (2014, 2015a, b, 2017), which provide the basis for the description of the tropical optimization problems and their solutions in the next section, and for the use of these solutions to attack location problems in the subsequent sections. Further details on tropical mathematics are available in various introductory and advanced texts, including Golan (2003), Heidergott et al. (2006), McEneaney (2006), Itenberg et al. (2007), Gondran and Minoux (2008), and Maclagan and Sturmfels (2015) to name only a few recent publications.
3.1 Idempotent semifield
Let \(\mathbb {X}\) be a non-empty set that is closed under two associative and commutative operations, addition \(\oplus \) and multiplication \(\otimes \), and equipped with two distinct elements, zero \({\mathbb {0}}\) and one \({\mathbb {1}}\), which are neutral with respect to addition and multiplication. Addition is idempotent, which indicates that the equality \(x\oplus x=x\) holds for each \(x\in \mathbb {X}\). Multiplication is distributive over addition, and invertible, which provides each \(x\ne \mathbb {0}\) with an inverse \(x^{-1}\) such that \(x\otimes x^{-1}=\mathbb {1}\). Under these assumptions, the algebraic system \((\mathbb {X},\mathbb {0},\mathbb {1},\oplus ,\otimes )\) is frequently called the idempotent semifield.
Idempotent addition provides a partial order on \(\mathbb {X}\) to define \(x\le y\) if and only if \(x\oplus y=y\). It follows from the definition of the order relation that the operations in the semifield have the following properties. First, the inequality \(x\oplus y\le z\) is equivalent to the two inequalities \(x\le z\) and \(y\le z\) for any \(x,y,z\in \mathbb {X}\). Furthermore, both addition and multiplication are isotone, which implies that the inequality \(x\le y\) results in the inequalities \(x\oplus z\le y\oplus z\) and \(x\otimes z\le y\otimes z\). Finally, inversion is antitone, which means that \(x\le y\) yields \(x^{-1}\ge y^{-1}\), provided that \(x\ne {\mathbb {0}}\) and \(y\ne {\mathbb {0}}\). In addition, the set \(\mathbb {X}\) is assumed totally ordered by a linear order relation that is consistent with the partial order associated with addition.
As usual, the multiplication sign \(\otimes \) is omitted below to safe writing. The integer power notation serves to signify iterated products, defined as \(x^{0}=\mathbb {1}\), \(x^{p}=xx^{p-1}\), \(x^{-p}=(x^{-1})^{p}\) and \(\mathbb {0}^{p}=\mathbb {0}\) for all \(x\ne \mathbb {0}\) and integer \(p>0\). The power notation is assumed extendable to allow rational and real exponents.
A representative example of the idempotent semifield under consideration is the real semifield \(\mathbb {R}_{\max ,+}=(\mathbb {R}\cup \{-\infty \},-\infty ,0,\max ,+)\), where addition is defined as the operation of taking the maximum and multiplication is as the arithmetic addition, whereas the zero is given by \(-\infty \) and the one is by 0. For each \(x\in \mathbb {R}\), there exists the inverse \(x^{-1}\), which coincides with \(-x\) in conventional algebra. The power \(x^{y}\) acts as the arithmetic product xy defined for any \(x,y\in \mathbb {R}\). The partial order, which is given by addition, conforms to the standard linear order defined on \(\mathbb {R}\). Finally, the obvious equality \(\min (x,y)=-\max (-x,-y)\) yields \(\min (x,y)=(x^{-1}\oplus y^{-1})^{-1}\) for all \(x,y\in \mathbb {R}\).
As another example, consider the semifield \(\mathbb {R}_{\min ,\times }=(\mathbb {R}_{+}\cup \{+\infty \},+\infty ,1,\min ,\times )\), where \(\mathbb {R}_{+}\) is the set of positive reals. This semifield has \(\oplus =\min \), \(\otimes =\times \), \(\mathbb {0}=+\infty \) and \(\mathbb {1}=1\). Both inversion and exponentiation have standard interpretation. The partial order induced by idempotent addition is opposite to the natural order on \(\mathbb {R}\).
3.2 Vector and matrix algebra
The scalar addition \(\oplus \) and multiplication \(\otimes \) defined on \(\mathbb {X}\) are routinely extended to vector and matrix operations. The set of matrices with m rows and n columns over \(\mathbb {X}\) is denoted \(\mathbb {X}^{m\times n}\). Addition and multiplication of matrices, and multiplication by scalars follow the standard rules. For any matrices \(\varvec{A}=(a_{ij})\in \mathbb {X}^{m\times n}\), \(\varvec{B}=(b_{ij})\in \mathbb {X}^{m\times n}\) and \(\varvec{C}=(c_{ij})\in \mathbb {X}^{n\times l}\), and a scalar \(x\in \mathbb {X}\), the matrix operations are defined by the entry-wise formulae
The partial order relation and its associated properties of the operations in \(\mathbb {X}\) extend entry-wise to the matrix operations.
Consider square matrices of order n, which form the set \(\mathbb {X}^{n\times n}\). A matrix whose diagonal entries are all equal to \(\mathbb {1}\), and off-diagonal entries are to \(\mathbb {0}\) is the identity matrix denoted by \(\varvec{I}\). The power notation is defined as \(\varvec{A}^{0}=\varvec{I}\), \(\varvec{A}^{p}=\varvec{A}\varvec{A}^{p-1}\) for any square matrix \(\varvec{A}\) and integer \(p>0\) to indicate repeated multiplication.
The trace of a matrix \(\varvec{A}=(a_{ij})\in \mathbb {X}^{n\times n}\) is calculated as \(\mathrm {tr}\varvec{A}=a_{11}\oplus \cdots \oplus a_{nn}\). The traces of matrix powers from 1 to n combine together to define the scalar
Provided that \(\mathrm {Tr}(\varvec{A})\le \mathbb {1}\), the asterate operator (also known as the Kleene star) maps the matrix \(\varvec{A}\) to the matrix
Any matrix that consists of one row (column) specifies a row (column) vector. All vectors below are assumed column vectors unless otherwise specified. The set of all column vectors with n elements over \(\mathbb {X}\) is denoted \(\mathbb {X}^{n}\).
A vector with all elements equal to \(\mathbb {0}\) is the zero vector. Any vector without zero elements is called regular. For any vectors \(\varvec{a}=(a_{i})\) and \(\varvec{b}=(b_{i})\) in \(\mathbb {X}^{n}\), and a scalar \(x\in \mathbb {X}\), the vector addition and scalar multiplication are given by
For any nonzero vector \(\varvec{a}=(a_{i})\in \mathbb {X}^{n}\), the multiplicative conjugate transpose is a row vector \(\varvec{a}^{-}=(a_{i}^{-})\) that has elements \(a_{i}^{-}=a_{i}^{-1}\) if \(a_{i}\ne \mathbb {0}\), and \(a_{i}^{-}=\mathbb {0}\) otherwise.
The conjugate transposition is antitone in the sense that, if regular vectors \(\varvec{a}\) and \(\varvec{b}\) satisfy the element-wise inequality \(\varvec{a}\le \varvec{b}\), then \(\varvec{a}^{-}\ge \varvec{b}^{-}\). In addition, the transposition has the following properties. For any nonzero vector \(\varvec{a}\), the equality \(\varvec{a}^{-}\varvec{a}=\mathbb {1}\) holds. If the vector \(\varvec{a}\) is regular, then the entry-wise inequality \(\varvec{a}\varvec{a}^{-}\ge \varvec{I}\) is also valid.
4 Tropical optimization problems
In this section, we use idempotent algebra to formulate optimization problems and to describe their solutions. The problems find applications in various fields, including location analysis. Specifically, such problems occur in solving unconstrained and constrained single-facility location problems in the multidimensional space with Chebyshev distance (Krivulin 2012, 2014; Krivulin and Zimmermann 2013).
In the succeeding sections, we extend the solutions presented here to constrained single-facility location problems defined on the plane with rectilinear metric.
We start with a general constrained optimization problem formulated in terms of an arbitrary idempotent semifield. Suppose that, given vectors \(\varvec{p},\varvec{q},\varvec{g},\varvec{h}\in \mathbb {X}^{n}\), and a matrix \(\varvec{B}\in \mathbb {X}^{n\times n}\), the problem is to find all regular vectors \(\varvec{x}\in \mathbb {X}^{n}\) that
The solution of the problem, given in Krivulin (2014), involves the introduction of a parameter to represent the minimum value of the objective function. Then, the problem reduces to solving a parametrized system of linear inequalities. The existence conditions of regular solutions for the system serve to evaluate the parameter, whereas the solution of the system is taken as a complete solution to the initial optimization problem. The results obtained take the form of the following statement.
Theorem 1
Let \(\varvec{B}\) be a matrix with \(\mathrm {Tr}(\varvec{B})\le \mathbb {1}\), \(\varvec{p}\) be a nonzero vector, \(\varvec{q}\) and \(\varvec{h}\) be regular vectors, and \(\varvec{g}\) be a vector such that \(\varvec{h}^{-}\varvec{B}^{*}\varvec{g}\le \mathbb {1}\).
Then, the minimum value in problem (1) is equal to
and all regular solutions of the problem are given by
where \(\varvec{u}\) is any regular vector such that
The conditions of the theorem have the following meaning. The requirement of a regular vector \(\varvec{h}\) is a necessary condition that allows regular solutions of the inequality \(\varvec{g}\le \varvec{x}\le \varvec{h}\). The condition \(\mathrm {Tr}(\varvec{B})\le \mathbb {1}\) is necessary and sufficient to have a set of regular solutions to the inequality \(\varvec{B}\varvec{x}\le \varvec{x}\), whereas \(\varvec{h}^{-}\varvec{B}^{*}\varvec{g}\le \mathbb {1}\) is for a non-empty intersection of this solution set with the set defined by the constraints \(\varvec{g}\le \varvec{x}\le \varvec{h}\).
The assumptions of a non-zero vector \(\varvec{p}\) and a regular vector \(\varvec{q}\) are sufficient to keep the minimum value \(\theta >\mathbb {0}\), which allows the inverse \(\theta ^{-1}\) to exist. These two assumptions can be replaced by a list of weaker conditions, which is, however, insufficient for application to the location problems under consideration.
Consider two consequences of the theorem, which solve problem (1) when one of the inequality constraints is eliminated. First, we exclude the double inequality to write the problem
The general solution, which is offered by Theorem 1, takes the form of the next result (see, also Krivulin 2012).
Corollary 1
Let \(\varvec{B}\) be a matrix with \(\mathrm {Tr}(\varvec{B})\le \mathbb {1}\), \(\varvec{p}\) be a non-zero vector, and \(\varvec{q}\) be a regular vector. Then, the minimum value in problem (4) is equal to
and all regular solutions are given by
Furthermore, we consider another special case of the constrained problem at (1), formulated to
A solution goes as follows (see, also Krivulin and Zimmermann 2013).
Corollary 2
Let \(\varvec{p}\) be a non-zero vector, \(\varvec{q}\) and \(\varvec{h}\) be regular vectors, and \(\varvec{g}\) be a vector such that \(\varvec{g}\le \varvec{h}\). Then, the minimum value in problem (5) is equal to
and all regular solutions of the problem are given by the condition
Finally, we present a solution to the unconstrained problem (Krivulin 2012)
Corollary 3
Let \(\varvec{p}\) be a non-zero vector, and \(\varvec{q}\) be a regular vector. Then, the minimum value in problem (6) is equal to
and all regular solutions are given by
Below we show how to apply the results of tropical optimization in this section to solve the constrained rectilinear single-facility location problem under study.
5 Transformation and solution of location problem
We are now in a position to turn back to the location problem formulated above. The solution begins with the representation of the problem in terms of tropical mathematics. We apply a useful transformation technique, which can serve as a template to handle other optimization problems, and hence is of independent interest. Furthermore, we derive, in the framework of tropical optimization, a direct solution to the problem in the general setting, and then present solutions to special cases of the problem, where some or all of constraints are removed. The section concludes with direct representation of the solutions in terms of the conventional algebra.
5.1 Representation in terms of tropical optimization
We start with the general constrained location problem, which is formulated to find all vectors \(\varvec{x}=(x_{1},x_{2})^{T}\in \mathbb {R}^{2}\) that
where \(\varvec{r}_{j}=(r_{1j},r_{2j})^{T}\in \mathbb {R}^{2}\) are given vectors and \(d_{j},w_{j}\in \mathbb {R}\) with \(d_{j}\ge 0\) are given numbers for all \(j=1,\ldots ,m\), and \(s,t\in \mathbb {R}\) are given numbers such that \(s\le t\).
To solve problem (7), we represent it in terms of the semifield \(\mathbb {R}_{\max ,+}\) with the maximum in the role of addition and the arithmetic addition in the role of multiplication. Clearly, the context of location analysis guarantees the regularity, in terms of \(\mathbb {R}_{\max ,+}\), of all vectors involved in the problem setting.
First, we note that the rectilinear distance between two vectors \(\varvec{a}=(a_{1},a_{2})^{T}\) and \(\varvec{b}=(b_{1},b_{2})^{T}\) in terms of the operations in the semifield \(\mathbb {R}_{\max ,+}\) takes the form
Consider the distance between the points \(\varvec{x}\) and \(r_{j}\) for each \(j=1,\ldots ,m\). An application of the above formula and simple algebra give
To represent this distance in a compact vector form, we introduce the vectors \(\varvec{y}=(y_{1},y_{2})^{T}\) and \(\varvec{c}_{j}=(c_{1j},c_{2j})^{T}\) for all \(j=1,\ldots ,m\), with elements
It is not difficult to see that the elements of the vector \(\varvec{x}\) are uniquely determined by those of \(\varvec{y}\) through the equalities
Note that the above relations between \(x_{1},x_{2}\) and \(y_{1},y_{2}\) directly correspond to the obvious linear transformations, which are associated in the conventional arithmetic with the interchange between Chebyshev and rectilinear distances.
With the new vector notation, the distance between \(\varvec{x}\) and \(r_{j}\) becomes
We are now in a position to rewrite the objective function in problem (7) by using vectors \(\varvec{p}=(p_{1},p_{2})^{T}\) and \(\varvec{q}=(q_{1},q_{2})^{T}\) as follows:
where the right-hand side is obtained by regrouping terms and substitution
Furthermore, we examine the inequality constraints in (7). The constraints, which involve the distance between vectors, take the form of the inequalities
Note that each inequality is equivalent to the pair of inequalities \(\varvec{y}^{-}\varvec{c}_{j}\le d_{j}\) and \(\varvec{c}_{j}^{-}\varvec{y}\le d_{j}\). Consider the first inequality \(\varvec{y}^{-}\varvec{c}_{j}\le d_{j}\) and verify, using the properties of conjugate transposition, that it is equivalent to the inequality \(\varvec{c}_{j}\le d_{j}\varvec{y}\). Indeed, multiplication of the former inequality by \(\varvec{y}\) from the left gives \(\varvec{c}_{j}\le \varvec{y}\varvec{y}^{-}\varvec{c}_{j}\le d_{j}\varvec{y}\), whereas the left multiplication of the latter inequality by \(\varvec{y}^{-}\) results in the former one. The inequality \(\varvec{c}_{j}^{-}\varvec{y}\le d_{j}\) is equivalent to \(\varvec{y}\le d_{j}\varvec{c}_{j}\) by similar arguments.
Then, after slight rearrangement of the inequalities obtained, we represent the inequality constraints under consideration in the alternative form
These inequalities combine to produce the two equivalent inequalities
Finally, we replace the last inequalities by the one double inequality
where we use the vector notation \(\varvec{g}=(g_{1},g_{2})^{T}\) and \(\varvec{h}=(h_{1},h_{2})^{T}\), defined by
It remains to represent, in terms of the new vector \(\varvec{y}\), the last inequality constraint
We rewrite the left and right inequalities as \(s^{2}x_{1}^{-1}\le x_{1}\) and \(t^{-2}x_{1}\le x_{1}^{-1}\), or equivalently, as the inequalities \(s^{2}x_{1}^{-1}x_{2}\le x_{1}x_{2}\) and \(t^{-2}x_{1}x_{2}\le x_{1}^{-1}x_{2}\).
After substitution \(y_{1}=x_{1}x_{2}\) and \(y_{2}=x_{1}^{-1}x_{2}\), we have the inequalities \(s^{2}y_{2}\le y_{1}\) and \(t^{-2}y_{1}\le y_{2}\). In vector form, these inequalities are given by
where the matrix \(\varvec{B}\) is defined, using the notation \(\mathbb {0}=-\infty \), as follows:
Finally, location problem (7) reduces to the tropical optimization problem
which coincides with that of (1), where the unknown vector \(\varvec{x}\) is replaced by \(\varvec{y}\).
5.2 Derivation of direct solution
We now apply Theorem 1 to derive a direct solution to problem (8). To describe the results, we need to calculate the matrices
The description also involves a direct representation for the elements of the vectors \(\varvec{p}=(p_{1},p_{2})^{T}\), \(\varvec{q}=(q_{1},q_{2})^{T}\), \(\varvec{g}=(g_{1},g_{2})^{T}\) and \(\varvec{h}=(h_{1},h_{2})^{T}\), given by
where \(i=1,2\), and \(c_{1j}=r_{1j}r_{2j}\) and \(c_{2j}=r_{1j}^{-1}r_{2j}\) for all \(j=1,\ldots ,m\).
We start with calculating, as intermediate results, the row vectors
To represent the existence conditions imposed and the minimum value provided by the theorem, we find
According to Theorem 1, the conditions for problem (8) to have solutions are specified by the inequalities
Since \(\mathrm {Tr}(\varvec{B})=\mathrm {tr}\varvec{B}\oplus \mathrm {tr}\varvec{B}^{2}=s^{2}t^{-2}\le \mathbb {1}\) if \(s\le t\), the first inequality is obviously valid. The second condition takes the form of the inequality
An application of (2) to write the minimum value of the objective function yields
We now describe the solution set of vectors \(\varvec{y}=(y_{1},y_{2})^{T}\). It follows from Theorem 1 that problem (8) has the solution
where the intermediate vector \(\varvec{u}=(u_{1},u_{2})^{T}\) satisfies the condition at (3).
First, we represent the above vector equality in scalar form as
To describe the set of admissible vectors \(\varvec{u}\), we take the double inequality at (3) to consider the corresponding scalar inequalities
It is not difficult to verify that at least one of these inequalities holds as an equality. To see this, we can substitute for \(\theta \) each term on the right-hand side of (11). Consider, for instance, the case that \(\theta =q_{1}^{-1/2}p_{1}^{1/2}\). Under this assumption, we have
which means that both left and right parts of the first inequality coincide, and thus this inequality reduces to an equality. The other cases are examined in the same way.
Taking into account that one of the above inequalities acts as an equality, we rewrite them in the one-parametrized form
where \(\alpha \) is a real parameter such that \(0\le \alpha \le 1\).
Finally, note that the solution of the initial problem (7) in terms of the vector \(\varvec{x}=(x_{1},x_{2})^{T}\) can be calculated from the elements of the vector \(\varvec{y}\) as follows:
5.3 Direct solutions to location problems
In this subsection, we turn back to the conventional notation and summarize the result obtained to provide direct, explicit solutions of the general location problem and of its special cases. Consider the general problem formulated in the scalar form
After translating the formulae at (9), (10), (11), (12), (13) and (14) back into the language of conventional algebra, with eliminating both \(y_{1}\) and \(y_{2}\), the results of the previous subsection are summarized as follows.
Theorem 2
Define the notation
and suppose that
Then, the minimum value in problem (15) is equal to
and all solutions are given by
where
for all real \(\alpha \) such that \(0\le \alpha \le 1\).
As a consequence of the theorem, which also takes into account Corollaries 1, 2 and 3, we present solutions to special cases of the problem with reduced sets of constraints and without constraints. Consider the problem, which has only the upper-bound distance constraints. In ordinary notation, the problem is defined as follows:
The next statement offers a direct, explicit solution to the problem.
Corollary 4
Under the notation of Theorem 2, suppose that
Then, the minimum value in problem (20) is equal to
and all solutions are given by
where
for all real \(\alpha \) such that \(0\le \alpha \le 1\).
Furthermore, we examine the problem with the boundary constraints in the form
Corollary 5
Under the notation of Theorem 2, the minimum value in problem (21) is equal to
and all solutions are given by
where
for all real \(\alpha \) such that \(0\le \alpha \le 1\).
Finally, we consider the unconstrained problem
A solution to the problem is described as follows.
Corollary 6
Under the notation of Theorem 2, the minimum value in problem (22) is equal to
and all solutions are given by
where
for all real \(\alpha \) such that \(0\le \alpha \le 1\).
Note that, after elimination of the intermediate variables \(u_{1}\) and \(u_{2}\), the solution to the unconstrained problem becomes
which agrees with that derived by geometric (Elzinga and Hearn 1972; Francis 1972) and algebraic (Krivulin 2011b; Krivulin and Plotnikov 2015) techniques.
6 Numerical examples and graphical illustrations
We illustrate the results obtained with small artificial examples of optimal location of a facility with respect to \(m=3\) given points. The purpose of the illustration is to provide a clear demonstration of the computational technique used, and a transparent graphical representation of the solutions offered. Although the problems under consideration involve only three given points, the examples show strong evidence of the applicability of the method to solve efficiently real-world problems of large scale.
Consider the problem of locating a new point on the plane to minimize the maximum of distances from this point to three given points defined as
The values of addends corresponding to these points are assumed to be
whereas the upper bounds on the distances are to be
Finally, the left and right boundary of the feasible location region are given by
To describe the solutions to the problem under various constraints, we first calculate the numbers
We start with problem (22) without constraints. According to Corollary 6, we find the minimum
Next, we calculate the intermediate variables
and finally obtain the solution in the parametrized form
where \(\alpha \) is any real number such that \(0\le \alpha \le 1\).
Substitutions \(\alpha =0\) and \(\alpha =1\) give two points
which define the ends of the line segment representing the solutions.
The solution to the unconstrained problem is illustrated in Fig. 1 (left). The illustration shows the given points \(\varvec{r}_{1}\), \(\varvec{r}_{2}\) and \(\varvec{r}_{3}\), indicated by filled circles. For each point \(\varvec{r}_{j}\), the four open circles placed distance \(w_{j}>0\) from the filled circle designate artificial points to account for the addends. The representation of the solution involves the minimal \(45^{\circ }\)-tilted rectangle enclosing all artificial points. The solution set is given by the thick line segment, which goes through the centers of the long sides between two horizontal lines drawn through the bottom-left and top-right vertices of the rectangle.
Suppose now that the boundary constraints \(s\le x_{1}\le t\) are imposed, where \(s=4\) and \(t=8\). To solve the problem under these constraints, we apply Corollary 5.
First, we find that the minimum in the problem
remains the same value as for the unconstrained problem examined above.
Furthermore, we calculate the intermediates
and then obtain the solution given by
The solution set forms a line segment with the extreme points, which answer \(\alpha =0\) and \(\alpha =1\) to be
The solution is shown in Fig. 1 (right), where the feasible region is represented as the strip area between two vertical lines at \(x_{1}=s\) and \(x_{1}=t\).
Consider the problem, in which the upper-bounds \(d_{j}\) on the distances between the new and given points are used instead of boundary constraints examined above. To apply Corollary 4, we verify the condition
It follows from the corollary that the minimum in the problem now becomes
Furthermore, we calculate
The solution is written as
and constitutes a line segment having the ends at the points
A graphical illustration of the solution is provided in Fig. 2 (left). The plot demonstrates the feasible location area as the intersection of turned squares drawn for each point \(\varvec{r}_{j}\) to have the distance from the vertices of the square to the point equal to \(d_{j}\). A thick line segment that coincides with the lower long side of the small turned rectangle, which represents the feasible area, shows the solution.
We conclude this section with the solution to the general location problem, which combines both boundary and upper-bound distance constraints. By following the solution offered by Theorem 2, we begin with the validation of the condition
The evaluation of the minimum value yields
After calculation of the intermediate expressions
we obtain the solution given by
The solution to the problem is depicted in Fig. 2 (right) by the thick line segment between the points
which correspond to setting \(\alpha =0\) and \(\alpha =1\).
7 Application to CCTV monitoring facility location
In this section, we present an application to a real-world problem that arises in the deployment of CCTV video surveillance systems in the indoor environment, including office, industrial, commercial, educational, social, health-care and other buildings.
A typical CCTV system is composed of three major components (Cieszynski 2004; Cohen et al. 2009; SPAWAR Systems Center Atlantic 2013): imaging sensors (video cameras) generating an input video stream, a transmission system to transmit video signal data, and a central video monitoring/processing facility. The design and deployment of CCTV systems in the indoor environment give rise to a range of location problems. Specifically, the problems of camera placement consist in finding optimal locations of cameras in a surveillance zone under various operational objectives and constraints, such as to maximize the coverage area subject to a fixed number of available cameras (see, e.g., overviews in Zhao et al. 2013; Liu et al. 2016). Below, we examine a different problem with the assumption that the placement of cameras in a CCTV system is already fixed and the problem is to determine the optimal location of the central monitoring facility to reduce losses in the wired transmission network of the system under some technological constraints.
We consider the CCTV video surveillance system, which is set up in a multi-floor building that is composed by rectangular shapes, with rectangular rooms and corridors at each floor, as illustrated by the scheme in Fig. 3. The intra-building conduit system consists of vertical riser shafts, horizontal cable trays, ladder racks and other facilities to provide full connectivity between any points in the building through the paths, which are parallel or perpendicular to the walls and to the ceiling. Rooms on all floors are equipped with surveillance cameras mounted at upper corners, where two walls and the ceiling meet at a right angle. To transmit video data, every camera is directly connected by a coaxial cable using intra-building cable runs to a central control viewing room, located in a dedicated area on the ground floor, which accommodates monitoring, data storage and video analytics facilities. In the scheme in Fig. 3, the feasible location region is surrounded by hatched border.
The use of coaxial wires imposes constraints on the maximum cable distance, which ranges, depending on the gauge of the cable, from several tens to a few hundreds of metres (Cohen et al. 2009; SPAWAR Systems Center Atlantic 2013). Another critical issue is the increasing attenuation (loss) of video signal as the transmission distance and frequency increase, which makes it difficult to handle video data, especially when transmitting high-quality video. Since the length of the wire between each camera and the control room depends on where the room is located, the attenuation is reduced by appropriate room location. Considering that the signal attenuation is measured proportional to the transmission distance, the attenuation can be identified with the distance to formulate the following minimax problem.
For a given placement of m surveillance cameras in a multi-floor building environment, we need to find the optimal location of the central monitoring facility (the control room) in a feasible area on the ground floor to minimize the maximum attenuation in the wired transmission network subject to maximum distance constraints on the wires between cameras and the facility. As it is easy to see, the problem takes the form of (15) and, therefore, has the direct solution provided by Theorem 2.
The procedure offered by the theorem involves simple straightforward calculations using the horizontal coordinates \((r_{1j},r_{2j})\) and the vertical height \(w_{j}\) of all cameras \(j=1,\ldots ,m\). Given a common distance constraint d on the wire length, the individual constraint for camera j is calculated as \(d_{j}=d-w_{j}\). The most computationally intensive part of the procedure is the evaluation of the intermediate variables \(p_{i}\), \(q_{i}\), \(g_{i}\) and \(h_{i}\) for \(i=1,2\) according to (16), which takes at most linear time with respect to the number of cameras. The condition (17) is verified to ensure that the distance bounds \(d_{j}\) and the location bounds s and t can be simultaneously satisfied to provide non-empty feasible location region. The procedure completes with the evaluation of the optimal distance \(\theta \) using (18) and the derivation of parametrized representation for the coordinates \((x_{1},x_{2})\) of the optimal location zone in the form of (19).
Solutions to the central monitoring facility location problem are then obtained by plotting the optimal location area, which typically takes the form of a line segment (depicted in Fig. 3 by a thick dashed line), on the ground floor map to determine an appropriate place to deploy the facility and to develop the transmission network.
8 Conclusions
In this paper, we used tropical mathematics to derive new solutions to constrained minimax single-facility location problems with addends on the plane with rectilinear distance. Tropical mathematics, which deals with the theory and application of algebraic systems with idempotent addition, offers a useful problem formulation and solution framework to provide direct, explicit solutions to a range of classical and novel problems in operations research, management science and other fields.
To handle the location problems under study, we have formulated these problems in the tropical mathematics setting, and then solved them by applying recent results in tropical optimization. In contrast to the known solution approaches that are mainly based on numerical iterative algorithms, including linear programming and graph optimization, the solutions obtained are given in a simple closed form, which is ready for both further analysis by analytical techniques and straightforward computation with no more than a linear computational cost. As the solution method for the location problems, we have proposed an explicit computational technique that involves easy direct computations, and may help to augment and supersede known approaches when indirect algorithmic solutions are less preferred or even impossible.
Future research will focus on the solution of the problem with additional constraints to define a more general feasible location area on the plane. Extensions of the approach to solve other minimax location problems, including rectilinear problems in three-dimensional space and multi-facility location problems, are also of interest.
References
Brady SD, Rosenthal RE (1980) Interactive computer graphical solutions of constrained minimax location problems. AIIE Trans 12(3):241–248. doi:10.1080/05695558008974512
Brandeau ML, Chiu SS (1989) An overview of representative problems in location research. Manag Sci 35(6):645–674. doi:10.1287/mnsc.35.6.645
Brimberg J, Wesolowsky GO (2009) Optimizing facility location with Euclidean and rectilinear distances. In: Floudas CA, Pardalos PM (eds) Encyclopedia of optimization. Springer, Berlin, pp 2869–2873. doi:10.1007/978-0-387-74759-0_491
Chhajed D, Francis RL, Lowe TJ (2013) Facility location. In: Gass SI, MC Fu (eds) Encyclopedia of operations research and management science. Springer, Berlin, pp 546–549. doi:10.1007/978-1-4419-1153-7_327
Cieszynski J (2004) Closed circuit television, 2nd edn. Newnes, Oxford. doi:10.1016/B978-0-08-054573-8.50001-4
Cohen N, Gattuso J, Maclennan-Brown K (2009) CCTV operational requirements manual 2009. Home Office Scientific Development Branch, St. Albans
Cuninghame-Green RA (1991) Minimax algebra and applications. Fuzzy Sets Syst 41(3):251–267. doi:10.1016/0165-0114(91)90130-I
Cuninghame-Green RA (1994) Minimax algebra and applications. In: Hawkes PW (ed) Advances in imaging and electron physics, Advances in imaging and electron physics, vol 90. Academic Press, San Diego, pp 1–121. doi:10.1016/S1076-5670(08)70083-1 CA
Dearing PM (1972) On some minimax location problems using rectilinear distance. Ph.D. thesis, University of Florida, Gainesville, FL
Dearing PM, Francis RL (1974) A network flow solution to a multifacility minimax location problem involving rectilinear distances. Transp Sci 8(2):126–141. doi:10.1287/trsc.8.2.126
Eiselt HA, Marianov V (eds) (2011) Foundations of location analysis, International series in operations research and management science, vol 155. Springer, New York. doi:10.1007/978-1-4419-7572-0
Elzinga J, Hearn DW (1972) Geometrical solutions for some minimax location problems. Transp Sci 6(4):379–394. doi:10.1287/trsc.6.4.379
Elzinga J, Hearn DW (1973) A note on a minimax location problem. Transp Sci 7(1):100–103. doi:10.1287/trsc.7.1.100
Farahani RZ, Hekmatfar M (eds) (2009) Facility location. Contributions to management science, Physica-Verlag, Heidelberg. doi:10.1007/978-3-7908-2151-2
Francis RL (1972) A geometrical solution procedure for a rectilinear distance minimax location problem. AIIE Trans 4(4):328–332. doi:10.1080/05695557208974870
Francis RL, McGinnis LF, White JA (1983) Locational analysis. Eur J Oper Res 12(3):220–252. doi:10.1016/0377-2217(83)90194-7
Golan JS (2003) Semirings and affine equations over them, Mathematics and its applications, vol 556. Kluwer, Dordrecht. doi:10.1007/978-94-017-0383-3
Gondran M, Minoux M (2008) Graphs, dioids and semirings, Operations research/computer science interfaces, vol 41. Springer, New York. doi:10.1007/978-0-387-75450-5
Hansen P, Thisse JF (1981) Outcomes of voting and planning: Condorcet, Weber and Rawls locations. J Public Econom 16(1):1–15. doi:10.1016/0047-2727(81)90039-6
Hansen P, Peeters D, Thisse JF (1981) Constrained location and the Weber-Rawls problem. In: Hansen P (ed) Annals of discrete mathematics (11)—Studies on graphs and discrete programming, vol 59. North-Holland Mathematics Studies, North-Holland, pp 147–166. doi:10.1016/S0304-0208(08)73463-7
Heidergott B, Olsder GJ, van der Woude J (2006) Max plus at work. Princeton series in applied mathematics. Princeton University Press, Princeton
Hudec O, Zimmermann K (1993) A service points location problem with min–max distance optimality criterion. Acta Univ Carolin Math Phys 34(1):105–112
Hudec O, Zimmermann K (1999) Biobjective center—balance graph location model. Optimization 45(1–4):107–115. doi:10.1080/02331939908844429
Itenberg I, Mikhalkin G, Shustin E (2007) Tropical algebraic geometry, Oberwolfach seminars, vol 35. Birkhäuser, Basel. doi:10.1007/978-3-7643-8310-7
Klamroth K (2002) Single-facility location problems with barriers. Springer series in operations research and financial engineering. Springer, New York. doi:10.1007/b98843
Krivulin N (2011a) Algebraic solution to a constrained rectilinear minimax location problem on the plane. In: 2011 International conference on multimedia technology (ICMT), IEEE, pp 6212–6220. doi:10.1109/ICMT.2011.6002526
Krivulin N (2012) A new algebraic solution to multidimensional minimax location problems with Chebyshev distance. WSEAS Trans Math 11(7):605–614
Krivulin N (2014) Complete solution of a constrained tropical optimization problem with application to location analysis. In: Höfner P, Jipsen P, Kahl W, Müller ME (eds) Relational and algebraic methods in computer science, Lecture notes in computer science, vol 8428. Springer, Cham, pp 362–378. doi:10.1007/978-3-319-06251-8_22
Krivulin N (2015a) Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl 468:211–232. doi:10.1016/j.laa.2014.06.044
Krivulin N (2015b) A multidimensional tropical optimization problem with nonlinear objective function and linear constraints. Optimization 64(5):1107–1129. doi:10.1080/02331934.2013.840624
Krivulin N (2017) Direct solution to constrained tropical optimization problems with application to project scheduling. Comput Manag Sci 14(1):91–113. doi:10.1007/s10287-016-0259-0
Krivulin N, Zimmermann K (2013) Direct solutions to tropical optimization problems with nonlinear objective functions and boundary constraints. In: Biolek D, Walter H, Utu I, von Lucken C (eds) Mathematical methods and optimization techniques in engineering. WSEAS Press, Athens, pp 86–91
Krivulin NK (2011b) An extremal property of the eigenvalue for irreducible matrices in idempotent algebra and an algebraic solution to a Rawls location problem. Vestnik St Petersburg Univ Math 44(4):272–281. doi:10.3103/S1063454111040078
Krivulin NK, Plotnikov PV (2015) On an algebraic solution of the Rawls location problem in the plane with rectilinear metric. Vestnik St Petersburg Univ Math 48(2):75–81. doi:10.3103/S1063454115020065
Laporte G, Nickel S, da Gama FS (2015) Location science. Springer, Cham. doi:10.1007/978-3-319-13111-5
Liu J, Sridharan S, Fookes C (2016) Recent advances in camera planning for large area surveillance: a comprehensive review. ACM Comput Surv 49(1):6:1–6:37. doi:10.1145/2906148
Maclagan D, Sturmfels B (2015) Introduction to tropical geometry, Graduate studies in mathematics, vol 161. AMS, Providence
McEneaney WM (2006) Max-plus methods for nonlinear control and estimation systems and control: foundations and applications, Birkhäuser, Boston. doi:10.1007/0-8176-4453-9
ReVelle CS, Eiselt HA (2005) Location analysis: a synthesis and survey. Eur J Oper Res 165(1):1–19. doi:10.1016/j.ejor.2003.11.032
SPAWAR Systems Center Atlantic (2013) CCTV technology handbook. US Department of Homeland Security, New York
Sule DR (2001) Logistics of facility location and allocation. Marcel Dekker, New York
Tharwat A, Zimmermann K (2010) One class of separable optimization problems: solution method, application. Optimization 59(5):619–625. doi:10.1080/02331930801954698
Wesolowsky GO (1972) Rectangular distance location under the minimax optimality criterion. Transp Sci 6(2):103–113. doi:10.1287/trsc.6.2.103
Zhao J, Yoshida R, Cheung SCS, Haws D (2013) Approximate techniques in solving optimal camera placement problems. Int J Distrib Sens Netw 9(11):1–15. doi:10.1155/2013/241913
Zimmermann K (1992) Min–max emergency service location problems with additional conditions. In: Oettli W, Pallaschke D (eds) Advances in optimization, Lecture notes in economics and mathematical systems, vol 382. Springer, Berlin, pp 504–512. doi:10.1007/978-3-642-51682-5_3
Zimmermann K (1992b) Optimization problems with unimodal functions in max-separable constraints. Optimization 24(1–2):31–41. doi:10.1080/02331939208843777
Acknowledgements
This work was supported in part by the Russian Foundation for Humanities (Grant No. 16-02-00059). The author thanks three referees for valuable comments and suggestions, which have been incorporated into the final version of the manuscript.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Krivulin, N. Using tropical optimization to solve constrained minimax single-facility location problems with rectilinear distance. Comput Manag Sci 14, 493–518 (2017). https://doi.org/10.1007/s10287-017-0289-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10287-017-0289-2
Keywords
- Minimax location problem
- Rectilinear distance
- Idempotent semifield
- Tropical optimization
- Constrained optimization
- Explicit solution