二进制变量下yijl=max(xijk+xilk-1)的线性约束转化及CPLEX Java实现

Can We Represent This as Linear Constraints? #

Yes! The constraint ( y_{ijl} = \max_{k=0..n}(x_{ijk} + x_{ilk} - 1) ) (with all variables binary) translates to:
( y_{ijl} = 1 ) if there exists at least one ( k ) where both ( x_{ijk} = 1 ) and ( x_{ilk} = 1 ); otherwise ( y_{ijl} = 0 ).

To model this linearly, we need auxiliary binary variables ( z_{ijk} ) that represent the logical AND of ( x_{ijk} ) and ( x_{ilk} ) (i.e., ( z_{ijk} = 1 ) iff ( x_{ijk} = 1 ) and ( x_{ilk} = 1 )). The full set of linear constraints is:

1. For each ( k ):
   ( z_{ijl,k} \leq x_{ijk} )
   ( z_{ijl,k} \leq x_{ilk} )
   ( z_{ijl,k} \geq x_{ijk} + x_{ilk} - 1 )
   These enforce ( z_{ijl,k} = x_{ijk} \land x_{ilk} ).

2. For each ( i,j,l ):
   ( \sum_{k=0}^n z_{ijl,k} \geq y_{ijl} )
   ( \sum_{k=0}^n z_{ijl,k} \leq (n+1) \cdot y_{ijl} )
   The first ensures ( y_{ijl} = 1 ) if any ( z_{ijl,k} = 1 ); the second ensures ( y_{ijl} = 0 ) if all ( z_{ijl,k} = 0 ).

CPLEX Java Implementation #

Assume you already have your model (IloCplex instance) and existing binary variables ( x_{ijk} ) (stored as a 3D array x[i][j][k]). Here's how to add the auxiliary variables and constraints:

Step 1: Create Auxiliary Variables

int I = ...; // Number of i values
int J = ...; // Number of j values
int L = ...; // Number of l values
int n = ...; // Upper bound of k (0 to n)

// Create y variables (binary)
IloNumVar[][][] y = new IloNumVar[I][J][L];
for (int i = 0; i < I; i++) {
    for (int j = 0; j < J; j++) {
        for (int l = 0; l < L; l++) {
            y[i][j][l] = model.boolVar("y_" + i + "_" + j + "_" + l);
        }
    }
}

// Create z variables (binary, one per k for each i,j,l)
IloNumVar[][][][] z = new IloNumVar[I][J][L][n+1];
for (int i = 0; i < I; i++) {
    for (int j = 0; j < J; j++) {
        for (int l = 0; l < L; l++) {
            for (int k = 0; k <= n; k++) {
                z[i][j][l][k] = model.boolVar("z_" + i + "_" + j + "_" + l + "_" + k);
            }
        }
    }
}

Step 2: Add Constraints for ( z_{ijl,k} )

for (int i = 0; i < I; i++) {
    for (int j = 0; j < J; j++) {
        for (int l = 0; l < L; l++) {
            for (int k = 0; k <= n; k++) {
                // z <= xijk
                model.addLe(z[i][j][l][k], x[i][j][k]);
                // z <= xilk
                model.addLe(z[i][j][l][k], x[i][l][k]);
                // z >= xijk + xilk - 1
                model.addGe(z[i][j][l][k], model.sum(
                    x[i][j][k], 
                    x[i][l][k], 
                    model.constant(-1)
                ));
            }
        }
    }
}

Step 3: Add Constraints Linking ( \sum z ) to ( y_{ijl} )

for (int i = 0; i < I; i++) {
    for (int j = 0; j < J; j++) {
        for (int l = 0; l < L; l++) {
            // Build sum of z over all k
            IloLinearNumExpr sumZ = model.linearNumExpr();
            for (int k = 0; k <= n; k++) {
                sumZ.addTerm(1.0, z[i][j][l][k]);
            }
            // sumZ >= y
            model.addGe(sumZ, y[i][j][l]);
            // sumZ <= (n+1)*y
            model.addLe(sumZ, model.prod(n+1, y[i][j][l]));
        }
    }
}

内容的提问来源于stack exchange，提问作者jkaapi