Locating a semi-obnoxious covering facility with repelling polygonal regions

Discrete Applied Mathematics 161 (2013) 2604–2623 Contents lists available at ScienceDirect Discrete Applied Mathematics journal homepage: www.elsevier.com/locate/dam Locating a semi-obnoxious covering facility with repelling polygonal regions✩ Frank Plastriaa,∗, José Gordillob, Emilio Carrizosab aVrije Universiteit Brussel, Belgium bUniversidad de Sevilla, Spain article info Article history: Received 11 June 2010 Received in revised form 13 May 2013 Accepted 18 May 2013 Available online 15 June 2013 Keywords: Continuous location Push–pull Semi-obnoxious facility Covering Euclidean distance Margin maximization abstract A facility is to be located in the Euclidean plane to serve certain sites by covering them closely. Simultaneously, a set of polygonal areas must be protected from the negative effects from that facility. The problem is formulated as a margin maximization model. Necessary optimality conditions are studied and a finite dominating set of solutions is obtained, leading to a polynomial algorithm. The method is illustrated on some examples. ©2013 Elsevier B.V. All rights reserved. 1. Introduction A facility is called semi-obnoxious, semi-desirable or push–pull (to use the expressive terminology introduced in [15]) when it gives a service to demand in its neighborhood but is also felt as obnoxious, potentially or outrightly noxious to the environment, or needs to be protected from potential threats. For instance hospitals, airports, train stations, radio or wireless stations and alarm sirens are examples of semi-obnoxious facilities, since they are useful and necessary for the community, but are also a source of negative effects, such as noise or electromagnetic energy, and therefore considered as NIMBY (not in my backyard) facilities. Since the early work on modeling the optimal location in such situations as surveyed in general in [7] and in a discrete setting in [20], the last decade has known many more publications around this difficult topic. The research presented in this paper falls within this general framework but presents several distinctive features, as shortly described next, and more in detail in the next section. In our problem, a semi-obnoxious facility must be located in the plane with regards to two different sets. On the one hand, we have the demand points served by the proximity of the facility that is therefore pulled towards them, so should be as close as possible to all of them. On the other hand, a repelling region should be protected from the (ob)noxious effects coming from the facility, or it is the facility that should be protected from possible threats out of this region. Therefore the facility should be as far as possible from all points of the region. As usual the region is described as in a Geographical Information System (GIS) as a union of polygons. So the demand points must lie well covered within a circle centered at the facility, ✩This work has been written while the second author visited MOSI, Vrije Universiteit Brussel. The support of grants MTM2009-14039-C06-06 of MEC, Spain, and FQM-329 of Junta de Andalucía, Spain, is acknowledged. ∗Corresponding author. Tel.: +32 2 6293609; fax: +32 2 6293690. E-mail addresses: [email protected] (F. Plastria), [email protected] (J. Gordillo), [email protected] (E. Carrizosa). 0166-218X/$ – see front matter ©2013 Elsevier B.V. All rights reserved. http://dx.doi.org/10.1016/j.dam.2013.05.010 F. Plastria et al. / Discrete Applied Mathematics 161 (2013) 2604–2623 2605 Fig. 1. Two possible separating balls. while the region should remain well outside this same circle. Both the push and pull objectives are thus considered to be of Rawlsian nature [15] using Euclidean distances, yielding a new continuous covering location model of the kind reviewed in [29]. The three last examples cited higher typically present such features. The quality of connection with a wireless station sharply depends on the Euclidean distance to it, but is also considered as harmful when living too close by, so highly populated areas should be touched only at low level. Also if some countries neighboring a region form a possible threat of attack to the facility or may be a source of spying by listening in to the emissions of the station, the facility should lie at some largest possible Euclidean distance from it. Similarly an alarm siren should be well heard by the whole community, but should not trouble too much the wildlife in the nature reserves around, while noise decays uniformly in all directions. As far as we are aware no earlier work seems to have been published with all the same characteristics. The major differences with mainstream work in semi-obnoxious models are as follows. •Our model is about location in a continuous space, contrary to many studies in a discrete or a network environment [6,16,2,3]. •We use Euclidean distance, instead of other (less realistic) distance measures [23,18]. •At least the pull part of the objective is often considered of minsum type (Weber-like) see [14,9,31,34,19], whereas we use minmax. •The problem is usually seen as biobjective and the efficient set or a finite approximation of it [24,4,26,25] is sought, but we seek one explicit solution. •We consider repelling regions, as in [4], instead of repelling points (see [8,18,5,1,22,21]). In the next section, we introduce a formulation of our problem using the popular quadratic margin maximization method of Support Vector Machine in Machine Learning. This formulation enables the construction of an exact global optimal solution, without resorting to the use of cumbersome global optimization methods that yield only approximations as in [28,32,13,5]. The structural properties derived in Section 3lead to a finite dominating set, the enumeration of which yields a finite and polynomial method detailed in Section 4, that is tested on some artificial databases in Section 5. 2. The model 2.1. The basic aim Consider G+and G−, two groups of objects in the Euclidean plane, where G+is a finite set of points G+= {x1,...,xn} ⊂ R2, and G−is a set of compact convex polygonal areas G−= {S1,...,Sm} ⊂ R2(with n,m≥3). The points of G+ represent individual customers to be serviced by the facility, while the polygons represent areas to be protected from the inconveniences of the semi-obnoxious facility to be located. The points of G+are assumed not to be contained in any element of G−. Also the polygons in G−are assumed to have pairwise disjoint interiors. Note that this is not a restriction because any (possibly disconnected) polygonal region can be decomposed into a finite set G−which satisfies our assumptions. Our aim is to locate a single semi-obnoxious facility, x0∈R2, which is as near as possible to the points of G+(attracting elements) in order to receive a high-quality service, and far from the polygons of G−(repelling elements). As explained in the Introduction, all distances are measured in the Euclidean way. Therefore the location of the facility will be decided through the construction of a ball B(x0,r), with x0∈R2and r∈R+, such that every point of G+is deeply contained in the ball and every polygon of G−lies far outside the ball. In Fig. 1, an example of the problem is depicted. The black points represent the attracting points of G+, whereas the graycolored areas represent the repelling elements of G−. Our problem is to build a ball containing all the points well inside while remaining well away from any polygon. 2606 F. Plastria et al. / Discrete Applied Mathematics 161 (2013) 2604–2623 Different solutions may exist separating the elements in G+and G−. For instance, in Fig. 1 two possible circles separating the two groups have been depicted. In order to single out one ball, we follow the strategy that is successfully used in Support Vector Machines, [10,33], and maximize a quadratic margin as defined in the next section. Following this strategy, the smallest circle in Fig. 1 will be preferred. 2.2. The optimization problem Given the elements of the two groups, G+and G−, the following constraints are desirable, ∥x0−xi∥2<r2∀xi∈G+,(1) min x∈Sj ∥x0−x∥2≥r2∀Sj∈G−,(2) where ∥·∥is the Euclidean norm. Constraints (1)–(2) are equivalent respectively to r2− ∥x0−xi∥2>0∀xi∈G+⇔min xi∈G+ (r2− ∥x0−xi∥2) > 0,(3) min x∈Sj (∥x0−x∥2−r2)≥0∀Sj∈G−⇔min Sj∈G− min x∈Sj (∥x0−x∥2−r2)≥0.(4) We propose to maximize the (quadratic) margin ∆, which is the minimum of the two positive amounts described in (3)–(4). The optimization problem we have to solve is then max x0,r∆(5) where ∆=min min xi∈G+ (r2− ∥x0−xi∥2), min Sj∈G− min x∈Sj (∥x0−x∥2−r2).(6) This may be rewritten as max x0,r,∆ ∆ s.t. ∆≤min xi∈G+ (r2− ∥x0−xi∥2) ∆≤min Sj∈G− min x∈Sj (∥x0−x∥2−r2) (7) or equivalently, max x0,r,∆ ∆ s.t. ∆≤r2− ∥x0−xi∥2∀xi∈G+ ∆≤ ∥x0−x∥2−r2∀x∈Sj,∀Sj∈G−. (8) If we denote r2 +=r2−∆and r2 −=r2+∆, the objective function of Problem (8) changes into ∆=r2 −−r2 + 2, and the problem can be reformulated as max x0,r+,r− r2 −−r2 + s.t. ∥x0−xi∥ ≤ r+∀xi∈G+ ∥x0−x∥ ≥ r−∀x∈Sj,∀Sj∈G− r+,r−≥0. (9) and if needed one may recover r2as r2 −+r2 + 2, if ∆is positive. Indeed, Problem (9) is in fact more general since it also encompasses situations with negative optimal value, that correspond to the (frequent) situations of unfeasibility of previous constraints sets (1)–(2),(3)–(4), or those of problem (7). This new formulation is never unfeasible, and indicates what should be considered as optimal (or rather least undesirable) in these latter cases. It will follow from Theorem 1 below that the optimal radii r+and r−are easily defined as a function of the center x0, and Problem (9) can be reformulated further with an objective depending on x0only, as follows F. Plastria et al. / Discrete Applied Mathematics 161 (2013) 2604–2623 2607 Fig. 2. The two separating concentric balls with maximum margin. (a) Feasible case, (b) unfeasible case. max x0∈R2f(x0) s.t. f(x0)=r2 −(x0)−r2 +(x0) r+(x0)=max xi∈G+ ∥x0−xi∥ r−(x0)=min Sj∈G− min x∈Sj ∥x0−x∥. (10) Hence we may view our problem as obtaining two concentric balls B(x0,r+)and B(x0,r−), where the ball B(x0,r−)does not contain strictly any points of the polygons of G−, the ball B(x0,r+)contains every point xibelonging to G+, and the difference between the squares of the first and second radius is as large as possible. In case r−≥r+, i.e. when the original problem is feasible, this geometrically means that the area of the annulus between the two circles is as large as possible (see Fig. 2(a)), showing that our problem is somewhat related to the so-called largest empty annulus problem [12]. (In that model, however, only a set of points is given and an annulus of maximal area without such points in its interior is sought, and no regions are considered.) In case r−<r+, when the original problem is unfeasible, the area of the annulus should be as small as possible (see Fig. 2(b)). Note that the use of the squared radii in the objective seems particularly suited to the main kinds of applications mentioned in the Introduction, since effects like noise and electro-magnetic energy decay quadratically with distance. 3. Necessary conditions for optimality We now derive a number of necessary optimality conditions, based on the notion of active element as defined below. We will write (x0,r+,r−)to either denote a finite feasible solution of Problem (9) or assume that r+=r+(x0)and r−=r−(x0) as defined in Problem (10). A point xifrom G+is an active point for the solution (x0,r+,r−)iff the distance from xito the center x0is exactly r+, that is, d(x0,xi)= ∥x0−xi∥ = r+. Thus, the set of active points of G+, denoted by A+(x0), consists of the points lying on the boundary of the ball B(x0,r+). In the same way, a polygon Sjfrom G−is an active polygon for (x0,r+,r−)iff the distance from Sjto x0is exactly r−, that is, d(x0,Sj)=minx∈Sj∥x0−x∥ = r−. We denote by A−(x0)the set of active polygons from G−. When x0is clear from the context, we will simply write A+and A−. Showing that a feasible solution (x0,r+,r−)is not optimal may be done in two ways: either find another feasible solution (x′ 0,r′ +,r′ −)with a better objective value or exhibit a direction of increase of fat x0. Theorem 1. If (x0,r+,r−)is an optimal solution, there exists at least one active element in each group G+and G−, that is, the sets A+and A−are non-empty. Proof. Suppose that A+is an empty set. Since (x0,r+,r−)is a feasible solution of Problem (9), all the points of the group G+must be (due to the emptiness of A+) contained strictly in the ball B(x0,r+), that is, ∥x0−xi∥<r+,∀xi∈G+. Then, it is sufficient to take r′ +=r+(x0)=max xi∈G+ ∥x0−xi∥, which is strictly smaller than r+, and we obtain (x0,r′ +,r−), a feasible solution improving strictly the value of the objective function. 2608 F. Plastria et al. / Discrete Applied Mathematics 161 (2013) 2604–2623 Fig. 3. Proof of Theorem 2, case r+≤r−. On the other hand, suppose that A−is empty. Due to the feasibility of (x0,r+,r−), the distance from x0to every polygon of G−is strictly greater than r−, that is, d(x0,Sj) > r−,∀Sj∈G−. Thus, it is sufficient to consider r′ −=r−(x0)=min Sj∈G− d(x0,Sj)=min Sj∈G− min x∈Sj ∥x0−x∥, which is strictly greater than r−, and the solution (x0,r+,r′ −)strictly improves the objective function. In both cases, we conclude that the initial solution (x0,r+,r−)cannot be optimal.  Theorem 2. For any optimal solution (x0,r+,r−)one has 1. If r+≤r−, then there must exist at least two active polygons in G−. 2. If r+≥r−, then there must exist at least two active points in G+. Proof. By Theorem 1 there exists at least one active point ain G+and one active polygon Sin G−. 1. In case r+≤r−, suppose Sis the only polygon in A−. Let ybe the projection of x0on S, i.e. the point in Ssuch that d(x0,S)=minx∈Sd(x0,x)=d(x0,y)and consider the direction p=x0−y. We will show that this vector prepresents a direction of improvement for the objective function. If we move x0an amount ϵ > 0, small enough (for not finding any new active element), in the direction u=p ∥p∥, we obtain that x′ 0=x0+ϵuand r′ −=r−+ϵ. The other radius r′ +must be measured as the maximum distance from x′ 0to the points belonging to A+(x0). In case r′ +≤r+, because the new center is closer to all the points in A+(x0), the radii r′ +and r′ −will have decreased and increased respectively, and consequently the objective function will also have strictly improved. Otherwise, the radius r′ +will be the distance from x′ 0to the point aof A+(x0)that is now the furthest one (see Fig. 3). Due to the triangle inequality on a,x0and x′ 0, one has that r′ +≤r++ϵ, and the value of the objective function is strictly improved as soon as r+<r−, since r′2 −−r′2 +≥(r−+ϵ)2−(r++ϵ)2 =r2 −−r2 ++2ϵ(r−−r+) > r2 −−r2 +. But also if r+=r−the points x′ 0,aand ycannot be collinear since this would mean that a=y, contrary to our general assumption that no point of G+belongs to an element of G−. Therefore x′ 0,aand yare not collinear, so by the strict triangle inequality we have r′ +<r++ϵ, and thus r′2 −−r′2 +> (r−+ϵ)2−(r++ϵ)2=0=r2 −−r2 +. 2. When r+≥r−, suppose there is only one active point ain A+. Then, the vector p=a−x0will be shown to represent a direction of improvement. If x0is moved an amount ϵ > 0, small enough for not having new active elements, in the direction u=p ∥p∥, we obtain that r′ +=r+−ϵ. The radius r′ −will be the minimum distance from x′ 0=x0+ϵuto the polygons in A−(x0). If now r′ −≥r−, that is the new center is further from all the polygon candidates to become active, the two radii r′ +and r′ −have improved and so also the objective function has. Any active polygon Sfor the center x0will also be the polygon closest to the new center x′ 0, since there are no new active polygons in G−. Let ybe the projection of x0on S, i.e., the point of S such that d(x0,S)=minx∈Sd(x0,x)=d(x0,y). Now the objective function can be expressed as follows: r2 −−r2 += ∥x0−y∥2− ∥x0−a∥2. Three different situations must be considered. F. Plastria et al. / Discrete Applied Mathematics 161 (2013) 2604–2623 2609 Fig. 4. Proof of Theorem 2, case r+≥r−: the distance to the polygon is measured in the vertex. Fig. 5. Proof of Theorem 2, case r+≥r−: the distance to the polygon is measured in the edge. •If yis a vertex of the polygon Sand x0is strictly contained in the normal cone of Sin y(denoted by NS(y)), that is, x0 satisfies (x0−y)t(y−s) > 0∀s∈S, then, for ϵ > 0 small enough, x′ 0will also be contained strictly in this normal cone, and d(x′ 0,S)=minx∈Sd(x′ 0,x)=d(x′ 0,y)(see Fig. 4). In that case, due to the triangle inequality, one has that r−≤r′ −+ϵand consequently, r′ −≥r−−ϵ, and the value of the objective function is improved in case r+>r−, because r′2 −−r′2 +≥(r−−ϵ)2−(r+−ϵ)2 =r2 −−r2 ++2ϵ(r+−r−) > r2 −−r2 +.(11) For r+=r−, we know that r−<r′ −+ϵ, except for the case when x′ 0,yand aare collinear. But this situation is not possible for r+=r−, because it would mean that a∈S, which is not allowed by assumption. Therefore, r′2 −−r′2 +> (r−−ϵ)2−(r+−ϵ)2=r2 −−r2 +.(12) •If the point yis not a vertex of Sit lies on (the relative interior of) an edge of Sand the value ϵ > 0 may be chosen small enough so that the point zof Sclosest to the new center lies on the same edge of the polygon (see Fig. 5). Using the definition of r−and the triangle inequality on x0,zand x′ 0we obtain r−=min x∈Sd(x0,x)≤d(x0,z)≤r′ −+ϵ. Thus r′ −≥r−−ϵand we obtain again the same inequalities as in (11) showing that the objective function is improved for r+>r−. In case r+=r−, we may again rule out x0,yand acollinear because it would mean a=y∈S, contrary to assumptions. Therefore we obtain as above inequality (12), showing that the objective function is also improved. •If yis a vertex of Sand x0is on the boundary of the normal cone of Sin y, then the projection of the new center x′ 0on Swill be either the same vertex yor a point zon an adjacent edge of S, depending on the position of a. Hence, one of the two arguments used previously applies to find a solution with a better value of the objective function.  2610 F. Plastria et al. / Discrete Applied Mathematics 161 (2013) 2604–2623 Fig. 6. Proof of Theorem 4, second part. Remark 3. It can be proved that, when points of G+are allowed to lie in some polygon of G−,Theorem 2 still holds in case of strict inequalities. However, when r+=r−one may only conclude existence of an optimal solution with two active elements in G+and of a (possibly different) optimal solution with two active elements in G−. Theorem 4. For any optimal solution (x0,r+,r−)the convex hulls CH(A+)and CH(A−)of the two groups of active elements intersect. Proof. Assume contrarily that CH(A+)∩CH(A−)= ∅. Then a straight line hof equation ptx=ccan be found which strictly separates these two convex hulls. We may choose pas a unit vector and c∈R, such that the halfplane containing CH(A+) is defined by {ptx>c}. Consider the straight line g: {x=x0+λp, λ ∈R}. We now show that the objective function will be improved by moving x0along this straight line a certain amount ϵ > 0. Denote by San active polygon from A−(x0)which is the closest one to the new center x′ 0=x0+ϵp, and by aa point from A+(x0)which maximizes the distance from x′ 0to A+(x0). Denote by a0the orthogonal projection of aon g. Let ybe the point of Ssuch that d(x0,S)=minx∈Sd(x0,x)=d(x0,y)and y0its orthogonal projection on the straight line g. With this notation, the objective function can be expressed as follows: r2 −−r2 += ∥x0−y∥2− ∥x0−a∥2 = ∥x0−y0∥2+ ∥y0−y∥2− ∥x0−a0∥2− ∥a0−a∥2. If we move x0to x′ 0along the straight line g, to measure the new radius r′ −, three different situations must be analyzed. •In case the point yis a vertex of the polygon and x0is strictly contained in the normal cone of Sin y, then, for an amount ϵ > 0 small enough, the new center x′ 0will also be contained strictly in the normal cone, and the distance from x′ 0to S will continue being the distance from x′ 0to the vertex y, that is, d(x′ 0,S)=minx∈Sd(x′ 0,x)=d(x′ 0,y). Then, since p=a0−y0 ∥a0−y0∥(observe that a0= y0, because gis orthogonal to the separating hyperplane and hence, a0and y0are also separated by the straight line h), the following calculation shows that the objective function improves, r′2 −−r′2 += ∥x0+ϵp−y0∥2+ ∥y0−y∥2− ∥x0+ϵp−a0∥2− ∥a0−a∥2 = ∥x0−y0∥2+2ϵ(x0−y0)tp+ ∥y0−y∥2− ∥x0−a0∥2−2ϵ(x0−a0)tp− ∥a0−a∥2 =r2 −−r2 ++2ϵ(a0−y0)ta0−y0 ∥a0−y0∥ =r2 −−r2 ++2ϵ∥a0−y0∥>r2 −−r2 +. •If the point yis not a vertex of Sit lies on (the relative interior of) an edge of Sand the value ϵ > 0 may be chosen small enough so that the point zof Sclosest to the new center x′ 0lies on the same edge of this polygon. (See Fig. 6.) Consider the orthogonal projection z0of zon the straight line g. Observe that p=a0−z0 ∥a0−z0∥(a0= z0, because gis orthogonal to hand hseparates aand z) and observe also that x0−yand z−yare orthogonal, because yis the projection of x0on the edge containing z. Therefore, by Pythagoras’s Theorem, one has that ∥x0−z0∥2+ ∥z0−z∥2= ∥x0−z∥2= ∥x0−y∥2+ ∥y−z∥2 ≥ ∥x0−y∥2= ∥x0−y0∥2+ ∥y0−y∥2.(13) The objective function at x′ 0is then r′2 −−r′2 += ∥x0+ϵp−z0∥2+ ∥z0−z∥2− ∥x0+ϵp−a0∥2− ∥a0−a∥2 = ∥x0−z0∥2+2ϵ(x0−z0)tp+ ∥z0−z∥2− ∥x0−a0∥2−2ϵ(x0−a0)tp− ∥a0−a∥2 F. Plastria et al. / Discrete Applied Mathematics 161 (2013) 2604–2623 2611 Fig. 7. Bisector of two polygons S1and S2. Breakpoints •. and using inequality (13) we obtain r′2 −−r′2 +≥ ∥x0−y0∥2+ ∥y0−y∥2− ∥x0−a0∥2− ∥a0−a∥2+2ϵ(a0−z0)tp =r2 −−r2 ++2ϵ∥a0−z0∥>r2 −−r2 +. •In case yis a vertex of Sand x0is on the boundary of the normal cone of Sin y, then the projection of x′ 0on Swill be either the vertex yor a point zon an edge of S, and, depending on the position of a, one of the two previous arguments applies to find a solution which improves the objective function.  Remark 5. For the following theorem, we consider the data to be in general position. This means that the following exceptional situations do NOT appear. 1. One point of G+and two vertices of two polygons of G−are collinear. 2. One point of G+and one vertex of a polygon of G−define an orthogonal direction to an edge of a polygon of G−. 3. Two points of G+and one vertex of a polygon of G−are collinear. 4. Two points of G+define an orthogonal direction to an edge of a polygon of G−. Clearly these exceptional situations are non-generic in the sense of occurring with zero probability. Would they occur, any small random perturbation of the data would destroy their presence. Therefore general position may be quite safely assumed. In several cases, though, the effect of their occurrence will be discussed anyway. Likewise, the concept of bisector for two convex polygons and breakpoints will be necessary for the proof of Theorem 7 (see [11,27] for a detailed description). Definition 6. The bisector of two convex polygons S1and S2is the locus of points x∈R2satisfying d(x,S1)=d(x,S2). This bisector is a continuous unbounded curve consisting of linear and parabolic segments. The points at which two such segments meet will be called breakpoints (see Fig. 7). Theorem 7. When the data are in a general position one of the following situations arises for any optimal solution (x0,r+,r−): 1. there exist at least four associated active elements; 2. there exist at least three active elements, two polygons S1,S2∈A−and one point a ∈A+, satisfying that y1,y2and a are collinear, with yisuch that d(x0,Si)=minx∈Sid(x0,x)=d(x0,yi), i=1,2; 3. there exist at least three active elements, two polygons S1,S2∈A−and one point a ∈A+, and x0is a breakpoint. Proof. In case the two radii are equal Theorem 2 immediately yields four active elements. Therefore the following two cases remain. 1. When r+<r−, by Theorems 1 and 2, we know that an optimal solution must have at least two distinct active polygons S1,S2∈A−, and one active point, a∈A+. Suppose an optimal solution (x0,r+,r−)has been obtained with only these three active elements. Since x0must be at the same distance from the two active polygons of A−, it must be along their bisector which is composed of line segments and pieces of parabola. So x0is either a breakpoint or an ‘inner point’ of such a segment or piece. It will suffice to show that the latter case cannot happen because a new better solution could then be found. To this end the following different cases must be considered. 2612 F. Plastria et al. / Discrete Applied Mathematics 161 (2013) 2604–2623 Fig. 8. Distances from x0to the polygons are the distances to two vertices. •If the points of S1and S2closest to x0are vertices y1∈S1and y2∈S2x0lies on the mediatrix rof y1and y2(see Fig. 8). Suppose that the active point a∈A+is nearer to S1than to S2(the other case is analogous by symmetry). Define Ras the convex region determined by those points nearer to S1than to S2which are in the normal cone of S1at y1, that is, R= {x:d(x,y1)≤d(x,y2)} ∩ NS1(y1). In this region define the function g(x)= ∥x−y1∥2− ∥x−a∥2=2xt(a−y1)+ ∥y1∥2− ∥a∥2.(14) One has that f(x)=g(x), ∀x∈R, with fthe objective function of Problem (10), in particular, f(x0)=g(x0). In order to find a direction of improvement for the objective function in the neighborhood of x0, we study the directional derivatives of the objective function fat this point. The function gis differentiable in the region Rwith gradient ∇g(x0)=2(a−y1)at x0. Since f≡gin the convex region Rthe directional derivative along any vector v=y−x0 with y∈Requals ∇vf(x0)= ∇vg(x0)= ∇g(x0)t·v=2(a−y1)tv(15) and to obtain a direction of improvement of f, it is sufficient to choose such a vector vfor which the scalar product (a−y1)tvis strictly positive. Consider the straight line r:(a−y1)t(x−x0)=0 through x0and orthogonal to the vector (a−y1)and construct the region Zdetermined by those points in Rthat are also in the positive halfplane defined by the straight line r: Z=R∩ {x:(a−y1)t(x−x0) > 0}. Except in case the straight line coincides with the mediatrix, for some small enough ϵ > 0 the intersection Z∩B(x0, ϵ) is not empty, and moving x0in direction of any point in this intersection will improve the objective. The exceptional case where rcoincides with the mediatrix is only possible if y1,y2, and aare collinear, hence corresponding to the non-generic situation number 1 in Remark 5 that was ruled out. One may note, however, that in this exceptional case, if we move x0along the mediatrix, the value of the objective function remains constant and the optimal solution is not unique. •If the points of S1and S2closest to x0are a vertex y1∈S1and a point y2lying on the relative interior of an edge of S2 then x0is not a breakpoint of the bisector of S1and S2and lies on a parabolic piece of it, the parabola being the bisector between the vertex y1and the edge of S2(see Fig. 9). Suppose that the active point a∈A+is nearer to S1than to S2(for the other situation, see the reasoning described for the next case, with y1and y2lying on the edges of the polygons). Then a,y1and the parabola lie on the same side of the mediatrix of y1and y2, and this mediatrix is tangent to the parabola at x0. Define the convex set R=NS1(y1)∩ {x:d(x,y1)≤d(x,S2)}and the function gas above in (14). One has that f(x)=g(x), ∀x∈Rsufficiently close enough to x0not to introduce new active elements, and hence, the expression (15) for the directional derivative of fat x0along any vector v=y−x0with y∈Rremains valid and the objective improves along any such direction vfor which (a−y1)tvis strictly positive Consider then the straight line rcontaining x0and orthogonal to (a−y1), so of equation (a−y1)t(x−x0)=0. It cannot be tangent to the parabola since this would mean it coincides with the mediatrix of y1and y2, so that y1,a,x0 and y2are collinear, and hence that a−y1would be orthogonal to the edge containing y2, a situation we ruled out as non-generic case number 2 of Remark 5 (however, in that case a local optimum has been found). Therefore the mediatrix of y1and y2and the line rcross at x0, implying we may find some zdifferent from (but close to) x0such that (a−y1)t(z−x0) > 0 and lying on the same side of the parabola as a, so for which we have d(x,y1) < d(x,S2), thus lying in the interior of R(the set of points satisfying these two constraints is shown as Zin Fig. 9). Hence the direction v=z−x0improves the objective strictly. •If the points y1of S1and y2of S2closest to x0are both on the relative interior of respective edges of S1and S2,x0 lies on the bisectrix of the angle formed by these two edges, and this latter is the bisector of S1and S2within some neighborhood of x0(see Fig. 10). F. Plastria et al. / Discrete Applied Mathematics 161 (2013) 2604–2623 2619 Fig. 15. Candidates type 1. Area of the annulus: 183.27 and 132.32, respectively. Fig. 16. Candidates type 2. Area of the annulus: 182.32, 171.45 and 160.97, respectively. solutions are different because the centers of the balls are different breakpoints of the same bisector. Due to the definition of breakpoint, one of the active squares in this kind of solutions has a vertex as the active element, but the adjacent edge touches tangentially the ball B(x0,r−). Hence, one can say that the two elements (the vertex and the edge) can be considered as active. In this example, there are no candidate solutions with a configuration of type 4. Type 5 is excluded because we found feasible solutions with positive value. If we compare the ten areas (that is, the values of the objective function), we find that the point x0illustrated in the first picture in Fig. 15 is optimal for our problem. 5.2. Medium dataset Other larger databases have been similarly generated to test the algorithm. In the next example we generated at random 50 points for the group G+and 20 points as the centers of the squares of G−.Fig. 18 illustrates the dataset. By means of the method described in Section 4, all the candidate optimal solutions have been studied. The two pictures in Fig. 19 show (at different zoom levels) all 37 obtained candidate locations represented by stars. All the stars far from the set of squares and points represent local optima with a negative value of the objective function. These solutions have at least two active points associated (configurations of type 2 and 5), and represent local optima of formulation (10) with negative objective value. Since our dataset is spherically separable these cannot be global optima. Fig. 20 shows the optimal solution for this dataset. The solution x0, represented by a star, has two active points associated (encircled) and two active squares (in both of them, the point lying on the boundary of the ball is a vertex). 5.3. Large dataset Finally, we show in Fig. 21 a larger random database with 100 points and 50 squares (smaller than above). In Fig. 22 we can see the finite dominating set on two different zoom levels. In total there are 42 candidate points, but most have negative objective value. 2620 F. Plastria et al. / Discrete Applied Mathematics 161 (2013) 2604–2623 Fig. 17. Candidates type 3. Area of the annulus: 35.648, 101.54, 138.16, 21.53 and 33.932, respectively. Fig. 18. Initial scenario (50 points and 20 squares). However as the database is spherically separable we have some solutions with a positive value. All 7 candidates with positive value are depicted in Fig. 23. The optimal location of the facility and the separating balls are shown in Fig. 24. Again, the solution has four active elements associated with it, two active points and two active polygons. The ball of radius r−touches these two squares at one vertex of each square. Observe the quite small number of candidates in the finite dominating set, as compared to the cardinality of the number of cases considered as calculated in the complexity study in Section 4.6.1. This is due to the fact that most cases considered during its construction are found to be unsuitable and are therefore discarded. Some of this work will be avoided by the preprocessing. F. Plastria et al. / Discrete Applied Mathematics 161 (2013) 2604–2623 2621 Fig. 19. Candidates to optimal solution. Fig. 20. Optimal solution. Fig. 21. Initial scenario (100 points and 40 squares). 6. Conclusion and extensions In this work, the problem of locating a single semi-obnoxious facility in the Euclidean plane with repelling areas has been solved. The idea of maximizing a margin, as done in the field of Support Vector Machines, has been introduced to define the concept of solution. 2622 F. Plastria et al. / Discrete Applied Mathematics 161 (2013) 2604–2623 Fig. 22. Finite dominating set. Fig. 23. Candidates with positive value of the objective function. Fig. 24. Optimal solution. The problem has been formulated as a nonlinear continuous optimization problem and necessary conditions for optimality have been deduced. These conditions state that every candidate solution must have at least four active elements (except for some special cases), two of them belonging to the group whose associated ball is larger and one of them belonging to the other group. Likewise, other conditions have been obtained by studying the intersection of the convex hulls of the sets of active elements and the sets of groups, respectively. F. Plastria et al. / Discrete Applied Mathematics 161 (2013) 2604–2623 2623 With these necessary conditions, it has been proved that a finite dominating set of solutions can be built in order to obtain an optimal solution. This dominating set of solutions has been constructed algorithmically and been implemented. Furthermore, some numerical results have been given. More research, e.g. using more advanced algorithmic techniques of computational geometry, should allow to develop better preprocessing rules to avoid a lot of unnecessary work or even to reduce the size of the finite dominating set, and possibly fathoming rules may be developed that would avoid its full enumeration. However, it seems doubtful that its complexity could be reduced without a fundamentally different approach. The concept of a solution for this problem can be extended by considering other types of balls such as ellipsoids. The problem may also be extended to higher dimensions, and/or to the location of several facilities, for which several of the necessary conditions developed here should still hold. For such extensions, as well as for large databases, the number of candidate solutions will become prohibitive and heuristic techniques will have to be used to obtain a solution within an acceptable amount of time. The use of metaheuristics such as Variable Neighborhood Search, see e.g. [17], would be a good candidate. References [1] S. Abravaya, M. Segal, Low complexity algorithms for optimal consumer push–pull partial covering in the plane, European Journal of Operational Research 197 (2) (2009) 456–464. [2] O. Berman, Q. Wang, Locating semi-obnoxious facilities with expropriation: minisum criterion, Journal of the Operational Research Society 58 (3) (2006) 378–390. [3] O. Berman, Q. Wang, Locating a semi-obnoxious facility with expropriation, Computers & Operations Research 35 (2) (2008) 392–403. [4] R. Blanquero, E. Carrizosa, A D.C. biobjective location model, Journal of Global Optimization 23 (2) (2002) 139–154. [5] Rafael Blanquero, Emilio Carrizosa, Pierre Hansen, Locating objects in the plane using global optimization techniques, Mathematics of Operations Research 34 (4) (2009) 837–858. [6] E. Carrizosa, E. Conde, A fractional model for locating semi-desirable facilities on networks, European Journal of Operational Research 136 (1) (2002) 67–80. [7] E. Carrizosa, F. Plastria, Location of semi-obnoxious facilities, Studies in Locational Analysis 12 (1999) 1–27. [8] E. Carrizosa, D. Romero-Morales, Attainment of an optimal solution in a semiobnoxious location problem, Studies in Locational Analysis 12 (1999) 41–48. [9] Pey-Chun Chen, Pierre Hansen, Brigitte Jaumard, Hoang Tuy, Weber’s problem with attraction and repulsion, Journal of Regional Science 32 (4) (1992) 467–486. [10] N. Cristianini, J. Shawe-Taylor, An Introduction to Support Vector Machines and Other Kernel-based Learning Methods, Cambridge University Press, Cambridge, 2000. [11] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer-Verlag, Berlin, 1997. [12] J.M. Díaz-Báñez, F. Hurtado, H. Meijer, D. Rappaport, J.A. Sellarès, The largest empty annulus problem, International Journal of Computational Geometry and Applications 13 (4) (2003) 317–325. [13] Z. Drezner, A. Suzuki, The big triangle small triangle method for the solution of nonconvex facility location problems, Operations Research 52 (1) (2004) 128–135. Cited By (since 1996) 43. [14] Z. Drezner, G.O. Wesolowsky, The Weber problem on the plane with some negative weights, INFOR 29 (1990) 87–99. [15] H.A. Eiselt, G. Laporte, Objectives in location problems, in: Z. Drezner (Ed.), Facility Location, A Survey of Application and Methods, Springer, New-York, 1995, pp. 151–180. [16] H.W. Hamacher, M. Labbé, S. Nickel, A.J.V. Skriver, Multicriteria semi-obnoxious network location problems (MSNLP) with sum and center objectives, Annals of Operations Research 110 (1) (2002) 33–53. [17] Pierre Hansen, Nenad Mladenović, José Moreno Pérez, Variable neighbourhood search: methods and applications, 4OR 6 (2008) 319–360. [18] A. Jourani, C. Michelot, M. Ndiaye, Efficiency for continuous facility location problems with attraction and repulsion, Annals of Operations Research 167 (1) (2009) 43–60. [19] E. Karasakal, D. Nadirler, An interactive solution approach for a bi-objective semi-desirable location problem, Journal of Global Optimization 42 (2) (2008) 177–199. [20] Jakob Krarup, David Pisinger, Frank Plastria, Discrete location problems with push–pull objectives, Discrete Applied Mathematics 123 (1–3) (2002) 363–378. [21] Jochen Krebs, Stefan Nickel, Extensions to the continuous ordered median problem, Mathematical Methods of Operations Research 71 (2010) 283–306. [22] E. Melachrinoudis, Z. Xanthopulos, Semi-obnoxious single facility location in Euclidean space, Computers & Operations Research 30 (14) (2003) 2191–2209. [23] Stefan Nickel, Eva-Maria Dudenhöffer, Weber’s problem with attraction and repulsion under polyhedral gauges, Journal of Global Optimization 11 (4) (1997) 409–432. [24] Y. Ohsawa, Bicriteria Euclidean location associated with maximin and minimax criteria, Naval Research Logistics (NRL) 47 (7) (2000) 581–592. [25] Y. Ohsawa, F. Plastria, K. Tamura, Euclidean push-pull partial covering problems, Computers & Operations Research 33 (12) (2006) 3566–3582. [26] Y. Ohsawa, K. Tamura, Efficient location for a semi-obnoxious facility, Annals of Operations Research 123 (1) (2003) 173–188. [27] Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, John Wiley & Sons, Inc., New York, NY, USA, 1992. [28] F. Plastria, GBSSS: the generalized big square small square method for planar single-facility location, European Journal of Operational Research 62 (2) (1992) 163–174. [29] F. Plastria, Continuous covering location problems, in: Z. Drezner, H.W. Hamacher (Eds.), Facility Location: Applications and Theory, Springer-Verlag, 2002, pp. 37–79 (Chapter 2). [30] Michael Ian Shamos, Dan Hoey, Closest-point problems, in: Proceedings of the 16th Annual Symposium on Foundations of Computer Science, SFCS’75, IEEE Computer Society, Washington, DC, USA, 1975, pp. 151–162. [31] A.J.V. Skriver, K.A. Andersen, The bicriterion semi-obnoxious location (BSL) problem solved by an ϵ-approximation, European Journal of Operational Research 146 (3) (2003) 517–528. [32] Hoang Tuy, Faiz Al-Khayyal, Fangjun Zhou, A D.C. optimization method for single facility location problems, Journal of Global Optimization 7 (1995) 209–227. [33] V.N. Vapnik, Statistical Learning Theory, John Wiley & Sons, Inc., 1998. [34] H. Yapicioglu, A.E. Smith, G. Dozier, Solving the semi-desirable facility location problem using bi-objective particle swarm, European Journal of Operational Research 177 (2) (2007) 733–749.