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 describe techniques to build them systematically. They give many examples of reformulations for some well-known discrete optimization problems.

There is also some research on 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. Solver designers generally give some modeling guidelines and illustrate them with examples of problems. But sometimes, even the solvers' designers 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 than solving techniques. At Hexaly, 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 innovative 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 you have read our privacy policy.

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