6
$\begingroup$

For a given optimization problem there are often many known math programming formulations. For example for the TSP here is a survey https://link.springer.com/chapter/10.1007/3-540-36626-1_5 of many different formulations, that all describe the same problem, sometimes in lifted spaces.

Often there is an "intuitive way" of modeling a problem. For example for the knapsack problem the single constraint formulation is the first things that comes to my mind. But there are alternative formulations in extended spaces, which do not come to my mind straightforward.

Are there strategies/rules/systematic approaches to derive "alternative formulation"? Is there literature on this?

$\endgroup$
1
  • 4
    $\begingroup$ Mathematical modelling is more than science, it's an art. The more you do, the better you get. Deriving non-trivial models normally requires spending quite a lot of time. Of course, in theory we can have many alternative formulations by slight modifications. This is not what you want. $\endgroup$
    – rasul
    Jan 16, 2021 at 23:15

1 Answer 1

5
$\begingroup$

About extended reformulation for integer linear programming, you can be interested in this lecture by Vanderbeck and Wolsey, and the corresponding research report. They formalize reformulations, especially what are good reformulations, and described techniques to build them systematically. They give many examples of reformulations for some well-known discrete optimization problems.

There is also some research about reformulations of quadratic binary programs. For example, look at the work of Billionnet, Elloumi, and Lambert.

As well said in the comment, formulating problems mathematically is more than science. Now, formulating and reformulating problems to be solved at best by solvers is an experimental work. The designers of solvers generally give some modeling guidelines and illustrate them on example problems. But sometimes, even the designers of the solvers themselves cannot say what formulations will be better solved by an optimization engine. Just because optimization engines are complex systems and, like any complex system, their outputs are not fully predictable.

Modeling techniques are generally less emphasized in research and teaching in comparison with solving techniques. At LocalSolver, we love implementing and improving solving techniques in a very agnostic fashion. But we are also convinced that "modeling is the master and computation the servant" as John Hooker nicely wrote. In particular, we are convinced that the classical Boolean modeling approach, traditionally used in integer linear programming, is not the best one to capture the structure of combinatorial problems, which is critical to solving them efficiently in practice. We have introduced fresh-new modeling features to model discrete problems like routing, scheduling, packing, or clustering problems. For example, for the TSP you cited in your question, ideas are given in previous posts like this one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.