Geodesic
Piecewise convex formulations of binary and permutation problems
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 14 (2011) no. 4, pp. 409-423.

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

It is well-known that the problem of maximization of any difference of convex functions can be turned into a convex maximization problem; here the aim is a piecewise convex maximization problem instead. Although this may seem harder, sometimes the dimension may be reduced by 1, and the local search may be improved by using extreme points of the closure of the convex hull of better points. We show that it is always the case for both binary and permutation problems and give, as such instances, piecewise convex formulations for the maximum clique problem and the quadratic assignment problem. 
@article{SJVM_2011_14_4_a5,
     author = {D. Fortin and I. Tseveendorj},
     title = {Piecewise convex formulations of binary and permutation problems},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {409--423},
     publisher = {mathdoc},
     volume = {14},
     number = {4},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2011_14_4_a5/}
}
TY  - JOUR
AU  - D. Fortin
AU  - I. Tseveendorj
TI  - Piecewise convex formulations of binary and permutation problems
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2011
SP  - 409
EP  - 423
VL  - 14
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJVM_2011_14_4_a5/
LA  - ru
ID  - SJVM_2011_14_4_a5
ER  - 
%0 Journal Article
%A D. Fortin
%A I. Tseveendorj
%T Piecewise convex formulations of binary and permutation problems
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2011
%P 409-423
%V 14
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJVM_2011_14_4_a5/
%G ru
%F SJVM_2011_14_4_a5
D. Fortin; I. Tseveendorj. Piecewise convex formulations of binary and permutation problems. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 14 (2011) no. 4, pp. 409-423. http://geodesic.mathdoc.fr/item/SJVM_2011_14_4_a5/

[1] Adams W. P., Guignard M., Hahn P. M., Hightower W. L., “A level-2 reformulation-linearization technique bound for the quadratic assignment problem”, European J. Oper. Res., 180:3 (2007), 983–996 | DOI | MR | Zbl

[2] Bomze I. M., Budinich M., Pardalos P. M., Pelillo M., “The maximum clique problem”, Handbook of combinatorial optimization, Supplement Vol. A, Kluwer Acad. Publ., Dordrecht, 1999, 1–74 | MR

[3] de Klerk E., Pasechnik D. V., “Approximation of the stability number of a graph via copositive programming”, SIAM J. Optim., 12:4 (2002), 875–892 | DOI | MR | Zbl

[4] Flores-Bazán F., “On minima of the difference of functions”, J. Optim. Theory Appl., 93:3 (1997), 525–531 | DOI | MR | Zbl

[5] Fortin D., Tsevendorj I., “Maximum clique regularizations”, Optimization and optimal control (Ulaanbaatar, 2002), Ser. Comput. Oper. Res., 1, World Sci. Publ., NJ, River Edge, 2003, 103–119 | MR | Zbl

[6] Fortin D., Tsevendorj I., “Piecewise convex maximization approach to multiknapsack”, Optimization: A Journal of Mathematical Programming and Operations Research, 58 (2009), 883–895 | MR | Zbl

[7] Fortin D., Tsevendorj I., “A trust branching path heuristic for permutation problems”, International Journal of Pure and Applied Mathematics, 56:3 (2009), 329–343 | MR | Zbl

[8] Fortin D., Tsevendorj I., “Piecewise-convex maximization problems: algorithm and computational experiments”, J. Global Optim., 24:1 (2002), 61–77 | DOI | MR | Zbl

[9] Gibbons L. E., Hearn D. W., Pardalos P. M., Ramana M-V., “Continuous characterizations of the maximum clique problem”, Math. Oper. Res., 22:3 (1997), 754–768 | DOI | MR | Zbl

[10] Hadley S. W., Rendl F., Wolkowicz H., “A new lower bound via projection for the quadratic assignment problem”, Math. Oper. Res., 17:3 (1992), 727–739 | DOI | MR | Zbl

[11] Hiriart-Urruty J.-B., “From convex optimization to nonconvex optimization. Necessary and sufficient conditions for global optimality”, Nonsmooth optimization and related topics (Erice, 1988), Ettore Majorana Internat. Sci. Ser. Phys. Sci., 43, Plenum, New York, 1989, 219–239 | MR

[12] Hiriart-Urruty J.-B., “Global optimality conditions in maximizing a convex quadratic function under convex quadratic constraints”, J. Global Optim., 21:4 (2001), 445–455 | DOI | MR

[13] Horst R., Thoai N. V., “On an optimality condition in DC optimization”, J. Optim. Theory Appl., 103:1 (1999), 1–43 ; “Errata to: DC programming: overview”, J. Optim. Theory Appl., 121:1 (2004), 211 | DOI | MR | DOI | MR | Zbl

[14] Kuznetsova A., Strekalovsky A. S., “On solving the maximum clique problem”, J. Global Optim., 21:3, International Workshop on Global Optimization, Part III (Florence, 1999) (2001), 265–288 | DOI | MR | Zbl

[15] Motzkin T. S., Straus E. G., “Maxima for graphs and a new proof of a theorem of Turán”, Canad. J. Math., 17 (1965), 533–540 | DOI | MR | Zbl

[16] Sherali H. D., Adams W. P., “A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems”, SIAM J. Discrete Math., 3:3 (1990), 411–430 | DOI | MR | Zbl

[17] Strekalovsky A. S., “Global optimality conditions for nonconvex optimization”, J. Global Optim., 12:4 (1998), 415–434 | DOI | MR | Zbl

[18] Strekalovsky A. S., Orlov A. V., “A new approach to nonconvex optimization”, Num. Methods and Prog., 8 (2007), 160–176

[19] Tsevendorj I., “Piecewise-convex maximization problems: global optimality conditions”, J. Global Optim., 21:1 (2001), 1–14 | DOI | MR | Zbl

[20] Tuy H., Convex analysis and global optimization, Nonconvex Optimization and its Applications, 22, Kluwer Academic Publishers, Dordrecht, 1998 | MR | Zbl

[21] Vassiliev I. L., “About the experience of the solution of the assignment problem”, Optimizatsiya, upravlenie, intellekt, 1999, no. 3, 133–151

[22] Xia Y., “Second order cone programming relaxation for quadratic assignment problems”, Optim. Methods Softw., 23:3 (2008), 441–449 | DOI | MR | Zbl

[23] Xia Y., “Two-dimensional second-order cone programming”, Int. J. Oper. Res., 5:4 (2009), 468–484 | DOI | MR | Zbl

[24] Xia Y., Yuan Y-X., “A new linearization method for quadratic assignment problems”, Optim. Methods Softw., 21:5 (2006), 805–818 | DOI | MR | Zbl