Reformulations in Mathematical Programming: Definitions and Systematics

Leo Liberti

RAIRO - Operations Research (2009)

  • Volume: 43, Issue: 1, page 55-85
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Liberti, Leo. "Reformulations in Mathematical Programming: Definitions and Systematics." RAIRO - Operations Research 43.1 (2009): 55-85. <http://eudml.org/doc/250675>.

@article{Liberti2009,
abstract = { 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. },
author = {Liberti, Leo},
journal = {RAIRO - Operations Research},
keywords = {Reformulation; formulation; model; linearization; mathematical program.; reformulation; mathematical program},
language = {eng},
month = {1},
number = {1},
pages = {55-85},
publisher = {EDP Sciences},
title = {Reformulations in Mathematical Programming: Definitions and Systematics},
url = {http://eudml.org/doc/250675},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Liberti, Leo
TI - Reformulations in Mathematical Programming: Definitions and Systematics
JO - RAIRO - Operations Research
DA - 2009/1//
PB - EDP Sciences
VL - 43
IS - 1
SP - 55
EP - 85
AB - 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.
LA - eng
KW - Reformulation; formulation; model; linearization; mathematical program.; reformulation; mathematical program
UR - http://eudml.org/doc/250675
ER -

References

top
  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.  
  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.  
  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.  
  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.  
  7. F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim.5 (1995) 13–51.  
  8. K.M. Anstreicher, Recent advances in the solution of quadratic assignment problems. Math. Program. B97 (2003) 27–42.  
  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.  
  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.  
  13. D. Bertsimas and M. Sym, The price of robustness. Oper. Res.52 (2004) 35–53.  
  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.  
  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.  
  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).  
  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.  
  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érationelle4 (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.  
  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.  
  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.  
  34. S. Gueye and P. Michelon, “miniaturized" linearizations for quadratic 0/1 problems. Ann. Oper. Res.140 (2005) 235–261.  
  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.  
  36. P.L. Hammer and S. Rudeanu, Boolean Methods in Operations Research and Related Areas. Springer, Berlin (1968).  
  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.  
  39. R. Horst, On the convexification of nonlinear programming problems: an applications-oriented approach. Eur. J. Oper. Res.15 (1984) 382–392.  
  40. R. Horst and Hoang Tuy, Global Optimization: Deterministic Approaches. Springer-Verlag, Berlin, 3rd ed. (1996).  
  41. K.-L. Hsiung, S.-J. Kim and S. Boyd, Tractable approximate robust geometric programming. Optim. Eng. to appear.  
  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.  
  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.  
  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).  
  46. L. Liberti, Reduction constraints for the global optimization of NLPs. Int. Trans. Oper. Res.11 (2004) 34–41.  
  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. 4OR2 (2004) 255–258.  
  49. L. Liberti, Linearity embedded in nonconvex programs. J. Glob. Optim.n33 (2005) 157–196.  
  50. L. Liberti, Writing global optimization software, in Global Optimization: from Theory to Implementation, edited by Liberti and Maculan.Springer, berlin (2006) 211–262.  
  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. 4OR5 231–245 (2007).  
  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.  
  54. L. Liberti and C.C. Pantelides, Convex envelopes of monomials of odd degree. J. Glob. Optim.25 (2003) 157–168.  
  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.  
  56. L. Liberti and N. Maculan, Eds., Global Optimization: from Theory to Implementation. Springer, Berlin (2006).  
  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.  
  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.  
  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.  
  62. O.L. Mangasarian, The linear complementarity problem as a separable bilinear program. J. Glob. Optim.6 (1995) 153–161.  
  63. F. Margot, Pruning by isomorphism in branch-and-cut. Math. Program.94 (2002) 71–90.  
  64. F. Margot, Exploiting orbits in symmetric ilp. Math. Program. B98 (2003) 3–21.  
  65. G.P. McCormick, Computability of global solutions to factorable nonconvex programs: Part I – Convex underestimating problems. Math. Program.10 (1976) 146–175.  
  66. C.A. Meyer and C.A. Floudas, Convex hull of trilinear monomials with mixed sign domains. J. Glob. Optim.29 (2004) 125–155.  
  67. N. Mladenović, F. Plastria and D. Urošević, Reformulation descent applied to circle packing problems. Comput. Oper. Res.32 (2005) 2419–2434.  
  68. I. Nowak, Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming. Birkhäuser, Basel (2005).  
  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.  
  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).  
  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.  
  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.  
  78. H.D. Sherali and A. Alameddine, A new reformulation-linearization technique for bilinear programming problems. J. Global Optimization2 (1992) 379–410.  
  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.  
  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.  
  83. H.D. Sherali and H. Wang, Global optimization of nonconvex factorable programming problems. Math. Program.89 (2001) 459–478.  
  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. .  URIhttp://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.  
  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.  
  91. M. Tawarmalani and N. Sahinidis, Convex extensions and envelopes of semi-continuous functions. Math. Program.93 (2002) 247–263.  
  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.  
  93. M.J. Todd, Semidefinite optimization. Acta Numerica10 (2001) 515–560.  
  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.  
  95. T.J. van Roy and L.A. Wolsey, Solving mixed integer programming problems using automatic reformulation. Oper. Res.35 (1987) 45–57.  
  96. J.C. Vera, J.F. Pena and L.F. Zuluaga, 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.  
  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.  
  99. L.A. Wolsey, Integer Programming. Wiley, New York (1998).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.