# Reformulations in Mathematical Programming: Definitions and Systematics

RAIRO - Operations Research (2009)

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

## Access Full Article

top## Abstract

top## How to cite

topLiberti, 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- 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.
- 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.
- 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.
- C.S. Adjiman, S. Dallwig, C.A. Floudas and A. Neumaier, A global optimization method, $\alpha $BB, for general twice-differentiable constrained NLPs: I. Theoretical advances. Comput. Chem. Eng.22 (1998) 1137–1158.
- C.S. Adjiman, I.P. Androulakis and C.A. Floudas, A global optimization method, $\alpha $BB, for general twice-differentiable constrained NLPs: II. Implementation and computational results. Comput. Chem. Eng.22 (1998) 1159–1179.
- F.A. Al-Khayyal and J.E. Falk, Jointly constrained biconvex programming. Math. Oper. Res.8 (1983) 273–286.
- F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim.5 (1995) 13–51.
- K.M. Anstreicher, Recent advances in the solution of quadratic assignment problems. Math. Program. B97 (2003) 27–42.
- 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.
- 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.
- H.M.T. Ben Amor, J. Desrosiers and A. Frangioni, Stabilization in column generation. Discrete Appl. Math. to appear.
- W. Ben-Ameur and H. Kerivin, Routing of uncertain demands. Optim. Eng.3 (2005) 283–313.
- D. Bertsimas and M. Sym, The price of robustness. Oper. Res.52 (2004) 35–53.
- 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.
- 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.
- J. Bjorkqvist and T. Westerlund, Automated reformulation of disjunctive constraints in MINLP optimization. Comput. Chem. Eng.23 (1999) S11–S14.
- 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.
- A. Brook, D. Kendrick and A. Meeraus, GAMS, a user's guide. ACM SIGNUM Newsletter, 23 (1988) 10–11.
- G.B. Dantzig, Linear Programming and Extensions. Princeton University Press, Princeton, NJ (1963).
- 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).
- L. Di Giacomo, Mathematical programming methods in dynamical nonlinear stochastic Supply Chain management. Ph.D. thesis, DSPSA, Università di Roma “La Sapienza" (2007).
- J.E. Falk and J. Liu, On bilevel programming, part i: general nonlinear cases. Mathem. Program.70 (1995) 47–72.
- R. Fletcher and S. Leyffer, User manual for filter. Technical report, University of Dundee, UK (1999).
- R. Fortet, Applications de l'algèbre de boole en recherche opérationelle. Revue Française de Recherche Opérationelle4 (1960) 17–26.
- R. Fourer, Personal communication (2004).
- R. Fourer and D. Gay, The AMPL Book. Duxbury Press, Pacific Grove (2002).
- R. Fourer, J. Ma, K. Martin and W. Sheng, Optimization services 1.0 user manual. Technical report, COIN-OR (2007).
- 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.
- S. Galli, Parsing AMPL internal format for linear and non-linear expressions. Didactical project, DEI, Politecnico di Milano, Italy (2004).
- P.E. Gill, User's Guide for SNOPT 5.3. Systems Optimization Laboratory, Department of EESOR, Stanford University, California (1999).
- M. Grant, S. Boyd and Y. Ye, Disciplined convex programming, in Liberti and Maculan [56], 155–210.
- C. Guéret, C. Prins and M. Sevaux, Applications of optimization with Xpress-MP. Dash optimization. Bilsworth (2000).
- S. Gueye and Ph. Michelon, A linearization framework for unconstrained quadratic (0-1) problems. Discrete Appl. Math., to appear.
- S. Gueye and P. Michelon, “miniaturized" linearizations for quadratic 0/1 problems. Ann. Oper. Res.140 (2005) 235–261.
- 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.
- P.L. Hammer and S. Rudeanu, Boolean Methods in Operations Research and Related Areas. Springer, Berlin (1968).
- P. Hansen, Method of non-linear 0-1 programming. Ann. Discrete Math.5 (1979) 53–70.
- P. Hansen and C. Meyer, Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem. Discrete Appl. Math., to appear.
- R. Horst, On the convexification of nonlinear programming problems: an applications-oriented approach. Eur. J. Oper. Res.15 (1984) 382–392.
- R. Horst and Hoang Tuy, Global Optimization: Deterministic Approaches. Springer-Verlag, Berlin, 3rd ed. (1996).
- K.-L. Hsiung, S.-J. Kim and S. Boyd, Tractable approximate robust geometric programming. Optim. Eng. to appear.
- ILOG, ILOG CPLEX 10.0 User's Manual. ILOG S.A., Gentilly, France (2005).
- 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.
- M. Kojima, N. Megiddo and Y. Ye, An interior point potential reduction algorithm for the linear complementarity problem. Math. Program.54 (1992) 267–279.
- 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).
- L. Liberti, Reduction constraints for the global optimization of NLPs. Int. Trans. Oper. Res.11 (2004) 34–41.
- L. Liberti, Reformulation and Convex Relaxation Techniques for Global Optimization. Ph.D. thesis, Imperial College London, UK, (2004).
- L. Liberti, Reformulation and convex relaxation techniques for global optimization. 4OR2 (2004) 255–258.
- L. Liberti, Linearity embedded in nonconvex programs. J. Glob. Optim.n33 (2005) 157–196.
- L. Liberti, Writing global optimization software, in Global Optimization: from Theory to Implementation, edited by Liberti and Maculan.Springer, berlin (2006) 211–262.
- L. Liberti, Reformulation techniques in mathematical programming, Thèse d'Habilitation à Diriger des Recherches, Université de Paris-Dauphine (2007).
- L. Liberti, Compact linearization of binary quadratic problems. 4OR5 231–245 (2007).
- 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.
- L. Liberti and C.C. Pantelides, Convex envelopes of monomials of odd degree. J. Glob. Optim.25 (2003) 157–168.
- L. Liberti and C.C. Pantelides, An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms. J. Glob. Optim.36 (2006) 161–189.
- L. Liberti and N. Maculan, Eds., Global Optimization: from Theory to Implementation. Springer, Berlin (2006).
- 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.
- 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.
- 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).
- 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.
- O.L. Mangasarian, Linear complementarity problems solvable by a single linear program. Math. Program.10 (1976) 263–270.
- O.L. Mangasarian, The linear complementarity problem as a separable bilinear program. J. Glob. Optim.6 (1995) 153–161.
- F. Margot, Pruning by isomorphism in branch-and-cut. Math. Program.94 (2002) 71–90.
- F. Margot, Exploiting orbits in symmetric ilp. Math. Program. B98 (2003) 3–21.
- G.P. McCormick, Computability of global solutions to factorable nonconvex programs: Part I – Convex underestimating problems. Math. Program.10 (1976) 146–175.
- C.A. Meyer and C.A. Floudas, Convex hull of trilinear monomials with mixed sign domains. J. Glob. Optim.29 (2004) 125–155.
- N. Mladenović, F. Plastria and D. Urošević, Reformulation descent applied to circle packing problems. Comput. Oper. Res.32 (2005) 2419–2434.
- I. Nowak, Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming. Birkhäuser, Basel (2005).
- 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).
- 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).
- J. Puchinger and G.R. Raidl, Relaxation guided variable neighbourhood search, in Proc. of Mini Euro Conference on Variable Neighbourhood Search, Tenerife, Spain (2005).
- A. Saxena, V. Goyal and M. Lejeune, MIP reformulations of the probabilistic set covering problem. Technical Report 2007-02-1579, Optimization Online (2007).
- H.D. Sherali, Global optimization of nonconvex polynomial programming problems having rational exponents. J. Glob. Optim.12 (1998) 267–283.
- H. Sherali, Personal communication (2007).
- H.D. Sherali and W.P. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishers, Dodrecht (1999).
- 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.
- 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.
- H.D. Sherali and A. Alameddine, A new reformulation-linearization technique for bilinear programming problems. J. Global Optimization2 (1992) 379–410.
- 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.
- H.D. Sherali and C. Smith, Improving discrete model representations via symmetry considerations. Manag. Sci.47 1396–1407.
- 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.
- 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.
- H.D. Sherali and H. Wang, Global optimization of nonconvex factorable programming problems. Math. Program.89 (2001) 459–478.
- 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).
- E.M.B. Smith and C.C. Pantelides, Global optimisation of nonconvex MINLPs. Comput. Chem. Eng.21 (1997) S791–S796.
- 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.
- INFORMS Computing Society. The mathematical programming glossary. . URIhttp://glossary.computing.society.informs.org/second.php?page=R.html
- A.S. Strekalovsky, Extremal problems with d.c. constraints. Comput. Mathem. Math. Phys.41 (2001) 1742–1751.
- A.S. Strekalovsky, On global optimality conditions for d.c. programming problems, Technical Paper, Irkutsk State University (1997).
- F. Tardella, Existence and sum decomposition of vertex polyhedral convex envelopes. Optim. Lett.2 (2008) 363–375.
- M. Tawarmalani and N. Sahinidis, Convex extensions and envelopes of semi-continuous functions. Math. Program.93 (2002) 247–263.
- M. Tawarmalani and N.V. Sahinidis, Global optimization of mixed integer nonlinear programs: A theoretical and computational study. Math. Program.99 (2004) 563–591.
- M.J. Todd, Semidefinite optimization. Acta Numerica10 (2001) 515–560.
- 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.
- T.J. van Roy and L.A. Wolsey, Solving mixed integer programming problems using automatic reformulation. Oper. Res.35 (1987) 45–57.
- J.C. Vera, J.F. Pena and L.F. Zuluaga, Exploiting equalities in polynomial programming, Technical Report 2006-05-1338, Optimization Online, 2006.
- X. Wang and T.S. Change, A multivariate global optimization using linear bounding functions. J. Glob. Optim.12 (1998) 383–404.
- 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.
- L.A. Wolsey, Integer Programming. Wiley, New York (1998).

## NotesEmbed ?

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