Deep cuts in concave and linear 0-1 programming

O. V. Khamisov

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 20 (2014) no. 2, pp. 294-304

Résumé

A technique for the construction of deep cuts in the global minimization problem for a continuously differentiable concave function on a polytope and in a Boolean programming problem is proposed. The introduced cuts are based constructively on the so-called best concave extension. The theoretical analysis is based on the properties of the image of the target function under the gradient mapping. Illustrative examples and results of a preliminary numerical experiment are presented.

Détail

Keywords: cutting plane, concave extension, recessive direction, global minimum.

Bibliographie

[1] Benson H., “Concave minimizition: theory, applications and algorithms”, Handbook of global optimization, eds. R. Horst, P. M. Pardalos, Kluwer Acad. Publ., Dordrecht, 1995, 43–148 | DOI | MR | Zbl

[2] Horst R., Tuy H., Global optimization: Deterministic approaches, Third revised and enlarged edition, Springer-Verlag, Berlin, 1996, 727 pp. | MR

[3] Pardalos P. M., Rosen J. B., Constrained global optimization. Algorithms and applications, Springer-Verlag, Berlin, 1987, 143 pp. | MR | Zbl

[4] Eremin I. I., Teoriya lineinoi optimizatsii, Izd-vo “Ekaterinburg”, Ekaterinburg, 1999, 312 pp.

[5] Eremin I. I., Dvoistvennost v lineinoi optimizatsii, Izd-vo UrO RAN, Ekaterinburg, 2001, 180 pp.

[6] Khedli Dzh., Nelineinoe i dinamicheskoe programmirovanie, Mir, M., 1967, 506 pp.

[7] Khachiyan L., Boros E., Borys K., Ellbassioni K., Gurvich V., “Generating all vertices of a polyhedron is hard”, Proc. of the seventeenth annual ACM-SIAM symposium on discrete algorithms (SODA-2006), 2006, 758–765 | DOI | MR | Zbl

[8] Linial N., “Hard enumeration problems in geometry and combinatorics”, SIAM J. Algebraic Discrete Methods, 7:2 (1986), 331–335 | DOI | MR | Zbl

[9] Rademacher L., “Approximating the centroid is hard”, Symposium on computational geometry (SCG'07), South Korea, Gyeongju, 2007, 302–305 | MR | Zbl

[10] Dyer M. E., Frieze A. M., “On the complexity of the computing the volume of a polyhedron”, SIAM J. Comput., 17:5 (1988), 967–974 | DOI | MR | Zbl

[11] Bulatov V. P., Metody pogruzheniya v zadachakh optimizatsii, Nauka, Novosibirsk, 1977, 159 pp. | MR

[12] Strekalovskii A. S., Elementy nevypukloi optimizatsii, Nauka, Novosibirsk, 2003, 336 pp.

[13] Rosen J. B., “Iterative solution of nonlinear optimal control problems”, SIAM J. Control, 4 (1966), 223–244 | DOI | MR | Zbl

[14] Bulatov V. P., Kasinskaya L. I., “Nekotorye metody minimizatsii vognutoi funktsii na vypuklom mnogogrannike i ikh prilozheniya”, Sb. “Metody optimizatsii i ikh prilozheniya”, eds. A. P. Merenkov, V. P. Bulatov, Nauka, Novosibirsk, 1982, 71–80 | MR

[15] Chinchuluun A., Enkhbat R., Pardalos P. M., “A numerical method for concave programming problem”, Continuous Optimization. Current Trends and Modern Applications, Appl. Optim., 99, eds. V. Jeyakumar, A. Rubinov, Springer, N.Y., 2005, 251–273 | DOI | MR | Zbl

[16] Bulatov V. P., “Metody resheniya mnogoekstremalnykh zadach (globalnyi poisk)”, Metody optimizatsii i ikh prilozheniya. Ch. 1. Matematicheskoe programmirovanie, Nauka, Novosibirsk, 1989, 131–157

[17] Porembski M., “How to extend the concept of convexity cuts to derive deeper cutting planes”, J. Global Optim., 15:4 (1999), 371–404 | DOI | MR | Zbl

[18] Porembski M., “Finitely convergent cutting planes for concave minimization”, J. Global Optim., 20 (2001), 113–136 | DOI | MR | Zbl

[19] Porembski M., “Cone adaptation strategies for a finite and exact cutting plane algorithm for concave minimization”, J. Global Optim., 24 (2002), 89–107 | DOI | MR | Zbl

[20] Bulatov V. P., Khamisov O. V., “Metody otsecheniya v $E^{n+1}$ dlya resheniya zadach globalnoi optimizatsii na odnom klasse funktsii”, Zhurn. vychisl. matematiki i mat. fiziki, 47:11 (2007), 1830–1842 | MR

[21] Rokafellar R., Vypuklyi analiz, Mir, M., 1973, 469 pp.

[22] Bulatov V. P., Khamisov O. V., “The cutting method in $E^{n+1}$ through concave extension for solving global extremum problem”, Proc. 21th conf. “Mathematische Optimierung”, Humboldt-Univ., Berlin, 1989, 16–19

[23] Dantzig G. B., “Note on solving linear programs in integers”, Naval. Res. Log. Quart., 6:1 (1959), 75–76 | DOI | MR

[24] Gomory R. E., An algorithm for integer solution to linear programs, Princeton – IBM Mathematics Research Project. Technical Report No 1, 1958

[25] Balas E., “Intersection cuts – a new type of cutting planes for integer programming”, Math. Oper. Res., 19:1 (1971), 19–39 | DOI | MR | Zbl

[26] Balas E., Bowman J. V., Glover F., Sommer D., “An intersection cut from the dual of the unit hypercube”, Math. Oper. Res., 19:1 (1971), 40–44 | DOI | MR | Zbl

[27] Korbut A. A., Finkelshtein Yu. Yu., Diskretnoe programmirovanie, Nauka, M., 1969, 368 pp. | MR | Zbl

[28] Shevchenko V. N., Kachestvennye voprosy tselochislennogo programmirovaniya, Nauka, M., 1995, 192 pp. | MR | Zbl

[29] Kolokolov A. A., “Regulyarnye razbieniya i otsecheniya v tselochislennom programmirovanii”, Sib. zhurn. issled. operatsii, 1:2 (1994), 18–39 | MR | Zbl