sum of maxima vs the maximum of the sum

Question

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?

Answer 1

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.$$