Systematic references on linearizing conditional / logical expressions

Question

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.

Answer 1

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).

Answer 2

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).

Answer 3

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

YALMIP - Logics and integer-programming representations