MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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.$$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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