Linear optimization binary constraints formulation in Solver

Question

I am working on this investment problem statement and facing a hard time in formulating the constraint equation.

"Let x1, x2, x3, and x4 denote the binary variables if broker chooses to invest or not in investment options 1, 2, 3, 4. Suppose broker has the following constraints:

*if x3 + x4 ge 1 Then x1 + x2 = 1 and if x3 + x4 = 0 then x1 + x2 ge 0*

How do I combine the above constraints?

Answer 1

I will let you do the final checking, but basically this should work like:

"The constraints is if X3 + X4 ge 1 Then x1 + X2 = 1."

This is equivalent to:

(x3 or x4) implies ((x1 and not x2) or (not x1 and x2))

- (x3 or x4) captures the >= 1
- x1 + x2 = 1 is an XOR and captured by ((x1 and not x2) or (not x1 and x2))
  - DNF of XOR

Let's ask WolframAlpha to do boolean minimization: Computation -> we are interested in CNF!

- The CNF produced is ready to be mapped to ILP as it's a conjunction of ORs
- Each OR is a term of it's literals summing up to >= 1:

(1 - x1) + (1 - x2) + (1 - x3) >= 1
(1 - x1) + (1 - x2) + (1 - x4) >= 1
x1 + x2 + (1 - x3)             >= 1
x1 + x2 + (1 - x4)             >= 1

This should be a rather tight / strong formulation!

I recommend double-checking it with a Truth Table.