Geodesic
The pricing problem. Part~I. Exact and approximate algorithms
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 5, pp. 83-100.

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

We consider the mill pricing problem which is shown to be NP-hard in the strong sense. To solve this problem, some exact and approximate algorithms based on decomposition, genetic local search, and tabu search are developed. Results of the computing experiments are given. Tab. 3, bibliogr. 25.
Keywords: NP-hard in the strong sense, the bilevel pricing problem, minimax problem, local search, tabu search, genetic algorithm, hybrid algorithm.
Mots-clés : decomposition 
@article{DA_2012_19_5_a5,
     author = {A. V. Plyasunov and A. A. Panin},
     title = {The pricing problem. {Part~I.} {Exact} and approximate algorithms},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {83--100},
     publisher = {mathdoc},
     volume = {19},
     number = {5},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_5_a5/}
}
TY  - JOUR
AU  - A. V. Plyasunov
AU  - A. A. Panin
TI  - The pricing problem. Part~I. Exact and approximate algorithms
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 83
EP  - 100
VL  - 19
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_5_a5/
LA  - ru
ID  - DA_2012_19_5_a5
ER  - 
%0 Journal Article
%A A. V. Plyasunov
%A A. A. Panin
%T The pricing problem. Part~I. Exact and approximate algorithms
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 83-100
%V 19
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_5_a5/
%G ru
%F DA_2012_19_5_a5
A. V. Plyasunov; A. A. Panin. The pricing problem. Part~I. Exact and approximate algorithms. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 5, pp. 83-100. http://geodesic.mathdoc.fr/item/DA_2012_19_5_a5/

[1] Vasilev F. P., Metody optimizatsii, Faktorial Press, M., 2002, 829 pp.

[2] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[3] Dementev V. T., Shamardin Yu. V., “Zadacha o vybore tsen na produktsiyu pri uslovii obyazatelnogo udovletvoreniya sprosa”, Diskret. analiz i issled. operatsii. Ser. 2, 9:2 (2002), 31–40 | MR | Zbl

[4] Panin A. A., “Geneticheskii algoritm dlya odnoi zadachi tsenoobrazovaniya”, Tr. IVMiMG SO RAN. Ser. Informatika, 9, 2009, 190–196

[5] Plyasunov A. V., “O vychislitelnykh vozmozhnostyakh metaevristik”, Mat. Ross. konf. “Diskretnaya optimizatsiya i issledovanie operatsii” (Vladivostok, 7–14 sentyabrya 2007 g.), Izd-vo In-ta matematiki, Novosibirsk, 2007, 61–68

[6] Plyasunov A. A., “Gibridnye metody resheniya slozhnykh kombinatornykh zadach, ispolzuyuschie dekompozitsiyu”, Sb. dokl. 8-i mezhdunar. konf. “Intellektualnaya obrabotka informatsii” (Respublika Kipr, Pafos, 17–24 oktyabrya, 2010 g.), MAKS Press, M., 2010, 286–289

[7] Alekseeva E., Kochetova N., Kochetov Yu., Plyasunov A., “A hybrid memetic algorithm for the competitive $p$-median problem”, Preprints 13th IFAC Symp. Information Control Problems in Manufacturing, Moscow, 2009, 1516–1520

[8] Alekseeva E. V., Kochetova N. A., Kochetov Yu. A., Plyasunov A. V., “A heuristic and exact methods for the dicrete $(r|p)$-centroid problem”, Lect. Notes Comput. Sci., 6022, Springer-Verl., Berlin, 2010, 11–22 | DOI

[9] Bouhtou M., Grigoriev A., Van Der Kraaij A. F., Van Hoesel S., Spieksma F., Uetz M., “Pricing bridges to cross a river”, Naval Res. Logistics, 54:4 (2007), 411–420 | DOI | MR | Zbl

[10] Chandru V., Hooker J. N., Optimization methods for logical inference, John Wiley Sons, New York, 1999, 365 pp. | MR

[11] Dechter R., Constraint processing, Morgan Kaufmann, San Francisco, 2003, 481 pp.

[12] Dempe S. J., Foundations of bilevel programming, Kluwer Acad. Publ., Dordrecht, 2002, 481 pp. | MR | Zbl

[13] Geoffrion A. V., “Generalized Benders decomposition”, J. Optimization Theory Appl., 10:4 (1972), 237–260 | DOI | MR | Zbl

[14] Gote G., Laughton M. A., “Large scale mixed integer programming: Benders-type heuristics”, Eur. J. Oper. Res., 16 (1984), 327–333 | DOI | MR

[15] Hanjoul P., Hansen P., Peeters D., Thisse J.-F., “Uncapacitated plant location under alternative spatial price policies”, Market Sci., 36 (1990), 41–57 | MR | Zbl

[16] Van Hentenryck P., Milano M., Hybrid optimization: the ten years of CPAIOR, Springer Sci.+Business Media, New York, 2011, 570 pp. | MR

[17] Hooker J. N., Integrated methods for optimization, Springer Sci.+Business Media, New York, 2007, 490 pp. | MR | Zbl

[18] Hooker J. N., Logic-based methods for optimization: combining optimization and constraint satisfaction, Wiley–Intersci., New York, 2000, 520 pp. | MR | Zbl

[19] Lodi A., Milano M., Toth P., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems, Lect. Notes Comput. Sci., 6140, Springer-Verl., Berlin, 2010, 369 pp. | DOI | Zbl

[20] Marriott K., Stuckey P., Programming with constraints: an introduction, The MIT Press, Cambridge, 1998, 476 pp. | MR

[21] McDaniel D., Devine M., “A modified Benders partitioning algorithm for mixed integer programming”, Manage. Sci., 24 (1977), 312–319 | DOI | Zbl

[22] Mirchandani P. D., Francis R. L., “Decomposition methods for facility location problems”, Discrete Location Theory, Wiley Sons, New York, 1990, 439–478 | MR

[23] Rebeiro C. C., Hansen P., Essays and surveys in metaheuristics, Kluwer Acad. Publ., Boston, 2002, 651 pp. | MR

[24] Vanderbeck F., Wolsey L. A., Reformulation and decomposition of integer programs, Center Oper. Res. Econometrics, Montreal, 2009, 71 pp.

[25] Vanderbeck F., Savelsbergh M. W. P., “A generic view of Dantzig–Wolfe decomposition for integer programming”, Oper. Res. Lett., 34 (2006), 296–306 | DOI | MR | Zbl