# Systematic references on linearizing conditional / logical expressions

On this site, one can usually finds questions like “How to transform my expression into linear form?” The expressions usually contain and, or, iff, and combines of them. But the answers are usually problem specific, making it hard to generalize them to other cases.

My questions are:

• Is there any systematic material on linearization for conditional / logical expressions?
• It seems that Constraint Programming (CP), which I am not quite familiar with, handles conditional / logical expressions more intuitively. Is there any reference on the link between CP and Mathematical Programming.
• Jul 23 at 6:12

A systematic approach is to rewrite the logical proposition in conjunctive normal form, which somewhat automatically yields linear constraints:

$$\bigwedge_{i \in I} \bigvee_{j \in J_i} z_{ij} \iff \left(\sum_{j \in J_i} z_{ij} \ge 1 \text{ for all i \in I}\right)$$

Several examples are here.

A good reference is:

Raman, R. and I.E. Grossmann, Relation Between MILP Modelling and Logical Inference for Chemical Process Synthesis, Computers Chem. Engng. 15 (1991).

• Thank you, @RobPratt! This feels like magic to me. It can be very helpful for complex logical expressions. Aug 2 at 15:02

I was also interested in this.

I found these lecture notes online by Laurent Lessard which covers many cases. RobPratt's answer is very useful. The reason for adding these lecture notes as well is because they cover some cases where I would not be confident converting to CNF (e.g. implications).

I've found the following documentation from YALMIP often useful:

YALMIP - Logics and integer-programming representations

• Thanks Sudix. This link contains not only logical constraints, but also "Multiplications of variables and functions" and "Representations of functions", which are useful. Jul 31 at 9:33