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.
Mots-clés : 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, Tome 43 (2009) no. 1, pp. 55-85. doi : 10.1051/ro/2009005. http://archive.numdam.org/articles/10.1051/ro/2009005/
[1] and , A tight linearization and an algorithm for 0-1 quadratic programming problems. Manage. Sci. 32 (1986) 1274-1290. | MR | Zbl
[2] and , 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] , and , Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs. Discrete Optim. 1 (2004) 99-120. | MR | Zbl
[4] , , and , A global optimization method, BB, for general twice-differentiable constrained NLPs: I. Theoretical advances. Comput. Chem. Eng. 22 (1998) 1137-1158.
[5] , and , A global optimization method, BB, for general twice-differentiable constrained NLPs: II. Implementation and computational results. Comput. Chem. Eng. 22 (1998) 1159-1179.
[6] and , Jointly constrained biconvex programming. Math. Oper. Res. 8 (1983) 273-286. | MR | Zbl
[7] , Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (1995) 13-51. | MR | Zbl
[8] , Recent advances in the solution of quadratic assignment problems. Math. Program. B 97 (2003) 27-42. | MR | Zbl
[9] , , and , Links between linear bilevel and mixed 0-1 programming problems. J. Optim. Theor. Appl. 93 (1997) 273-300. | MR | Zbl
[10] , , , and , Pooling problem: Alternate formulations and solution methods. Manage. Sci. 50 (2004) 761-776.
[11] , and , Stabilization in column generation. Discrete Appl. Math. to appear.
[12] and , Routing of uncertain demands. Optim. Eng. 3 (2005) 283-313. | MR | Zbl
[13] and , The price of robustness. Oper. Res. 52 (2004) 35-53. | MR | Zbl
[14] and , Using a mixed-integer quadratic programming solver for the unconstrained quadratic 0-1 problem. Math. Program. 109 (2007) 55-68. | MR
[15] , and , 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] and , Automated reformulation of disjunctive constraints in MINLP optimization. Comput. Chem. Eng. 23 (1999) S11-S14.
[17] , and , Some convexifications in global optimization of problems containing signomial terms. Comput. Chem. Eng. 27 (2003) 669-679.
[18] , and , GAMS, a user's guide. ACM SIGNUM Newsletter, 23 (1988) 10-11.
[19] , Linear Programming and Extensions. Princeton University Press, Princeton, NJ (1963). | MR | Zbl
[20] , , and , Towards the optimal solution of the multiprocessor scheduling problem with communication delays, in MISTA Proceedings (2007).
[21] , Mathematical programming methods in dynamical nonlinear stochastic Supply Chain management. Ph.D. thesis, DSPSA, Università di Roma “La Sapienza" (2007).
[22] and , On bilevel programming, part i: general nonlinear cases. Mathem. Program. 70 (1995) 47-72. | MR | Zbl
[23] and , User manual for filter. Technical report, University of Dundee, UK (1999).
[24] , Applications de l'algèbre de boole en recherche opérationelle. Revue Française de Recherche Opérationelle 4 (1960) 17-26.
[25] , Personal communication (2004).
[26] and , The AMPL Book. Duxbury Press, Pacific Grove (2002).
[27] , , and , Optimization services 1.0 user manual. Technical report, COIN-OR (2007).
[28] , 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] , Parsing AMPL internal format for linear and non-linear expressions. Didactical project, DEI, Politecnico di Milano, Italy (2004).
[30] , User's Guide for SNOPT 5.3. Systems Optimization Laboratory, Department of EESOR, Stanford University, California (1999).
[31] , and , Disciplined convex programming, in Liberti and Maculan [56], 155-210. | MR | Zbl
[32] , and , Applications of optimization with Xpress-MP. Dash optimization. Bilsworth (2000).
[33] and , A linearization framework for unconstrained quadratic (0-1) problems. Discrete Appl. Math., to appear. | MR | Zbl
[34] and , “miniaturized" linearizations for quadratic 0/1 problems". Ann. Oper. Res. 140 (2005) 235-261. | MR | Zbl
[35] , and , Computing global minima to polynomial optimization problems using Gröbner bases. J. Glob. Optim. 7 (1995) 115-125. | MR | Zbl
[36] and , Boolean Methods in Operations Research and Related Areas. Springer, Berlin (1968). | MR | Zbl
[37] , Method of non-linear 0-1 programming. Ann. Discrete Math. 5 (1979) 53-70.
[38] and , Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem. Discrete Appl. Math., to appear. | MR | Zbl
[39] , On the convexification of nonlinear programming problems: an applications-oriented approach. Eur. J. Oper. Res. 15 (1984) 382-392. | MR | Zbl
[40] and , Global Optimization: Deterministic Approaches. Springer-Verlag, Berlin, 3rd ed. (1996). | MR | Zbl
[41] , and , 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] and , 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] , and , An interior point potential reduction algorithm for the linear complementarity problem. Math. Program. 54 (1992) 267-279. | MR | Zbl
[45] . 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] , Reduction constraints for the global optimization of NLPs. Int. Trans. Oper. Res. 11 (2004) 34-41. | MR | Zbl
[47] , Reformulation and Convex Relaxation Techniques for Global Optimization. Ph.D. thesis, Imperial College London, UK, (2004).
[48] , Reformulation and convex relaxation techniques for global optimization. 4OR 2 (2004) 255-258. | Zbl
[49] , Linearity embedded in nonconvex programs. J. Glob. Optim.n 33 (2005) 157-196. | MR | Zbl
[50] , Writing global optimization software, in Global Optimization: from Theory to Implementation, edited by Liberti and Maculan.Springer, berlin (2006) 211-262. | MR | Zbl
[51] , Reformulation techniques in mathematical programming, Thèse d'Habilitation à Diriger des Recherches, Université de Paris-Dauphine (2007).
[52] , Compact linearization of binary quadratic problems. 4OR 5 231-245 (2007). | MR
[53] , 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] and , Convex envelopes of monomials of odd degree. J. Glob. Optim. 25 (2003) 157-168. | MR | Zbl
[55] and , An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms. J. Glob. Optim. 36 (2006) 161-189. | MR | Zbl
[56] and , Eds., Global Optimization: from Theory to Implementation. Springer, Berlin (2006). | MR | Zbl
[57] , , and , Mathematical models and a constructive heuristic for finding minimum fundamental cycle bases. Yugosl. J. Oper. Res. 15 (2005) 15-24. | MR
[58] , , and , Reformulation in mathematical programming: an application to quantum chemistry. Discrete Appl. Math. to appear. | MR | Zbl
[59] , , and , Expressing combinatorial optimization problems by systems of polynomial equations and the nullstellensatz, Technical Report RC24276(W0706-020), IBM Corporation (2007).
[60] , 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] , Linear complementarity problems solvable by a single linear program. Math. Program. 10 (1976) 263-270. | MR | Zbl
[62] , The linear complementarity problem as a separable bilinear program. J. Glob. Optim. 6 (1995) 153-161. | MR | Zbl
[63] , Pruning by isomorphism in branch-and-cut. Math. Program. 94 (2002) 71-90. | MR | Zbl
[64] , Exploiting orbits in symmetric ilp. Math. Program. B 98 (2003) 3-21. | MR | Zbl
[65] , Computability of global solutions to factorable nonconvex programs: Part I - Convex underestimating problems. Math. Program. 10 (1976) 146-175. | MR | Zbl
[66] and , Convex hull of trilinear monomials with mixed sign domains. J. Glob. Optim. 29 (2004) 125-155. | MR | Zbl
[67] , and , Reformulation descent applied to circle packing problems. Comput. Oper. Res. 32 (2005) 2419-2434. | Zbl
[68] , Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming. Birkhäuser, Basel (2005). | MR | Zbl
[69] , , and , Mixed integer linear/nonlinear programming interface specification, Global Cape-Open Deliverable WP2.3-04 (2002).
[70] , Reformulations quadratiques convexes pour la programmation quadratique en variables 0-1. Ph.D. thesis, Conservatoire National d'Arts et Métiers (2006).
[71] and , Relaxation guided variable neighbourhood search, in Proc. of Mini Euro Conference on Variable Neighbourhood Search, Tenerife, Spain (2005).
[72] , and , MIP reformulations of the probabilistic set covering problem. Technical Report 2007-02-1579, Optimization Online (2007).
[73] , Global optimization of nonconvex polynomial programming problems having rational exponents. J. Glob. Optim. 12 (1998) 267-283. | MR | Zbl
[74] , Personal communication (2007).
[75] and , A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishers, Dodrecht (1999). | MR | Zbl
[76] and , 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] and , 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] and , A new reformulation-linearization technique for bilinear programming problems. J. Global Optimization 2 (1992) 379-410. | MR | Zbl
[79] and , Reformulation-linearization methods for global optimization, in Encyclopedia of Optimization, edited by C. Floudas and P. Pardalos. Springer, New York, to appear.
[80] and , Improving discrete model representations via symmetry considerations. Manag. Sci. 47 1396-1407.
[81] and , New reformulation linearization/convexification relaxations for univariate and multivariate polynomial programming problems. Oper. Res. Lett. 21 (1997) 1-9. | MR | Zbl
[82] and , A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. J. Glob. Optim. 2 (1991) 101-112. | MR | Zbl
[83] and , Global optimization of nonconvex factorable programming problems. Math. Program. 89 (2001) 459-478. | MR | Zbl
[84] , On the Optimal Design of Continuous Processes. Ph.D. thesis, Imperial College of Science, Technology and Medicine, University of London (1996).
[85] and , Global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 21 (1997) S791-S796.
[86] and , 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] , Extremal problems with d.c. constraints. Comput. Mathem. Math. Phys. 41 (2001) 1742-1751. | Zbl
[89] , On global optimality conditions for d.c. programming problems, Technical Paper, Irkutsk State University (1997).
[90] , Existence and sum decomposition of vertex polyhedral convex envelopes. Optim. Lett. 2 (2008) 363-375. | MR | Zbl
[91] and , Convex extensions and envelopes of semi-continuous functions. Math. Program. 93 (2002) 247-263. | MR | Zbl
[92] and , Global optimization of mixed integer nonlinear programs: A theoretical and computational study. Math. Program. 99 (2004) 563-591. | MR | Zbl
[93] , Semidefinite optimization. Acta Numerica 10 (2001) 515-560. | MR | Zbl
[94] , 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] and , Solving mixed integer programming problems using automatic reformulation. Oper. Res. 35 (1987) 45-57. | MR | Zbl
[96] , and , Exploiting equalities in polynomial programming, Technical Report 2006-05-1338, Optimization Online, 2006.
[97] and , A multivariate global optimization using linear bounding functions. J. Glob. Optim. 12 (1998) 383-404. | MR | Zbl
[98] , 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] , Integer Programming. Wiley, New York (1998). | MR | Zbl
Cité par Sources :
