4
$\begingroup$

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.
Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, @RobPratt! This feels like magic to me. It can be very helpful for complex logical expressions. $\endgroup$
    – Penghui Guo
    Commented Aug 2, 2023 at 15:02
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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

YALMIP - Logics and integer-programming representations

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks Sudix. This link contains not only logical constraints, but also "Multiplications of variables and functions" and "Representations of functions", which are useful. $\endgroup$
    – Penghui Guo
    Commented Jul 31, 2023 at 9:33

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.