Geodesic
A branch and bound method for the facility location problem with customer preferences
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 2, pp. 21-41.

Voir la notice de l'article provenant de la source Math-Net.Ru

The article is focused on computational study of the bilevel facility location problem with customer's preferences taken into account. Different integer linear programming formulations are considered. The cutting plane method is implemented for the new family of valid inequalities which are based on relation with the problem for a pair of matrices. The optimal solution of the problem is searched by two variants of branch and bound method using the cutting plane method implemented. The upper bounds for these exact methods are found by Simulated Annealing method. The computational experience illustrates the effectiveness of the proposed methods in comparison with the known approaches. Pic. 1, tabl. 7, bibl. 15.
Keywords: bilevel facility location problem, cutting plane method, local search, branch and bound method. 
@article{DA_2009_16_2_a2,
     author = {I. L. Vasiliev and K. B. Klimentova},
     title = {A branch and bound method for the facility location problem with customer preferences},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {21--41},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_2_a2/}
}
TY  - JOUR
AU  - I. L. Vasiliev
AU  - K. B. Klimentova
TI  - A branch and bound method for the facility location problem with customer preferences
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 21
EP  - 41
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_2_a2/
LA  - ru
ID  - DA_2009_16_2_a2
ER  - 
%0 Journal Article
%A I. L. Vasiliev
%A K. B. Klimentova
%T A branch and bound method for the facility location problem with customer preferences
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 21-41
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2009_16_2_a2/
%G ru
%F DA_2009_16_2_a2
I. L. Vasiliev; K. B. Klimentova. A branch and bound method for the facility location problem with customer preferences. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 2, pp. 21-41. http://geodesic.mathdoc.fr/item/DA_2009_16_2_a2/

[1] Alekseeva E. V., Kochetov Yu. A., “Geneticheskii lokalnyi poisk dlya zadachi o $p$-mediane s predpochteniyami klientov”, Diskret. analiz i issled. operatsii. Ser. 2, 14:1 (2007), 3–31 | MR

[2] Beresnev V. L., Diskretnye zadachi razmescheniya i polinomy ot bulevykh peremennykh, Izd-vo Instituta matematiki, Novosibirsk, 2005, 408 pp.

[3] Vasilev I. L., Klimentova K. B., Kochetov Yu. A., “Novye nizhnie otsenki dlya zadachi razmescheniya s predpochteniyami klientov”, Zhurn. vychisl. matematiki i mat. fiziki (to appear)

[4] Gorbachevskaya L. E., Polinomialno razreshimye i NP-trudnye dvukhurovnevye zadachi standartizatsii, Dis. $\dots$ kand. fiz.-mat. nauk, Novosibirsk, 1998, 131 pp.

[5] Gorbachevskaya L. E., Dementev V. T., Shamardin Yu. V., “Dvukhurovnevaya zadacha standartizatsii s usloviem edinstvennosti optimalnogo potrebitelskogo vybora”, Diskret. analiz i issled. operatsii. Ser. 2, 6:2 (1999), 3–11 | MR | Zbl

[6] Cánovas L., García S., Labbé M., Marín A., “A strengthened formulation for the simple plant location problem with order”, Operations Research Letters, 35:2 (2007), 141–150 | DOI | MR | Zbl

[7] Dempe S., Foundations of bilevel programming, Kluwer Acad. Publ., Dordrecht, 2002, 320 pp. | MR | Zbl

[8] Hanjoul P., Peeters D., “A facility location problem with clients' preference orderings”, Regional Sci. Urban Econom., 17 (1987), 451–473 | DOI

[9] Hansen P., Kochetov Y., Mladenovic N., Lower bounds for the uncapacitated facility location problem with user preferences, Les Charies du GERAD G–2004–24, 2004, 10 pp.

[10] Kirkpatrick S., Gelatt C. D., Vecchi M. P., “Optimization by simulated annealing”, Science, 220:4598 (1983), 671–680 | DOI | MR

[11] Kochetov Yu., Ivanenko D., “Computationally difficult instances for the uncapacitated facility location problem”, Metaheuristics: progress as real solvers, Springer, New York, 2005, 351–367

[12] Nemhauser G. N., Wolsey L. A., Integer and combinatiorial optimization, A Wiley-Interscience Publication, New York, 1999, 766 pp. | MR | Zbl

[13] Pochet Y., Wolsey L. A., Production planning by mixed integer programming, Springer-Verl., New York, 2006, 477 pp. | MR | Zbl

[14] Van Laarhoven P. J. M., Aarts E. H. L., Simulated annealing: theory and application, D. Reidel Publ. Comp., Dordrecht, 1988, 198 pp.

[15] http://www.dashoptimisation.com