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?

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.