6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ thanks a lot, is there a way to decide how high i can set M^1 and M^2? $\endgroup$ – T K. Jan 29 at 8:55
  • $\begingroup$ You should set those big-M values as small as possible, based on $T$ and bounds on $X$, without cutting off useful solutions. Do you have bounds on $X$? $\endgroup$ – RobPratt Jan 29 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.