3
$\begingroup$

Can we transform a CNF to ILP without introducing new variables?

My question can be seen as a follow up to Express boolean logic operations in zero-one integer linear programming (ILP) as the solution proposed in that post introduces additional variables.

Also, my current understanding is that each 0 value in the truth table is represented by one linear inequality. This means that if my boolean function is of 16 input variables and balanced, there will be 2^15 linear inequalities so is there a way to reduce the number of inequalities?

$\endgroup$
  • $\begingroup$ @DavidRicherby well, I know that each clause can be represented by one linear inequality, for example, (x v y v ¬Z) can be represented as x + y + (1-z) >= 1 but I'm stuck in the adding of the clauses, how this should be done? for instance, (x v y v ¬z) ^ (¬x v y v ¬Z)? There is another post that describes how Boolean expressions can be transformed into linear inequalities but it adds more variables which I would like to avoid in my problem. $\endgroup$ – Moati Feb 17 '17 at 18:34
  • 1
    $\begingroup$ Perhaps you should explain what you want more clearly. Edit your question to include a more elaborate explanation of what you want. $\endgroup$ – Yuval Filmus Feb 20 '17 at 21:47
  • $\begingroup$ I can't understand what you are looking for. I don't understand what "I'd like to represent f within the linear inequalities (not just the input variables)" means. As far as how to encode the constraints when f evaluates 0, people have already given you hints on how to do that. Study the NP-completeness of zero-one integer programming. Reduce CircuitSAT to zero-one integer programming -- this reduction is covered in standard resources. $\endgroup$ – D.W. Feb 21 '17 at 18:36
  • $\begingroup$ @D.W. let me give you a concrete example. let's assume that the function is the xor of (x,y,z) then, f = (x v y v z) ^ (x v ¬y v ¬z) ^ (¬x v y v ¬z) ^ (¬x v ¬y v z). From the standard resources, the linear inequalities are as follows: x + y + z >= 1, x + (1-y) + (1-z) >= 1, (1-x) + y + (1-z) >= 1, (1-x) + (1-y) + z >= 1. So they are represented by the input variables x, y, z. In my problem, I'd like f to be part of the linear inequalities as well. Let me rephrase my question as follows: is there a way to represent a truth table of a Boolean function as a set of linear inequalities? $\endgroup$ – Moati Feb 21 '17 at 18:51
  • $\begingroup$ I don't know what it means for "f to be part of the linear inequalities as well". Can you try defining what that means systematically, in terms of concepts we do know? Or perhaps you should try to find a simple example, where you can show us an example of an answer that you would be happy with and an answer that you would not be happy with. To answer the rephrased question: Yes, you can represent the truth table of a Boolean function as a set of linear inequalities, and other people have repeatedly told you how: study the reduction from SAT to zero-one integer programming. $\endgroup$ – D.W. Feb 21 '17 at 21:22
1
$\begingroup$

No. Usually (for most functions / CNF formulas) you'll need additional variables. Linear inequalities form a convex space. If the set of solutions such that $f(x)=1$ is not convex, you'll need additional variables.

The exact number of additional variables and inequalities required depends on the function / on the CNF formula.

$\endgroup$
  • $\begingroup$ my current approach is that I introduce one linear inequality for each row in the truth table such that f(x)=0 so can you give me a non-trivial example where multiple rows are expressed in one linear inequality? would it be based solely on observations or there would be a systematic way to do it? Thanks $\endgroup$ – Moati Feb 22 '17 at 18:28
  • $\begingroup$ I found that there is an algorithm called Quine-McCluskey that would give the minimal sum of products and I presume there is a standard approach to transform from sum of products to product of sums $\endgroup$ – Moati Feb 22 '17 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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