Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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,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}& 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
Any ideas to help?? – john Jul 6 '12 at 19:32

Your Answer


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

Browse other questions tagged or ask your own question.