# sum of maxima vs the maximum of the sum

Consider the following integer program \begin{align} \max &\sum\nolimits_{i}\sum\nolimits_{j} U_i(j)\cdot x_{i,j}\\ \text{subject to}& \sum_{i}x_{i,j}\cdot f\left(i,j\right)\leqslant c_j,& &\forall\, j\\ & x_{i,j}\in\{0,1\}. \end{align} and the following set $\Gamma$ of integer programs ($i$ is fixed below): \begin{align} \max &\sum\nolimits_{j} U_i(j)\cdot x_{i,j}\\ \text{subject to}& \sum_{i}x_{i,j}\cdot f\left(i,j\right)\leqslant c_j,& &\forall\, j\\ & x_{i,j}\in\{0,1\}. \end{align} and this is done $\forall \,i$. I want to have the same results from both optimization problems(i.e. same $x_{i,j}$ from the first optimization problem and the second set and $\sum\nolimits_{i}\max\sum\nolimits_{j} U_i(j)\cdot x_{i,j}=\max\sum\nolimits_{i,j} U_i(j)\cdot x_{i,j})$

The problem is that the constraints are coupled as we can see. Consequently, the order in which the problems in $\Gamma$ are solved changes the answer. For example if we start with $i=1$ and do the maximization, we will find $x_{i,j}\, \forall j$. We can then set $c_j$ to $c_j-x_{i,j}\cdot f(i,j)$ and solve for the next $i$. But the order in which we choose the $i$'s is important. Intuitively, I am guessing that there should be an optimal order that leads to the same result. But, how can I find the optimal order? Does this problem has a well known name?

-
Sorry is the question unclear and that's why no one is answering? Or is it too simple? Or is it that many people are unfamiliar with this topic? –  john Jul 9 '12 at 20:20
Your question has gotten over 100 views at this writing; it is liikely that over 50 MathOverflow denizens have read it. Some subjects do not attract much interest, and your question may be one of them. You can try editing it once a day to improve its appeal and bring it to the fore, but please make only serious content changing edits. Providing a more specific example of the type of problem might generate more interest. Gerhard "Ask Me About System Design" Paseman, 2012.07.10 –  Gerhard Paseman Jul 10 '12 at 18:31

In some cases there exists no ordering of $\Gamma$ such that solving the problems in $\Gamma$ sequentially gives the optimal value of the original problem.

Here is a simple counterexample. Let $i,j$ range from 1 to 2 and set $c_j=1, f(i,j)=1$ for all $i,j$. Take $U_{i,j}=1$ for $i=j$ and $U_{i,j}=2$ for $i\ne j$. Then the original problem is solved by taking $x_{1,1}=x_{2,2}=0$ and $x_{1,2}=x_{2,1}=1$, giving an objective function value of 4. But solving $\Gamma$ in either order leads to an objective function value of 3.

Let's go through it step by step.

The problem is $$\max x_{11} + x_{22} + 2x_{12} + 2x_{21}$$ subject to $$x_{11}+x_{21}\le 1$$ $$x_{12}+x_{22}\le 1$$

For the other two problems, we have

$$\max x_{11} + 2x_{12}$$ subject to $$x_{11}+x_{21}\le 1$$ $$x_{12}+x_{22}\le 1$$ which leads to $x_{12}=1$ AND $x_{11}=1$, in order to achieve a maximum value of 3. Notice that the solution to this problem in the comment below is not correct.

Then the second problem becomes $$\max 2x_{21} + x_{22}$$ subject to $$x_{21}\le 0$$ $$x_{22}\le 0.$$

-
Thanks for your answer. But I have to disagree. The original problem can be formulated as follows: \begin{align} \max & x_{1,1}+2x_{1,2}+2x_{2,1}+x_{2,2}\\ subject to & x_{1,1}+x_{2,1}\leq 1\\ & x_{1,2}+x_{2,2}\leq 1 \end{align} which indeed leads to $x_{1,2}=x_{2,1}=1$. As for the other two problems, we have: \begin{align} \max & x_{1,1}+2x_{1,2}\\ subject to & x_{1,1}+x_{2,1}\leq 1\\ & x_{1,2}+x_{2,2}\leq 1 \end{align} which leads to $x_{1,2}=1$. –  john Jul 13 '12 at 16:34
Now set $c_{2}=0$, the second problem becomes: \begin{align} \max & 2x_{2,1}+x_{2,2}\\ \text{subject to} & x_{1,1}+x_{2,1}\leq 1\\ & x_{1,2}+x_{2,2}\leq 0 \end{align} Which leads to $x_{2,1}=1$. And the objective function is 4, same results as the first problem. Actually in this scenario the order in which you solve the problem is not important. –  john Jul 13 '12 at 16:36
@john, Your solution of this problem (in comments) is not correct. I have made it completely explicit for you now. –  David Ketcheson Jul 14 '12 at 7:16