Reformulations in mathematical programming : definitions and systematics
RAIRO - Operations Research - Recherche Opérationnelle, Volume 43 (2009) no. 1, pp. 55-85.

A reformulation of a mathematical program is a formulation which shares some properties with, but is in some sense better than, the original program. Reformulations are important with respect to the choice and efficiency of the solution algorithms; furthermore, it is desirable that reformulations can be carried out automatically. Reformulation techniques are widespread in mathematical programming but interestingly they have never been studied under a unified framework. This paper attempts to move some steps in this direction. We define a framework for storing and manipulating mathematical programming formulations and give several fundamental definitions categorizing useful reformulations in essentially four types (opt-reformulations, narrowings, relaxations and approximations). We establish some theoretical results and give reformulation examples for each type.

DOI: 10.1051/ro/2009005
Classification: 90C11, 90C26, 90C27, 90C30, 90C99
Keywords: reformulation, formulation, model, linearization, mathematical program
@article{RO_2009__43_1_55_0,
     author = {Liberti, Leo},
     title = {Reformulations in mathematical programming : definitions and systematics},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {55--85},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {1},
     year = {2009},
     doi = {10.1051/ro/2009005},
     mrnumber = {2502325},
     zbl = {1158.90390},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2009005/}
}
TY  - JOUR
AU  - Liberti, Leo
TI  - Reformulations in mathematical programming : definitions and systematics
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2009
SP  - 55
EP  - 85
VL  - 43
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2009005/
DO  - 10.1051/ro/2009005
LA  - en
ID  - RO_2009__43_1_55_0
ER  - 
%0 Journal Article
%A Liberti, Leo
%T Reformulations in mathematical programming : definitions and systematics
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2009
%P 55-85
%V 43
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2009005/
%R 10.1051/ro/2009005
%G en
%F RO_2009__43_1_55_0
Liberti, Leo. Reformulations in mathematical programming : definitions and systematics. RAIRO - Operations Research - Recherche Opérationnelle, Volume 43 (2009) no. 1, pp. 55-85. doi : 10.1051/ro/2009005. http://archive.numdam.org/articles/10.1051/ro/2009005/

[1] W.P. Adams and H.D. Sherali, A tight linearization and an algorithm for 0-1 quadratic programming problems. Manage. Sci. 32 (1986) 1274-1290. | MR | Zbl

[2] W.P. Adams and H.D. Sherali, A hierarchy of relaxations leading to the convex hull representation for general discrete optimization problems. Ann. Oper. Res. 140 (2005) 21-47. | MR | Zbl

[3] W.P. Adams, R.J. Forrester and F.W. Glover, Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs. Discrete Optim. 1 (2004) 99-120. | MR | Zbl

[4] C.S. Adjiman, S. Dallwig, C.A. Floudas and A. Neumaier, A global optimization method, αBB, for general twice-differentiable constrained NLPs: I. Theoretical advances. Comput. Chem. Eng. 22 (1998) 1137-1158.

[5] C.S. Adjiman, I.P. Androulakis and C.A. Floudas, A global optimization method, αBB, for general twice-differentiable constrained NLPs: II. Implementation and computational results. Comput. Chem. Eng. 22 (1998) 1159-1179.

[6] F.A. Al-Khayyal and J.E. Falk, Jointly constrained biconvex programming. Math. Oper. Res. 8 (1983) 273-286. | MR | Zbl

[7] F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (1995) 13-51. | MR | Zbl

[8] K.M. Anstreicher, Recent advances in the solution of quadratic assignment problems. Math. Program. B 97 (2003) 27-42. | MR | Zbl

[9] C. Audet, P. Hansen, B. Jaumard and G. Savard, Links between linear bilevel and mixed 0-1 programming problems. J. Optim. Theor. Appl. 93 (1997) 273-300. | MR | Zbl

[10] C. Audet, J. Brimberg, P. Hansen, S. Le Digabel and N. Mladenović, Pooling problem: Alternate formulations and solution methods. Manage. Sci. 50 (2004) 761-776.

[11] H.M.T. Ben Amor, J. Desrosiers and A. Frangioni, Stabilization in column generation. Discrete Appl. Math. to appear.

[12] W. Ben-Ameur and H. Kerivin, Routing of uncertain demands. Optim. Eng. 3 (2005) 283-313. | MR | Zbl

[13] D. Bertsimas and M. Sym, The price of robustness. Oper. Res. 52 (2004) 35-53. | MR | Zbl

[14] A. Billionnet and S. Elloumi, Using a mixed-integer quadratic programming solver for the unconstrained quadratic 0-1 problem. Math. Program. 109 (2007) 55-68. | MR

[15] A. Billionnet, S. Elloumi and M.-C. Plateau, Improving the performance of standard solvers via a tighter convex reformulation of constrained quadratic 0-1 programs: the QCR method. Discrete Appl. Math., to appear. | MR | Zbl

[16] J. Bjorkqvist and T. Westerlund, Automated reformulation of disjunctive constraints in MINLP optimization. Comput. Chem. Eng. 23 (1999) S11-S14.

[17] K.-M. Björk, P.O. Lindberg and T. Westerlund, Some convexifications in global optimization of problems containing signomial terms. Comput. Chem. Eng. 27 (2003) 669-679.

[18] A. Brook, D. Kendrick and A. Meeraus, GAMS, a user's guide. ACM SIGNUM Newsletter, 23 (1988) 10-11.

[19] G.B. Dantzig, Linear Programming and Extensions. Princeton University Press, Princeton, NJ (1963). | MR | Zbl

[20] T. Davidović, L. Liberti, N. Maculan and N. Mladenović, Towards the optimal solution of the multiprocessor scheduling problem with communication delays, in MISTA Proceedings (2007).

[21] L. Di Giacomo, Mathematical programming methods in dynamical nonlinear stochastic Supply Chain management. Ph.D. thesis, DSPSA, Università di Roma “La Sapienza" (2007).

[22] J.E. Falk and J. Liu, On bilevel programming, part i: general nonlinear cases. Mathem. Program. 70 (1995) 47-72. | MR | Zbl

[23] R. Fletcher and S. Leyffer, User manual for filter. Technical report, University of Dundee, UK (1999).

[24] R. Fortet, Applications de l'algèbre de boole en recherche opérationelle. Revue Française de Recherche Opérationelle 4 (1960) 17-26.

[25] R. Fourer, Personal communication (2004).

[26] R. Fourer and D. Gay, The AMPL Book. Duxbury Press, Pacific Grove (2002).

[27] R. Fourer, J. Ma, K. Martin and W. Sheng, Optimization services 1.0 user manual. Technical report, COIN-OR (2007).

[28] A. Frangioni, On a new class of bilevel programming problems and its use for reformulating mixed-integer problems. Eur. J. Oper. Res. 82 (1995) 615-646. | Zbl

[29] S. Galli, Parsing AMPL internal format for linear and non-linear expressions. Didactical project, DEI, Politecnico di Milano, Italy (2004).

[30] P.E. Gill, User's Guide for SNOPT 5.3. Systems Optimization Laboratory, Department of EESOR, Stanford University, California (1999).

[31] M. Grant, S. Boyd and Y. Ye, Disciplined convex programming, in Liberti and Maculan [56], 155-210. | MR | Zbl

[32] C. Guéret, C. Prins and M. Sevaux, Applications of optimization with Xpress-MP. Dash optimization. Bilsworth (2000).

[33] S. Gueye and Ph. Michelon, A linearization framework for unconstrained quadratic (0-1) problems. Discrete Appl. Math., to appear. | MR | Zbl

[34] S. Gueye and P. Michelon, “miniaturized" linearizations for quadratic 0/1 problems". Ann. Oper. Res. 140 (2005) 235-261. | MR | Zbl

[35] K. Hägglöf, P.O. Lindberg and L. Svensson, Computing global minima to polynomial optimization problems using Gröbner bases. J. Glob. Optim. 7 (1995) 115-125. | MR | Zbl

[36] P.L. Hammer and S. Rudeanu, Boolean Methods in Operations Research and Related Areas. Springer, Berlin (1968). | MR | Zbl

[37] P. Hansen, Method of non-linear 0-1 programming. Ann. Discrete Math. 5 (1979) 53-70.

[38] P. Hansen and C. Meyer, Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem. Discrete Appl. Math., to appear. | MR | Zbl

[39] R. Horst, On the convexification of nonlinear programming problems: an applications-oriented approach. Eur. J. Oper. Res. 15 (1984) 382-392. | MR | Zbl

[40] R. Horst and Hoang Tuy, Global Optimization: Deterministic Approaches. Springer-Verlag, Berlin, 3rd ed. (1996). | MR | Zbl

[41] K.-L. Hsiung, S.-J. Kim and S. Boyd, Tractable approximate robust geometric programming. Optim. Eng. to appear. | MR | Zbl

[42] ILOG, ILOG CPLEX 10.0 User's Manual. ILOG S.A., Gentilly, France (2005).

[43] J. Judice and G. Mitra, Reformulation of mathematical programming problems as linear complementarity problems and investigation of their solution methods. J. Optim. Theor. Appl. 57 (1988) 123-149. | MR | Zbl

[44] M. Kojima, N. Megiddo and Y. Ye, An interior point potential reduction algorithm for the linear complementarity problem. Math. Program. 54 (1992) 267-279. | MR | Zbl

[45] L. Liberti. Comparison of convex relaxations for monomials of odd degree, in Optimization and Optimal Control, edited by I. Tseveendorj, P.M. Pardalos and R. Enkhbat. World Scientific (2003). | MR | Zbl

[46] L. Liberti, Reduction constraints for the global optimization of NLPs. Int. Trans. Oper. Res. 11 (2004) 34-41. | MR | Zbl

[47] L. Liberti, Reformulation and Convex Relaxation Techniques for Global Optimization. Ph.D. thesis, Imperial College London, UK, (2004).

[48] L. Liberti, Reformulation and convex relaxation techniques for global optimization. 4OR 2 (2004) 255-258. | Zbl

[49] L. Liberti, Linearity embedded in nonconvex programs. J. Glob. Optim.n 33 (2005) 157-196. | MR | Zbl

[50] L. Liberti, Writing global optimization software, in Global Optimization: from Theory to Implementation, edited by Liberti and Maculan.Springer, berlin (2006) 211-262. | MR | Zbl

[51] L. Liberti, Reformulation techniques in mathematical programming, Thèse d'Habilitation à Diriger des Recherches, Université de Paris-Dauphine (2007).

[52] L. Liberti, Compact linearization of binary quadratic problems. 4OR 5 231-245 (2007). | MR

[53] L. Liberti, Automatic generation of symmetry-breaking constraints, in COCOA Proceedings, Lecture Notes in Computer Science, edited by B. Yang, D.-Z. Du and C.A. Wang 5165. Springer, Berlin (2008) 328-338. | Zbl

[54] L. Liberti and C.C. Pantelides, Convex envelopes of monomials of odd degree. J. Glob. Optim. 25 (2003) 157-168. | MR | Zbl

[55] L. Liberti and C.C. Pantelides, An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms. J. Glob. Optim. 36 (2006) 161-189. | MR | Zbl

[56] L. Liberti and N. Maculan, Eds., Global Optimization: from Theory to Implementation. Springer, Berlin (2006). | MR | Zbl

[57] L. Liberti, E. Amaldi, N. Maculan and F. Maffioli, Mathematical models and a constructive heuristic for finding minimum fundamental cycle bases. Yugosl. J. Oper. Res. 15 (2005) 15-24. | MR

[58] L. Liberti, C. Lavor, M.A.C. Nascimento and N. Maculan, Reformulation in mathematical programming: an application to quantum chemistry. Discrete Appl. Math. to appear. | MR | Zbl

[59] J.A. De Loera, J. Lee, S. Margulies and S. Onn, Expressing combinatorial optimization problems by systems of polynomial equations and the nullstellensatz, Technical Report RC24276(W0706-020), IBM Corporation (2007).

[60] R. Lougee-Heimer, The common optimization interface for operations research: Promoting open-source software in the operations research community. IBM J. Res. Dev. 47 (2003) 57-66.

[61] O.L. Mangasarian, Linear complementarity problems solvable by a single linear program. Math. Program. 10 (1976) 263-270. | MR | Zbl

[62] O.L. Mangasarian, The linear complementarity problem as a separable bilinear program. J. Glob. Optim. 6 (1995) 153-161. | MR | Zbl

[63] F. Margot, Pruning by isomorphism in branch-and-cut. Math. Program. 94 (2002) 71-90. | MR | Zbl

[64] F. Margot, Exploiting orbits in symmetric ilp. Math. Program. B 98 (2003) 3-21. | MR | Zbl

[65] G.P. Mccormick, Computability of global solutions to factorable nonconvex programs: Part I - Convex underestimating problems. Math. Program. 10 (1976) 146-175. | MR | Zbl

[66] C.A. Meyer and C.A. Floudas, Convex hull of trilinear monomials with mixed sign domains. J. Glob. Optim. 29 (2004) 125-155. | MR | Zbl

[67] N. Mladenović, F. Plastria and D. Urošević, Reformulation descent applied to circle packing problems. Comput. Oper. Res. 32 (2005) 2419-2434. | Zbl

[68] I. Nowak, Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming. Birkhäuser, Basel (2005). | MR | Zbl

[69] C.C. Pantelides, L. Liberti, P. Tsiakis and T. Crombie, Mixed integer linear/nonlinear programming interface specification, Global Cape-Open Deliverable WP2.3-04 (2002).

[70] M.-C. Plateau, Reformulations quadratiques convexes pour la programmation quadratique en variables 0-1. Ph.D. thesis, Conservatoire National d'Arts et Métiers (2006).

[71] J. Puchinger and G.R. Raidl, Relaxation guided variable neighbourhood search, in Proc. of Mini Euro Conference on Variable Neighbourhood Search, Tenerife, Spain (2005).

[72] A. Saxena, V. Goyal and M. Lejeune, MIP reformulations of the probabilistic set covering problem. Technical Report 2007-02-1579, Optimization Online (2007).

[73] H.D. Sherali, Global optimization of nonconvex polynomial programming problems having rational exponents. J. Glob. Optim. 12 (1998) 267-283. | MR | Zbl

[74] H. Sherali, Personal communication (2007).

[75] H.D. Sherali and W.P. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishers, Dodrecht (1999). | MR | Zbl

[76] H.D. Sherali and W.P. Adams, A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discrete Appl. Math. 52 (1994) 83-106. | MR | Zbl

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

[78] H.D. Sherali and A. Alameddine, A new reformulation-linearization technique for bilinear programming problems. J. Global Optimization 2 (1992) 379-410. | MR | Zbl

[79] H. Sherali and L. Liberti, Reformulation-linearization methods for global optimization, in Encyclopedia of Optimization, edited by C. Floudas and P. Pardalos. Springer, New York, to appear.

[80] H.D. Sherali and C. Smith, Improving discrete model representations via symmetry considerations. Manag. Sci. 47 1396-1407.

[81] H. Sherali and C.H. Tuncbilek, New reformulation linearization/convexification relaxations for univariate and multivariate polynomial programming problems. Oper. Res. Lett. 21 (1997) 1-9. | MR | Zbl

[82] H. Sherali and C.H. Tuncbilek, A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. J. Glob. Optim. 2 (1991) 101-112. | MR | Zbl

[83] H.D. Sherali and H. Wang, Global optimization of nonconvex factorable programming problems. Math. Program. 89 (2001) 459-478. | MR | Zbl

[84] E.M.B. Smith, On the Optimal Design of Continuous Processes. Ph.D. thesis, Imperial College of Science, Technology and Medicine, University of London (1996).

[85] E.M.B. Smith and C.C. Pantelides, Global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 21 (1997) S791-S796.

[86] E.M.B. Smith and C.C. Pantelides, A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 23 (1999) 457-478.

[87] INFORMS Computing Society. The mathematical programming glossary. http://glossary.computing.society.informs.org/second.php?page=R.html.

[88] A.S. Strekalovsky, Extremal problems with d.c. constraints. Comput. Mathem. Math. Phys. 41 (2001) 1742-1751. | Zbl

[89] A.S. Strekalovsky, On global optimality conditions for d.c. programming problems, Technical Paper, Irkutsk State University (1997).

[90] F. Tardella, Existence and sum decomposition of vertex polyhedral convex envelopes. Optim. Lett. 2 (2008) 363-375. | MR | Zbl

[91] M. Tawarmalani and N. Sahinidis, Convex extensions and envelopes of semi-continuous functions. Math. Program. 93 (2002) 247-263. | MR | Zbl

[92] M. Tawarmalani and N.V. Sahinidis, Global optimization of mixed integer nonlinear programs: A theoretical and computational study. Math. Program. 99 (2004) 563-591. | MR | Zbl

[93] M.J. Todd, Semidefinite optimization. Acta Numerica 10 (2001) 515-560. | MR | Zbl

[94] H. Tuy, D.C. optimization: Theory, methods and algorithms. in Handbook of Global Optimization , 1, edited by R. Horst and P.M. Pardalos. Kluwer Academic Publishers, Dordrecht (1995) 149-216. | MR | Zbl

[95] T.J. Van Roy and L.A. Wolsey, Solving mixed integer programming problems using automatic reformulation. Oper. Res. 35 (1987) 45-57. | MR | Zbl

[96] J.C. Vera, J.F. Pena and L.F. Zuluaa, Exploiting equalities in polynomial programming, Technical Report 2006-05-1338, Optimization Online, 2006.

[97] X. Wang and T.S. Change, A multivariate global optimization using linear bounding functions. J. Glob. Optim. 12 (1998) 383-404. | MR | Zbl

[98] T. Westerlund, Some transformation techniques in global optimization, in Global optimization: from theory to implementation, edited by L. Liberti and N. Maculan. Springer, Berlin (2006) 45-74. | MR | Zbl

[99] L.A. Wolsey, Integer Programming. Wiley, New York (1998). | MR | Zbl

Cited by Sources: