Heuristics for the facility location and design (1|1)-centroid problem on the plane

A chain (the leader) wants to set up a single new facility in a planar market where similar facilities of a competitor (the follower), and possibly of its own chain, are already present. The follower will react by locating another single facility after the leader locates its own facility. Fixed demand points split their demand probabilistically over all facilities in the market in proportion to their attraction to each facility, determined by the different perceived qualities of the facilities and the distances to them, through a gravitational model. Both the location and the quality (design) of the new leader’s facility are to be found. The aim is to maximize the profit obtained by the leader following the follower’s entry. Four heuristics are proposed for this hard-to-solve global optimization problem, namely, a grid search procedure, an alternating method and two evolutionary algorithms. Computational experiments show that the evolutionary algorithm called UEGO_cent.SASS provides the best results.     

A two-level evolutionary algorithm for solving the facility location and design (1|1)-centroid problem on the plane with variable demand

In this work, the problem of a company or chain (the leader) that considers the reaction of a competitor chain (the follower) is studied. In particular, the leader wants to set up a single new facility in a planar market where similar facilities of the follower, and possibly of its own chain, are already present. The follower will react by locating another single facility after the leader locates its own facility. Both the location and the quality (representing design, quality of products, prices, etc.) of the new leader’s facility have to be found. The aim is to maximize the profit obtained by the leader considering the future follower’s entry. The demand is supposed to be concentrated at n demand points. Each demand point splits its buying power among the facilities proportionally to the attraction it feels for them. The attraction of a demand point for a facility depends on both the location and the quality of the facility. Usually, the demand is considered in the literature to be fixed or constant regardless the conditions of the market. In this paper, the demand varies depending on the attraction for the facilities. Taking variable demand into consideration makes the model more realistic. However, it increases the complexity of the problem and, therefore, the computational effort needed to solve it. Three heuristic methods are proposed to cope with this hard-to-solve global optimization problem, namely, a grid search procedure, a multistart algorithm and a two-level evolutionary algorithm. The computational studies show that the evolutionary algorithm is both the most robust algorithm and the one that provides the best results.     

On the ( r | X p )-Medianoid Problem on a Network with Vertex and Edge Demands

This article considers the (r|X _p )-medianoid problem on a network N=(V,E) with vertex and edge demands. There are already p facilities located on the network and customers patronize the closest facility. The aim is to locate r additional facilities on the network where their captured demands will be maximized. Relationships with the (r|X _p )-medianoid problem with vertex demands are established. Complexity and algorithmic results are presented.     

On the complexity of locating linear facilities in the plane

We consider the computational complexity of linear facility location problems in the plane, i.e., given n demand points, one wishes to find r lines so as to minimize a certain objective-function reflecting the need of the points to be close to the lines. It is shown that it is NP-hard to find r lines so as to minimize any isotone function of the distances between given points and their respective nearest lines. The proofs establish NP-hardness in the strong sense. The results also apply to the situation where the demand is represented by r lines and the facilities by n single points.     

On the complexity of the dualization problem

The computational complexity of discrete problems concerning the enumeration of solutions is addressed. The concept of an asymptotically efficient algorithm is introduced for the dualization problem, which is formulated as the problem of constructing irreducible coverings of a Boolean matrix. This concept imposes weaker constraints on the number of “redundant” algorithmic steps as compared with the previously introduced concept of an asymptotically optimal algorithm. When the number of rows in a Boolean matrix is no less than the number of columns (in which case asymptotically optimal algorithms for the problem fail to be constructed), algorithms based on the polynomialtime-delay enumeration of “compatible” sets of columns of the matrix is shown to be asymptotically efficient. A similar result is obtained for the problem of searching for maximal conjunctions of a monotone Boolean function defined by a conjunctive normal form.     

On the complexity of inverse convex ordered 1-median problem on the plane and on tree networks

An ordered median function is used in location theory to generalize a class of problems, including median and center problems. In this paper we consider the complexity of inverse ordered 1-median problems on the plane and on trees, where the multipliers are sorted nondecreasingly. Based on the convexity of the objective function, we prove that the problems with variable weights or variable coordinates on the line are NP-hard. Then we can directly get the NP-hardness result for the corresponding problem on the plane. We finally develop a cubic time algorithm that solves the inverse convex ordered 1-median problem on trees with relaxation on modification bounds.     

On the complexity of the car sequencing problem

In this note we give an easier proof of the known result that the car sequencing problem is NP-hard, and point out that it is NP-hard in the strong sense. We show that a previous claim of NP-completeness is incorrect, and instead we give a sufficient condition of membership of NP. We also provide a pseudo-polynomial algorithm for a special case.     

On the complexity of the disjoint paths problem

In this paper we consider the disjoint paths problem. Given a graphG and a subsetS of the edge-set ofG the problem is to decide whether there exists a family of disjoint circuits inG each containing exactly one edge ofS such that every edge inS belongs to a circuit inC. By a well-known theorem of P. Seymour the edge-disjoint paths problem is polynomially solvable for Eulerian planar graphsG. We show that (assumingPNP) one can drop neither planarity nor the Eulerian condition onG without losing polynomial time solvability. We prove theNP-completeness of the planar edge-disjoint paths problem by showing theNP-completeness of the vertex disjoint paths problem for planar graphs with maximum vertex-degree three. This disproves (assumingPNP) a conjecture of A. Schrijver concerning the existence of a polynomial time algorithm for the planar vertex-disjoint paths problem. Furthermore we present a counterexample to a conjecture of A. Frank. This conjecture would have implied a polynomial algorithm for the planar edge-disjoint paths problem. Moreover we derive a complete characterization of all minorclosed classes of graphs for which the disjoint paths problem is polynomially solvable. Finally we show theNP-completeness of the half-integral relaxation of the edge-disjoint paths problem. This implies an answer to the long-standing question whether the edge-disjoint paths problem is polynomially solvable for Eulerian graphs.Supported by Sonderforschungsbereich 303 (DFG)     

A scheme of approximation solution of problem 1 |r j|L max

The strongly NP-hard scheduling problem of minimizing the maximum lateness on one machine subject to job release dates is under study. We present a general scheme of approximation solution of the problem which is based on searching for a given problem instance another instance, closest to the original in some metric and belonging to a known polynomially solvable class of instances. For a few concrete variants of the scheme (using different polynomially solvable classes of instances) some analytic formulas are found that make it possible, given a problem instance, to compute easily an upper bound on the absolute error of the solution obtained by a chosen scheme.     

On the complexity of rainbow spanning forest problem

Given a graph \(G=(V,E,L)\) and a coloring function \(\ell : E \rightarrow L\), that assigns a color to each edge of G from a finite color set L, the rainbow spanning forest problem (RSFP) consists of finding a rainbow spanning forest of G such that the number of components is minimum. A spanning forest is rainbow if all its components (trees) are rainbow. A component whose edges have all different colors is called rainbow component. The RSFP on general graphs is known to be NP-complete. In this paper we use the 3-SAT Problem to prove that the RSFP is NP-complete on trees and we prove that the problem is solvable in polynomial time on paths, cycles and if the optimal solution value is equal to 1. Moreover, we provide an approximation algorithm for the RSFP on trees and we show that it approximates the optimal solution within 2.     

On the complexity of a bundle pricing problem

We consider the problem of pricing items in order to maximize the revenue obtainable from a set of single minded customers. We relate the tractability of the problem to structural properties of customers’ valuations: the problem admits an efficient approximation algorithm, parameterized along the inhomogeneity of the valuations.     

On the inverse emergent plane crack problem

This paper deals with the detection of emergent plane cracks, by using boundary measurements. An identifiability result (uniqueness of the solution) is first proved. Then, we look at the stability of this solution with respect to the measurement. A weak stability result is proved, as well as a Lipshitz stability result for straight cracks, by using domain-derivative techniques. © 1998 B. G. Teubner Stuttgart—John Wiley & Sons, Ltd.