A reformulation of a mathematical program is a formulation whichshares some properties with, but is in some sense better than, theoriginal program. Reformulations are important with respect to thechoice and efficiency of the solution algorithms; furthermore, it isdesirable that reformulations can be carried outautomatically. Reformulation techniques are widespread in mathematicalprogramming but interestingly they have never been studied under aunified framework. This paper attempts to move some steps in thisdirection. We define a framework for storing and manipulatingmathematical programming formulations and give several fundamentaldefinitions categorizing useful reformulations in essentially fourtypes (opt-reformulations, narrowings, relaxations andapproximations). We establish some theoretical results and givereformulation examples for each type.
