Contributed Session Wed.3.H 3008

Wednesday, 15:15 - 16:45 h, Room: H 3008

Cluster 2: Combinatorial optimization [...]

Competitive and multi-objective facility location

 

Chair: Yury Kochetov

 

 

Wednesday, 15:15 - 15:40 h, Room: H 3008, Talk 1

Vladimir Beresnev
Algorithms for discrete competitive facility location problem

 

Abstract:
We consider a mathematical model generalizing the well-known facility location problem. In this model two rival sides (Leader and Follower) sequentially open their facilities and aim to capture clients in order to make maximal profit. We state the problem as a bilevel integer programming problem. It includes the upper level (Leader’s) problem and the lower level (Follower’s) problem. We consider so-called optimal noncooperative solutions to the problem, where from all possible optimal solutions to Follower’s problem we choose the solution which yields the smallest value of the objective function of the Leader’s problem. We represent our problem as the problem of maximizing a pseudo-Boolean function. We propose a local search algorithm for constructing an approximate solution to the problem and a branch-and-bound algorithm for finding an optimal solution of the problem. An important ingredient of the algorithms is a method for calculating an upper bound for the values of the pseudo-Boolean function on subsets of solutions.

 

 

Wednesday, 15:45 - 16:10 h, Room: H 3008, Talk 2

Yury Kochetov
A local search algorithm for the (r | p)-centroid problem on the plane

Coauthors: Emilio Carrizosa, Ivan A. Davydov, Alexandr V. Plyasunov

 

Abstract:
In the (r | p)-centroid problem two players, leader and
follower, open facilities to service clients. We assume that clients are on the Euclidean plane and facilities can be opened in arbitrary points on the plane. Leader opens p facilities. Later on, follower opens r facilities. Each client patronizes the closest facility. Our goal is to find p facilities for the leader to maximize his market share. We show that the problem is Σ2P-hard. In other words, this Stackelberg game is more difficult than well-known
NP-complete problems, unless P=NP. To find near optimal solutions we develop a local search heuristic, based on the exact approach for the follower problem. We apply discretization of the (r | Xp-1+1)-centroid problem where the leader can move one facility only in order to identify the best neighboring solution. Starting solution is generated by a new alternating heuristic and an exact
polynomial time algorithm for the (1 | 1)-centroid problem. Computational experiments for the randomly generated test instances show that this local search algorithm dominates the previous heuristics.

 

 

Wednesday, 16:15 - 16:40 h, Room: H 3008, Talk 3

Marta Mb Pascoal
Path based method for multicriteria metro location

Coauthor: Gilbert Laporte

 

Abstract:
We model the metro location problem considering the maximization of the population covered by the metro stations, the minimization of the construction cost and the minimization of the metro line lengths, under some constraints.
Sets of efficient metro lines and correspondent metro stations are obtained by applying a path based algorithm.
The metro lines are then combined following traditional metro configurations by means of solving a multicriteria linear program.

 

  cash loans . Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Levitra, but also as part of its analogs.