# How to linearize (or convexify) a function that takes the maximum of binary variables?

I have the following optimization problem in binary variables $x_{ij}$ and $y_i$.

$$\begin{array}{ll} \text{minimize} & \displaystyle\sum_{i} y_i \max_j \big( c_{ij} x_{ij} \big)\\ \text{subject to} & \sum_{j}x_{ij}=1\\ & \sum_{i}y_i \leq 1\\ & y_i \geq x_{ij}\end{array}$$

where $c_{ij} \in \mathbb Z$ are given. Is it possible to linearize this objective? Or to make it convex?

• It might be helpful to post the whole program. In many cases the constraints helps to simplify the program. Aug 11, 2018 at 3:30
• Are you minimizing or maximizing the objective? Aug 11, 2018 at 9:26
• I am minimizing the objective. See the edits.
– zdm
Aug 11, 2018 at 12:55
• Binary here means $\{0,1\}$
– zdm
Aug 12, 2018 at 13:21
• Is $c_{ij} > 0$? Also, your constraints are infeasible unless there is only one $i$. For each $i$, the first constraint forces $x_{ij}=1$ for some $j$, and so the third constraint forces $y_i =$ for all $i$. Aug 19, 2019 at 19:32

Start by the rewriting the objective as $\sum y_i t_i$ subject to the constraints $\max_{j} x_{ij}c_{ij} \leq t_i$.
The max constraints are modelled using standard epi-graph reformations, i.e. $x_{ij}c_{ij} \leq t_i$. The binary times continuous $y_i t_i$ terms you can do using standard big-M models, by introducing a new variable $w_i$ satisfying $-M(1-y_i) \leq w_i - t_i \leq M(1-y_i), -My_i \leq w_i \leq My_i$. Using the structure in your constraints, you can probably simplify things considerably, this is the brute-force model.