0
$\begingroup$

Let $I$ be a finite set, and $A_{ij},B_{ij},x_i,y_j\ge0$. I want to find the choice of $x_i,y_j$ maximizing $$\sum_{i\in I}\sum_{j\in J}A_{ij}\min\left(x_i,B_{ij}y_j\right)\tag1$$ subject to $$\sum_{i\in I}x_i=\sum_{j\in I}y_j=1\tag2.$$ As discussed on Mathematics, the feasible region is divided into polygons such that the objective function is linear on each interval. With this approach we end with a finite number of candidate points (the vertices) we need to compute the maximum of.

However, I need to find a closed form expression for $x_i,y_j$. Are we able to achieve this? If not, are we at least able to find a (sharp) lower bound for $(1)$ for which it is easier to obtain a closed form maximizer?

Improve this question
$\endgroup$
8
  • $\begingroup$ Standard trick is to introduce variables $z_{ij}$ with $z_{ij}\leq x_i$ and $z_{ij}\leq B_{ij}y_j$, and to maximize:$$\sum_{i\in I}\sum_{j\in J}A_{ij}z_{ij}.$$ $\endgroup$
    – Max Alekseyev
    Sep 6, 2019 at 11:33
  • $\begingroup$ @MaxAlekseyev Thank you for your comment. I guess we're enforcing $z_{ij}\ge0$, right? It's been a while since I thought about linear optimization, but I need to implement a solver (with as less overhead as possible) for the problem. Do you have a good reference at hand? (I guess there's no hope for a closed form solution, right?) $\endgroup$
    – 0xbadf00d
    Sep 6, 2019 at 12:45
  • $\begingroup$ @MaxAlekseyev Oh, and while I see the formal point in bringing the problem into some kind of "normal" or "standard" form by introducing $z_{ij}$, this should produce a significant overhead. Is there a more direct approach for the special shape of the problem? $\endgroup$
    – 0xbadf00d
    Sep 6, 2019 at 14:17
  • 1
    $\begingroup$ Since $A_{ij}\geq 0$, you don't need to enforce $z_{ij}\geq 0$. $\endgroup$
    – Max Alekseyev
    Sep 6, 2019 at 14:19
  • $\begingroup$ @MaxAlekseyev Would be great if you could (briefly) elaborate on the other questions in my comments. $\endgroup$
    – 0xbadf00d
    Sep 8, 2019 at 19:01

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.