Reformulation techniques in Mathematical Programming

This thesis concerns the use of reformulation techniques in mathematical programming. Optimization and decision problems can be cast into a formulation involving sets of known numerical parameters, decision variables whose value is to be determined as a result of an algorithmic process, one of more optional objective functions to be optimized and various sets of constraints, which can be either expressed explicitly as functions of the parameters and variables, or as implicit requirements on the variables. These elements, namely parameters, variables, objective(s) and constraints, form a language called mathematical programming. There are usually many different possible equivalent mathematical programming formulations for the same optimization or decision problem. Different formulations often perform differently according to the type of algorithm employed to solve the problem. Furthermore, related auxiliary problems which may be useful during the course of the algorithmic solution process may arise and be also cast as mathematical programming formulations. This thesis is an in-depth study of the symbolic transformations that map a mathematical programming formulation to its equivalent forms and to other useful related formulations, and of their relations to various solution algorithms