Linear programming with min of max function

I have to write the linear program which minimizes this function :

$$y = \max_j \sum_{i=1}^{n}c_{ij}x_{ij}$$

My book says that this is not a linear function but it can be trasformed into one using the minimizing program $\min y$ with the conditions :

$$ \sum_{i=1}^{n}c_{ij}x_{ij} \leq y \:\:, \:\:j = 1,...,m$$

(+ other conditions not related with $y$)

I really don't get why when these conditions are met then I should consider it a linear program, $y$ isn't neither a linear function nor a constant as far as I understand. Besides, I don't get neither how to calculate the maximum, can $y$ be traslated as :

$$\max (\sum_{i=1}^{n}c_{ij}x_{ij} \:\:, \:\:j = 1,...,m) $$

But, then I have a function with different variables, so how can I find a maximum, maybe considering the other restrictions ?

Maybe, I'm misunderstanding everything , I'm new to linear programming

Solution 1:

The $y$ in the linear program is being treated as a totally new variable that doesn't (directly) keep its old meaning as $\max_j \sum_i c_{ij} x_{ij}$. I suspect the reason for your confusion is that you're continuing to try to expand $y$ out to its old definition inside the linear program.

The point is that by adding a constraint that $\sum c_{ij} x_{ij} \leq y$ for each $j$, the linear program requires that the value assigned to the variable $y$ is at least $\max_j \sum_i c_{ij} x_{ij}$, so any optimal solution of the linear program, having made the variable $y$ as small as possible, must in fact make $y$ equal to $\max_j \sum_i c_{ij}x_{ij}$. (The constraints only force that $y$ is at least this max, but clearly there's no reason to have $y$ any larger than the max if there are no other constraints involving $y$, so an optimal solution makes it equal.)