1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – dtldarek Dec 15 '14 at 10:45
  • $\begingroup$ @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? $\endgroup$ – mark Dec 15 '14 at 11:13
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – mark Dec 15 '14 at 11:34
  • $\begingroup$ @aukie No, the objective function stays unmodified. $\endgroup$ – dtldarek Dec 15 '14 at 11:37
  • $\begingroup$ 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? $\endgroup$ – mark Dec 15 '14 at 11:54
  • $\begingroup$ @aukie These are not constants like $b$'s, $c$'s and so on. These are the unknowns you solve for, like $x$'es. $\endgroup$ – dtldarek Dec 15 '14 at 12:55
  • $\begingroup$ 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 :) $\endgroup$ – mark Dec 15 '14 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.