**Seminar on
Applied Mathematics**

**PROGRAM**

Matematički fakultet

Fakultet organizacionih nauka

JUPIM

IEEE Computer Chapter, Srbija

MI SANU, Knez Mihailova 36, sala 301f

**
**

**
Ponedeljak, 27.09.2010. u 14:15, Sala 301f, MI SANU:
**

**
Yury Kochetov,
Sobolev Institute of Mathematics,
Novosibirsk, Russia;
e-mail: jkochet@math.nsc.ru
HEURISTIC AND EXACT METHODS FOR THE
COMPETITIVE p-MEDIAN PROBLEM
**

**
Sadrzaj: In the competitive p-median problem two decision makers, a leader and a
follower, compete to attract clients from a given market. The leader opens
p facilities, anticipating that the follower will react to the decision by
opening his own r facilities. The decision makers try to maximize their
own profits. This Stackelberg game is P2 -hard. We develop a hybrid
memetic algorithm for it where probabilistic tabu search heuristic is
applied for improving the offspring. To obtain an upper bound, we
reformulate the problem as a mixed integer program with large number of
constraints and variables. Selecting some of them, we get the desired
upper bound. To find optimal solutions, we iteratively modify the subset
of the constraints and variables. This approach is tested on the
benchmarks from the library Discrete Location Problems. The optimal
solutions are found for r = p = 5, 100 clients, and 100 facilities.
**

**
**

**
**

**
RUKOVODIOCI SEMINARA
**

**
Vera Kovačević-Vujčić
Milan Dražić
**