Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
I want to turn this objective function
$$\max \sum_{i=1}^{N-1} \sum_{j=i+1}^N |TX_i^T - TX_j^T|$$
where $T$ is just a vector with increasing integers (e.g $[1 \ 2]$) and $X_i$ is a vector with $n$ variables like $[x_{11} \ x_{12}]$.
Is there a way to turn this objective function into a linear form?
And how can I do that?
My problem is that I don't quite fully understand it when I have to maximize the objective function.
Introduce a new variable $z_{i,j}$ to represent the summand, and apply the linearization of $\max$ described here. Explicitly, the problem is to maximize $\sum_{i=1}^{N-1} \sum_{j=i+1}^N z_{i,j}$ subject to \begin{align} z_{i,j} &\ge T X_i^T-T X_j^T\\ z_{i,j} &\ge -T X_i^T+T X_j^T\\ z_{i,j} &\le T X_i^T-T X_j^T + M_{i,j}^1 (1-y_{i,j})\\ z_{i,j} &\le -T X_i^T+T X_j^T+ M_{i,j}^2 y_{i,j}\\ y_{i,j} &\in \{0,1\} \end{align} Here, $M_{i,j}^1$ is a small upper bound on $z_{i,j} - T X_i^T + T X_j^T$, and $M_{i,j}^2$ is a small upper bound on $z_{i,j} + T X_i^T - T X_j^T$.
The idea is that $y_{i,j}=1$ forces $z_{i,j} = T X_i^T-T X_j^T$, and $y_{i,j}=0$ forces $z_{i,j} = -T X_i^T+T X_j^T$.
