Optimization – Logical OR in Linear Programming Constraint

integer programminglinear programmingoptimization

In a linear programming formulation, I have the following linear constraint:

$A_{i,a} x_{i,a} \leq x_{j,b}$

where $x_{i,a}$ and $x_{j,b}$ are binary variables, and $A_{i,a} \in \mathbb{R}^{+}$ is a parameter (i.e. a constant).

The above constraint must hold when the following conditions hold:

(a) $i, j \geq 1$ and

(b) $i > j$ or ($i < j$ and $a>b$)

  • First of all, is it correct according to the linear programming conventions and best practices to have an OR statement in the conditions of a linear constraint?

  • If so, what is the most appropriate way to formulate these conditions (is any of the options below acceptable)? I am a bit confused regarding the notation I should use, as a comma is commonly used to denote the logical and in the conditions of constraints in the context of linear programming.

    (1) $A_{i,a} x_{i,a} \leq x_{j,b}, \quad i, j \geq 1, i > j$ or $(i < j, a>b)$

    (2) $A_{i,a} x_{i,a} \leq x_{j,b}, \quad i, j \geq 1, i > j$ or $(i < j$ and $a>b)$

    (3) $A_{i,a} x_{i,a} \leq x_{j,b}, \quad i, j \geq 1, i > j \lor (i < j, a>b)$

    (4) $A_{i,a} x_{i,a} \leq x_{j,b}, \quad i, j \geq 1, i > j \lor (i < j \land a>b)$

Best Answer

You are confused. There are two very different cases.

  • These conditions are easy when they are on indices (just use a condition in the modeling tool or programming language).
  • Such conditions on decision variables are difficult and need special reformulations.

Conclusion: don't worry about things like $\forall i\lt j$. They can be handled directly. They are not part of the constraints, but rather determine which constraints are generated. The exact syntax depends on the modeling tool or programming language, but sometimes a loop with an "if" is used.

An artificial example of a conditional constraint in PuLP:

for i in range(N):
    for j in range(N):
        if i<j:
            prob += x[i] + y[j] == 1

(This fragment can be improved, but it illustrates the concept.)

Related Question