Automatic Reformulation Search (ARS)

This 36-months project, starting 2007, is funded by the ANR.

Official partners

Leo Liberti, LIX, Ecole Polytechnique, Palaiseau, France (Principal Investigator)
Frédéric Messine, ENSEEIHT, IRIT, Toulouse, France
Lucas Létocart, LIPN, Université de Paris 13, France
Marie-Christine Plateau, Gaz de France, Paris, France

Other scientific partners

David Savourey, LIX, Ecole Polytechnique
Sonia Cafieri, ENAC, Toulouse
Claudia D'Ambrosio, DEIS, Università di Bologna, Italy
Antonio Frangioni, Dip. Informatica, Università di Pisa, Italy

Abstract

Optimization problems are usually defined in terms of their mathematical programming formulation. This consists of a set of objective functions to be optimized subject to a set of constraints, all expressed in terms of a set of decision variables which may be discrete or continuous. Formulations may be symbolically transformed so that some of their numerical properties (e.g. optimal solutions, feasible region,...) are invariant. Yet sometimes the reformulated problem is easier to solve or is useful within a given solution algorithm. The main aims of this project are a systematic study of reformulation theory, the production of software tools for automating mathematical programming reformulation, and the formalization and implementation of solution algorithms based on reformulation techniques.

Temporary personnel

Sonia Cafieri, 2-year contract as a postdoctoral fellow at LIX, Ecole Polytechnique

Outcomes

International journal papers

[L] Leo Liberti, Reformulations in mathematical programming: Automatic symmetry detection and exploitation, Mathematical Programming A, to appear.
[DFLL10b] Claudia D'Ambrosio, Antonio Frangioni, Leo Liberti, Andrea Lodi, On interval subgradient and no-good cuts, Operations Research Letters, 38:341-345, 2010.
[CLL10] Sonia Cafieri, Jon Lee, Leo Liberti, On convex relaxations of quadrilinear terms, Journal of Global Optimization, 47:661-685, 2010.
J. Ninin, F. Messine, A Metaheuristic Methodology based on the Limitation of the Memory of Interval Branch and Bound Algorithms, Journal of Global Optimization, to appear.
Leo Liberti, Laurent Alfandari, Marie-Christine Plateau, Edge cover by connected bipartite subgraphs, Annals of Operations Research, accepted for publication.
Pietro Belotti, Jon Lee, Leo Liberti, François Margot, Andreas Wächter, Branching and bounds tightening techniques for non-convex MINLP, Optimization Methods and Software, 24(4):597-634, 2009.
Leo Liberti, Carlile Lavor, Nelson Maculan, Marco-Antonio Chaer Nascimento, Reformulation in mathematical programming: an application to quantum chemistry, Discrete Applied Mathematics, 157(6):1309-1318, 2009.
Maurizio Bruglieri, Leo Liberti, Optimal running and planning of a biomass-based energy production process, Energy Policy, 36:2430-2438, 2008.
Leo Liberti, Reformulations in Mathematical Programming: Definitions and Systematics, RAIRO-RO, 43(1):55-86, 2009.
Leo Liberti, Nelson Maculan, Yue Zhang, Optimal configuration of gamma ray machine radiosurgery units: the sphere covering subproblem, Optimization Letters, 3:109-121, 2009.
Leo Liberti, Spherical cuts for Integer Programming problems, International Transactions in Operational Research, 15:283-294, 2008.

Book chapters

[Lb] Leo Liberti, Symmetry in Mathematical Progra mming, in S. Leyffer and J. Lee (eds.), Mixed Integer Nonlinear Programmi ng, IMA Series, Springer, accepted.
[BLLNT] Pietro Belotti, Leo Liberti, Andrea Lodi, Giacomo Nannicini, And rea Tramontani, Disjunctive inequalities: applications a nd extensions, in J. Cochran et al. (eds.), Encyclopedia of Operations Re search and Management Science, Wiley, Hoboken, to appear.
Leo Liberti, Sonia Cafieri, Fabien Tarissan, Reformulations in Mathematical Programming: A Computational Approach, in A. Abraham, A.-E. Hassanien, P. Siarry (eds.), Foundations of Computational Intelligence, Vol. 3, Studies in Computational Intelligence series 203:153-234, Springer, New York, 2009.
Maurizio Bruglieri, Leo Liberti, Optimally running a biomass-based energy production process, in J. Kallrath, P. Pardalos, S. Rebennack, M. Scheidt (eds.), Optimization in the Energy Industry, Springer, 221-232, 2009.
Hanif Sherali, Leo Liberti, Reformulation-Linearization Technique for Global Optimization, in P. Pardalos and C. Floudas (eds.), Encyclopedia of Optimization, 2nd Edition, 3263-3268, Springer, Berlin, 2008.

International conference papers

[LCS] Leo Liberti, Sonia Cafieri, David Savourey, The Reformulation-Optimization Software Engine, in Komei Fukuda et al., Mathematical Software, Lecture Notes in Computer Science, 6327:303-314, 2010.
[CLH10] Alberto Costa, Leo Liberti, Pierre Hansen, Formulation symmetries in circle packing, ISCO Proceedings, Electronic Notes in Discrete Mathematics 36:1303-1310, 2010.
[CHL10b] Alberto Costa, Pierre Hansen, Leo Liberti, Static symmetry breaking in circle packing, in U. Faigle, R. Schrader, D. Herrmann (eds.), CTW10 Proceedings, 47-50, Köln, 2010.
Leo Liberti, Reformulations in Mathematical Programming: Definitions, in G. Righini (ed.), CTW08 Proceedings, Università di Milano, 66-70, 2008.
Leo Liberti, Automatic generation of symmetry-breaking constraints, in B. Yang, D.-Z. Du and C.A. Wang (eds.) COCOA08 Proceedings, LNCS 5165:328-338, Springer 2008.
Fabien Tarissan, Leo Liberti, Camilo La Rota, Biological Regulatory Network reconstruction: a mathematical programming approach, ECCS08 Proceedings, 2008.
Camilo La Rota, Fabien Tarissan, Leo Liberti, Inferring parameters in Genetic Regulatory Networks, CLAIO08 Proceedings, 2008.
Kanika Dhyani, Leo Liberti, Mathematical programming formulations for the bottleneck Hyperplane Clustering problem, MCO08 Proceedings, Communications in Computer and Information Science 14:87-96, Springer 2008.
Leo Liberti, Giacomo Nannicini, Nenad Mladenovic, A good recipe for solving MINLPs, Matheuristics08 Proceedings, Bologna, Italy, 2008.
Sonia Cafieri, Jon Lee, Leo Liberti, Comparison of convex relaxations of quadrilinear terms, WCGO09 Proceedings, Lecture Notes in Operations Research, Wudan, China, june 2009.
Gérard Cornuéjols, Leo Liberti, Giacomo Nannicini, Improved strategies for branching on general dijunctions, CTW09 Proceedings, Paris, France, june 2009.
Nora Touati, Lucas Létocart, Anass Nagih (2009), Diversification and reoptimization procedures in column generation for the resolution of the acyclic vehicle routing problem with time windows, INOC 2009: International Network Optimization Conference, Pise, Italy, april 2009.
P. Hansen, F. Messine, J. Ninin. A Reformulation based on Affine Arithmetic for Constrained Global Optimization Problems. Nonconvex Programming - NCP 07, Rouen, France, pp 74-75, 2007.
J. Fontchastagner, F. Messine, Y. Lefèvre. An Interval Branch and Bound Algorithm for Mixed Constrained Global Optimization Problems with Constraints of Black-Box Type. Nonconvex Programming - NCP 07, Rouen, France, pp 77-78, 2007.
F. Messine. Interval Bounding Methods. Nonconvex Programming - NCP 07, Rouen, France, pp 79-80, 2007.
Lucas Létocart, Marie-Christine Plateau, Gérard Plateau (2009), A surrogate dual heuristics for the 0-1 exact k-item quadratic knapsack problem, ISMP'09~: The 20th International Symposium on Mathematical Programming, Chicago, USA, august 2009.
Nora Touati, Lucas Létocart, Anass Nagih (2008), Solutions diversification in a column generation scheme, IFORS 2008: International Federation of Operational Research Societies Conference, Sandton, South Africa, july 2008.
Nora Touati, Lucas Létocart, Anass Nagih (2008), Reoptimization techniques in a column generation scheme, ECCO XXI: European Chapter on Combinatorial Optimization, Dubrovnik, Croatia, mai 2008.

Software

Reformulation/Optimization Software Engine (ROSE). Maintainer: Dr. David Savourey