Linearizing a constraint for ILP

Question

I have binary variables $x_{ij}$. One of my constraint is

$$\sum\limits_{i}\sum\limits_{j} x_{ij}*f_i(\sum\limits_{j}x_{ij})\leq B \ $$ where my $f_i()$ is implemented as a table. Will it be possible to linearize this constraint ? My objective is $$max \sum\limits_{i}\sum\limits_{j} x_{ij}A_{ij}$$

Answer 1

Yes, it can be done rather easily. You simply have to define disjunctions to describe the function values, and then linearize a product between a binary and a continuous variable

Your table can be written in pseudocode as

if sum_j x = 0 then f_i = tablevalue(0)
if sum_j x = 1 then f_i = tablevalue(1)
...
if sum_j x = n then f_i = tablevalue(n)

Introduce new binary matrix $s$ where $s_{ik}$ is 1 if $\sum_j x_{ij} = k$, and a continuous variable $f_i$ (assuming the table has continuous values)

The disjunctions above can then be written as

$$ \sum_k s_{ik}=1,\\ -(1-s_{ik})n \leq \sum_j x_{ij}-k \leq n(1-s_{ik})\\ -M(1-s_{ik}) \leq f_i-\text{tablevalue}(k) \leq M(1-s_{ik}) $$

M is a big-M constant consistent with the values in the table.

You now have the terms $x_{ij}f_i$ to linearize. This is a standard problem which I guess you already know how to do.