# Removing a max function in the constraints

Can the following problem be transformed into a linear programming problem:

Find $x_1,..,x_N$ which maximizes the objective function

$$\sum_{i=1}^{N}x_{i}\sum_{j=1}^{n_{i}}c_{ij}$$

subject to the constraints

$$\sum_{i=1}^{N}\sum_{j=1}^{n_{i}}b_{ij}\max\left(x_{i}c_{ij}-p_{ij},0\right)+x_{i}f_{i}\sum_{j=1}^{n_{i}}c_{ij}\leq C$$

$$x_{i}\geq0$$ where $c_{ij}$, $b_{ij}$, $n_i$, $f_i$ and $C$ are known.

Is there a way to remove the max function from the constraints, perhaps by adding additional linear constraints? If not what would be the a good approach to solve this problem?

• Have you tried adding a variable $y_{ij}$ which is bigger than both $x_ic_{ij}-p_{ij}$ and $0$? It should work if $b_{ij}$ are positive. – dtldarek Dec 15 '14 at 10:45
• @dtldarek $b_{ij}$ are positive, could you elaborate on your idea? Infact $c_{ij}$ and $p_{ij}$ and $f_{i}$ are all positive. Do you mean I should add another variable to the solve for? What will the objective function become? – mark Dec 15 '14 at 11:13

If you don't mind adding $\sum_i n_i$ new variables (and assuming $b$'s are non-negative), then you could introduce $y_{ij}$ such that \begin{align} y_{ij} &\geq x_ic_{ij}-p_{ij}\\ y_{ij} &\geq 0 \end{align}

And then modify the constraints for $x$'s subtituting $y$'s: \begin{align} \sum_{i=1}^{N}\sum_{j=1}^{n_{i}}b_{ij}y_{ij}+x_{i}f_{i}\sum_{j=1}^{n_{i}}c_{ij}&\leq C \tag{$\spadesuit$}\\ x_i &\geq 0 \end{align}

The objective function stays the same as before, that is, $$\sum_{i=1}^{N}x_{i}\sum_{j=1}^{n_{i}}c_{ij}.$$

Why does it work? Any solution for your original onstraints will have some $y$'s that make it work (i.e. equal to the maximum from previous constraints). On the other hand, assuming that $b$'s are positive, any solution with new constraints can be modified to obtain old constraints without invalidating it (if some $y_{ij}$ is not equal to the max from previous constraints, it could only be bigger; we can decrease it and the inequality $\spadesuit$ will still be satisfied because $b_{ij}$ was positive). Hence optimum calculated with new constraints won't be better nor worse than optimum for old constraints.

I hope this helps $\ddot\smile$

• Do you mind writing down the new objective function. Is it simply $\sum_{i=1}^{N}x_{i}\sum_{j=1}^{n_{i}}c_{ij}+\sum_{i=1}^{N}\sum_{j=1}^{n_{i}}y_{ij}$? that is literally adding a load of dummy variables on the end of the objective function? – mark Dec 15 '14 at 11:34
• @aukie No, the objective function stays unmodified. – dtldarek Dec 15 '14 at 11:37
• So I make up some arbitrary numbers $y_{ij}$ feed the problem into a solver and modify the solution afterwards? But how would I go about choosing these numbers? – mark Dec 15 '14 at 11:54
• @aukie These are not constants like $b$'s, $c$'s and so on. These are the unknowns you solve for, like $x$'es. – dtldarek Dec 15 '14 at 12:55
• so now I'm solving for the x's and y's. I didn't even know you could do that. Have some background reading to do. I was under the impression all variables to solve for appear in the objective function. Thanks :) – mark Dec 15 '14 at 13:14