Volume 43, Number 1, January-March 2009
|Page(s)||55 - 85|
|Published online||28 January 2009|
Reformulations in Mathematical Programming: Definitions and Systematics
LIX École Polytechnique, 91128
Palaiseau, France; firstname.lastname@example.org
Accepted: 17 July 2008
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.
Mathematics Subject Classification: 90C11 / 90C26 / 90C27 / 90C30 / 90C99
Key words: Reformulation / formulation / model / linearization / mathematical program.
© EDP Sciences, ROADEF, SMAI, 2009
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.