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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro/2009005/
[1] A tight linearization and an algorithm for 0-1 quadratic programming problems. Manage. Sci. 32 (1986) 1274-1290. | MR | Zbl
and ,[2] A hierarchy of relaxations leading to the convex hull representation for general discrete optimization problems. Ann. Oper. Res. 140 (2005) 21-47. | MR | Zbl
and ,[3] Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs. Discrete Optim. 1 (2004) 99-120. | MR | Zbl
, and ,[4] A global optimization method, BB, for general twice-differentiable constrained NLPs: I. Theoretical advances. Comput. Chem. Eng. 22 (1998) 1137-1158.
, , and ,[5] A global optimization method, BB, for general twice-differentiable constrained NLPs: II. Implementation and computational results. Comput. Chem. Eng. 22 (1998) 1159-1179.
, and ,[6] Jointly constrained biconvex programming. Math. Oper. Res. 8 (1983) 273-286. | MR | Zbl
and ,[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] Links between linear bilevel and mixed 0-1 programming problems. J. Optim. Theor. Appl. 93 (1997) 273-300. | MR | Zbl
, , and ,[10] Pooling problem: Alternate formulations and solution methods. Manage. Sci. 50 (2004) 761-776.
, , , and ,[11] Stabilization in column generation. Discrete Appl. Math. to appear.
, and ,[12] Routing of uncertain demands. Optim. Eng. 3 (2005) 283-313. | MR | Zbl
and ,[13] The price of robustness. Oper. Res. 52 (2004) 35-53. | MR | Zbl
and ,[14] Using a mixed-integer quadratic programming solver for the unconstrained quadratic 0-1 problem. Math. Program. 109 (2007) 55-68. | MR
and ,[15] 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
, and ,[16] Automated reformulation of disjunctive constraints in MINLP optimization. Comput. Chem. Eng. 23 (1999) S11-S14.
and ,[17] Some convexifications in global optimization of problems containing signomial terms. Comput. Chem. Eng. 27 (2003) 669-679.
, and ,[18] GAMS, a user's guide. ACM SIGNUM Newsletter, 23 (1988) 10-11.
, and ,[19] Linear Programming and Extensions. Princeton University Press, Princeton, NJ (1963). | MR | Zbl
,[20] Towards the optimal solution of the multiprocessor scheduling problem with communication delays, in MISTA Proceedings (2007).
, , and ,[21] Mathematical programming methods in dynamical nonlinear stochastic Supply Chain management. Ph.D. thesis, DSPSA, Università di Roma “La Sapienza" (2007).
,[22] On bilevel programming, part i: general nonlinear cases. Mathem. Program. 70 (1995) 47-72. | MR | Zbl
and ,[23] User manual for filter. Technical report, University of Dundee, UK (1999).
and ,[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] The AMPL Book. Duxbury Press, Pacific Grove (2002).
and ,[27] Optimization services 1.0 user manual. Technical report, COIN-OR (2007).
, , and ,[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] Disciplined convex programming, in Liberti and Maculan [56], 155-210. | MR | Zbl
, and ,[32] Applications of optimization with Xpress-MP. Dash optimization. Bilsworth (2000).
, and ,[33] A linearization framework for unconstrained quadratic (0-1) problems. Discrete Appl. Math., to appear. | MR | Zbl
and ,[34] “miniaturized" linearizations for quadratic 0/1 problems". Ann. Oper. Res. 140 (2005) 235-261. | MR | Zbl
and ,[35] Computing global minima to polynomial optimization problems using Gröbner bases. J. Glob. Optim. 7 (1995) 115-125. | MR | Zbl
, and ,[36] Boolean Methods in Operations Research and Related Areas. Springer, Berlin (1968). | MR | Zbl
and ,[37] Method of non-linear 0-1 programming. Ann. Discrete Math. 5 (1979) 53-70.
,[38] Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem. Discrete Appl. Math., to appear. | MR | Zbl
and ,[39] On the convexification of nonlinear programming problems: an applications-oriented approach. Eur. J. Oper. Res. 15 (1984) 382-392. | MR | Zbl
,[40] Global Optimization: Deterministic Approaches. Springer-Verlag, Berlin, 3rd ed. (1996). | MR | Zbl
and ,[41] Tractable approximate robust geometric programming. Optim. Eng. to appear. | MR | Zbl
, and ,[42] ILOG, ILOG CPLEX 10.0 User's Manual. ILOG S.A., Gentilly, France (2005).
[43] 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
and ,[44] An interior point potential reduction algorithm for the linear complementarity problem. Math. Program. 54 (1992) 267-279. | MR | Zbl
, and ,[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] Convex envelopes of monomials of odd degree. J. Glob. Optim. 25 (2003) 157-168. | MR | Zbl
and ,[55] An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms. J. Glob. Optim. 36 (2006) 161-189. | MR | Zbl
and ,[56] Global Optimization: from Theory to Implementation. Springer, Berlin (2006). | MR | Zbl
and , Eds.,[57] Mathematical models and a constructive heuristic for finding minimum fundamental cycle bases. Yugosl. J. Oper. Res. 15 (2005) 15-24. | MR
, , and ,[58] Reformulation in mathematical programming: an application to quantum chemistry. Discrete Appl. Math. to appear. | MR | Zbl
, , and ,[59] Expressing combinatorial optimization problems by systems of polynomial equations and the nullstellensatz, Technical Report RC24276(W0706-020), IBM Corporation (2007).
, , and ,[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] Convex hull of trilinear monomials with mixed sign domains. J. Glob. Optim. 29 (2004) 125-155. | MR | Zbl
and ,[67] Reformulation descent applied to circle packing problems. Comput. Oper. Res. 32 (2005) 2419-2434. | Zbl
, and ,[68] Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming. Birkhäuser, Basel (2005). | MR | Zbl
,[69] Mixed integer linear/nonlinear programming interface specification, Global Cape-Open Deliverable WP2.3-04 (2002).
, , and ,[70] Reformulations quadratiques convexes pour la programmation quadratique en variables 0-1. Ph.D. thesis, Conservatoire National d'Arts et Métiers (2006).
,[71] Relaxation guided variable neighbourhood search, in Proc. of Mini Euro Conference on Variable Neighbourhood Search, Tenerife, Spain (2005).
and ,[72] MIP reformulations of the probabilistic set covering problem. Technical Report 2007-02-1579, Optimization Online (2007).
, and ,[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] A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishers, Dodrecht (1999). | MR | Zbl
and ,[76] A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discrete Appl. Math. 52 (1994) 83-106. | MR | Zbl
and ,[77] 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
and ,[78] A new reformulation-linearization technique for bilinear programming problems. J. Global Optimization 2 (1992) 379-410. | MR | Zbl
and ,[79] Reformulation-linearization methods for global optimization, in Encyclopedia of Optimization, edited by C. Floudas and P. Pardalos. Springer, New York, to appear.
and ,[80] Improving discrete model representations via symmetry considerations. Manag. Sci. 47 1396-1407.
and ,[81] New reformulation linearization/convexification relaxations for univariate and multivariate polynomial programming problems. Oper. Res. Lett. 21 (1997) 1-9. | MR | Zbl
and ,[82] A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. J. Glob. Optim. 2 (1991) 101-112. | MR | Zbl
and ,[83] Global optimization of nonconvex factorable programming problems. Math. Program. 89 (2001) 459-478. | MR | Zbl
and ,[84] On the Optimal Design of Continuous Processes. Ph.D. thesis, Imperial College of Science, Technology and Medicine, University of London (1996).
,[85] Global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 21 (1997) S791-S796.
and ,[86] A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 23 (1999) 457-478.
and ,[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] Convex extensions and envelopes of semi-continuous functions. Math. Program. 93 (2002) 247-263. | MR | Zbl
and ,[92] Global optimization of mixed integer nonlinear programs: A theoretical and computational study. Math. Program. 99 (2004) 563-591. | MR | Zbl
and ,[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] Solving mixed integer programming problems using automatic reformulation. Oper. Res. 35 (1987) 45-57. | MR | Zbl
and ,[96] Exploiting equalities in polynomial programming, Technical Report 2006-05-1338, Optimization Online, 2006.
, and ,[97] A multivariate global optimization using linear bounding functions. J. Glob. Optim. 12 (1998) 383-404. | MR | Zbl
and ,[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 :