REFORMULATIONS IN MATHEMATICAL PROGRAMMING: DEFINITIONS AND SYSTEMATICS

A reformulation of a mathematical program is a formu-lation which shares some properties with, but is in some sense better than, the original program. Reformulations are important with respectto the choice and efficiency of the solution algorithms; furthermore, it isdesirable that reformulations can be carried out automatically. Refor-mulation techniques are widespread in mathematical programming butinterestingly they have never been studied under a unified framework.This paper attempts to move some steps in this direction. We definea framework for storing and manipulating mathematical programmingformulations and give several fundamental definitions categorizing use-ful reformulations in essentially four types (opt-reformulations, narrow-ings, relaxations and approximations). We establish some theoreticalresults and give reformulation examples for each type