Linearise a quadratic constraint to transform a quadratic program into a linear program

Question

I am trying to define a Linear Program but one of my constraints is quadratic. The program looks like this:

f: $\min \sum x_{ij}$

s.t.

$$\forall_i x_{ii} + \sum_{j}c_{ij}x_{ij}x_{jj} = 1$$

$$\forall_{i,j,k} (1-x_{ik}) + (1-x_{jk}) + c_{i,j} \geq 1$$

$$\sum_j x_{ij} = 1$$

$$\sum_i x_{ii} \leq k$$

$$\forall_{i,j} x_{i,j} \in \{0,1\}$$

The quadratic constraint is:

$$\forall_i x_{ii} + \sum_{j}c_{ij}x_{ij}x_{jj} = 1$$

where $x_{ii}, x_{i,j}, x_{jj}$ are variables and $c_{ij}$ is a value that can be either 1 or 0.

Any idea about how can I linearise this program?

Thank you very much!

Answer 1

Since your decision variables are all binary, you replace products $x_a x_b$ with a new binary variable $x_{ab}$ with the constraints $x_{ab} \geq x_a + x_b - 1, x_{ab}\leq x_a, x_{ab}\leq x_{b}$, representing the fact that both variables have to be 1 for the product to be true.