1
$\begingroup$

It is nice to know that every boolean formula can be expressed by zero-one integer programming by this answered question. But are there any applications?

To be more precise: Are there papers which use the existense of zero-one integer programming for boolean operations?

$\endgroup$

closed as too broad by D.W., Juho, A.Schulz, vonbrand, Luke Mathieson Feb 15 '14 at 4:35

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Applications in what sense? (Feels a little broad, this one.) $\endgroup$ – Raphael Feb 9 '14 at 22:48
  • 2
    $\begingroup$ Well, 0-1 ILP is equivalent to SAT. And such can be used for all the same purposes. $\endgroup$ – Dan D. Feb 10 '14 at 5:17
2
$\begingroup$

Yes, there are many applications. To find some, go to that question and look through the linked and related questions on the sidebar; that will already show you several applications. Next, do a search for the search term "ILP" on this site, and browse through the search results. You will find many examples of problems that can be solved with zero-one ILP using these techniques.

$\endgroup$
  • $\begingroup$ As search results and "Related" are bound to change over time, maybe you should link some examples? $\endgroup$ – Raphael Feb 10 '14 at 8:33
  • $\begingroup$ Or even link some papers? But that is the question ;-) $\endgroup$ – user14525 Feb 10 '14 at 16:29
  • $\begingroup$ Personally, I suggest that the original poster do some research on his own. We expect folks asking question to do research on their own before asking here, so I don't think it's unreasonable to ask the author to put in that effort. My answer is intended to help point in the correct direction to help make that search fruitful. $\endgroup$ – D.W. Feb 11 '14 at 19:08
1
$\begingroup$

Forget specific applications, and just think about what a linear program is. You're optimising (either maximising or minimising) some linear combination of variables, subject to certain linear constraints.

So embedding boolean logic in the linear program should allow you to extend this to boolean constraints as well. Rather than just finding any old assignment of truth values which satisfies the boolean expression, this gives you a natural way to find an optimal assignment, for some reasonable definition of "optimal".

Now can you think of an application?

This doesn't use the exact embedding, but Appel and George, Optimal Spilling for CISC Machines with Few Registers (2000) is one good example of a real-world optimisation problem based around boolean constraints and a linear objective function.

$\endgroup$
  • $\begingroup$ I thought, that other papers use this very often, but which? $\endgroup$ – user14525 Feb 10 '14 at 16:25