JCJC - Jeunes chercheuses & jeunes chercheurs

Automatic Reformulation Search – ARS

Submission summary

This project focusses on automatic methods for finding alternative formulations of a given optimization problem. These are usually expressed in terms of known parameters, decision variables (which may be integer and/or continuous), objective function(s) and constraints. Although equivalent formulations provide equally good descriptions of a problem, solution algorithms exhibit markedly different efficiency and behaviours depending on the formulation used. This difference may range up to several orders of magnitude. This underlines the importance of a systematic study of reformulation techniques and of the research of novel techniques. The implementation of these reformulations is equally important, as the importance of a reformulation should mainly be assessed according to its practical performance. Up to now the only existing "reformulation libraries" are the pre-processing libraries within commercial Linear Programming (LP) and Mixed-Integer Linear Programming (MILP) solvers, and present many inconveniences: (a) no systematic theoretical study thereof is provided along with the code; (b) they cannot be used separately from the corresponding solver; (c) the amount of user configuration they offer is limited; (d) they cannot be extended by the user. In other words, they are hard-coded in the solver. All this notwithstanding, their importance is paramount, and in terms of solver reliability they really make the difference between a research tool and a commercial-strength code. Such is the situation with LP and MILP solvers. For other optimization fields, the situation varies from unsatisfactory to dire. Although reformulation is already an important sub-field of global optimisation, for example, more developments are needed before a truly reliable global optimization solver can emerge. Commercial MILP solvers are usually able to provide a solution to most MILPs expressed in mathematical programming form, regardless of problem structure aside from linearity of objective and constraints. This state of affairs is due both to advances in algorithmics and to what is usually called pre-processing, or in other words reformulation of the problem prior to the solution. As regards Mixed-Integer Nonlinear Programming (MINLP) problems, the current literature provides satisfactory algorithms but not enough reformulation techniques. The need for automatic reformulations, and the availability thereof, suggest a complementary approach to algorithmics which was not previously explored in depth: namely, the inclusion of the formulation itself among the problem elements which are allowed to vary during the optimization process. More precisely, the search for an optimal solution currently only occurs in what is known as "solution space", whereas one promising possibility is to let the search range in "formulation space" as well, meaning that the algorithms themselves might modify the formulation according to the problem they are experiencing during the search. The implementation of this idea requires a very advanced software toolbox. In particular, the software implementation must be able to symbolically modify the algebraic and transcendental objective and constraint expressions, and in general to manipulate sets of problem entities (parameters, variables, objective and constraints) as combinatorial rather than numerical structures. The current project proposes to provide a systematic study of existing reformulations, to add new ones, to develop some algorithms which are able to explore formulation space, and to implement and benchmark all these ideas on a general software framework capable of symbolic manipulations.

Project coordination

Léo LIBERTI (Autre établissement d’enseignement supérieur)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

Partner

Help of the ANR 118,000 euros
Beginning and duration of the scientific project: - 36 Months

Useful links

Explorez notre base de projets financés

 

 

ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter