Summation of maximization terms in CPLEX

Question

I have a problem in the following type:

$$\sum_{i∈I}{\max_{j∈J}c_{ij}\cdot x_{j}}$$

For each objective, in a set of $x$ variables, the goal is to select the one with the highest cost coefficient. After obtaining their objective values, we sum them up. Is there any simple way to write this in CPLEX? In minimax or maximax adding a dummy variable would be the way but it does not work in this case as we sum the objectives of multiple problems. However, defining $i$ many problems, solving them seperately and summing their values would be too time consuming. Is there any fast way to do this?

Answer 1

It sounds like you want to maximize $$\sum_i \sum_j c_{ij} x_{ij}$$ subject to \begin{align} \sum_j x_{ij} &=1 &&\text{for all $i$} \\ x_{ij} &\in\{0,1\} &&\text{for all $i$ and $j$} \end{align} The optimal objective value is clearly $\sum_i \max_j c_{ij}$, so you don’t really need to call a solver. If you need to set $x_{ij}=1$ for exactly one largest $c_{ij}$ for each $i$, you can do that with a simple loop over $j$ for each $i$, again without calling a solver. If you insist on calling a solver and don’t want to decompose by $i$, just solve the one big problem directly. There is no need to introduce auxiliary variables or big-M constraints.

Answer 2

Wouldn't know exactly in CPLEX but referring to this answer one way is to define $\theta_i$ and binary variables $z \in \{0,1\}^{I\times J}$as

$ c_{ij}x_j \le \theta_i \le c_{ij}x_ j + M(1-z_{ij}) \ \ \forall j \ \ \forall i$
$ \sum_j z_{ij} = 1 \ \ \forall i$

Then sum up $\sum_i \theta_i$

If $x_j$ is already binary and to be used to indicate the max coefficient then referring to 2nd answer here
Define $\theta_i$ as
$c_{ij}\le \theta_i \le c_{ij} + M(1-x_{ij})\ \ \forall j$
$\sum_j x_{ij}=1 \ \ \forall i $
Then sum up $\sum_i \theta_i$

Answer 3

We can use the following identity:

$$\sum_{i \in I}{\max_{j \in J}c_{ij}\cdot x_{j}} = \max_{j_1,\dots,j_{|I|} \in J} \sum_{i \in I} c_{i j_i} \cdot x_{j_i} = \max_{j_1,\dots,j_{|I|} \in J} c_{1 j_1} x_{j_1} + \dots + c_{k j_{|I|}} x_{j_{|I|}}$$

One way to encode this as integer linear programming is to express each $j_i$ as a one-hot vector, e.g., $j_i=1$ corresponds to $(1,0,0,\dots,0)$, $j_i=2$ corresponds to $(0,1,0,\dots,0)$, etc. If we expand that out, we build a matrix $M$ with $|I|$ columns and $|J|$ rows, where $M_{uv}=1$ iff $j_u=v$. Then the objective function becomes

$$\max_M \sum_{u,v} M_{uv} c_{uv} x_v,$$

where the maximization is taken over all zero-or-one matrices $M$ such that $\sum_v M_{uv}=1$ for all $u$.