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.
Keywords: 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},
year = {2009},
publisher = {EDP-Sciences},
volume = {43},
number = {1},
doi = {10.1051/ro/2009005},
mrnumber = {2502325},
zbl = {1158.90390},
language = {en},
url = {http://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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
Cité par Sources :