Considering row as a knapsack
minimize $$c^Tx$$ st $$a^Tx <= W; l <= x <= u$$
NB minimize
If $$c_j/a_j >= 0$$, then dual fixing means that $$x_j$$ can probably
be fixed
If $$a_j > 0$$, then $$x_j$$ is contributing positively to the knapsack, but if $$c_j >=0$$ its optimal value would appear to be $$l_j$$, and it must be if $$c_j > 0$$, in which case $$l_j = -inf$$ implies dual infeasibility.
However, if $$c_j = 0$$ and $$l_j = -inf$$, then it is not logically correct to fix it to its lower bound and claim dual infeasibility. The row is redundant since, whatever values are assigned to the other variables, $$x_j$$ can be made sufficiently negative so that $$a^Tx <= W$$.
If $$l_j$$ is finite, then it is fair to fix $$x_j = l_j$$
If $$a_j < 0$$ then then $$x_j$$ is contributing negatively to the knapsack, and if $$c_j < 0$$ its optimal value is $$u_j$$, in which case $$u_j = inf$$ implies dual infeasibility. If $$c_j = 0$$ then, as above, if $$u_j$$ is finite fix $$x_j = u_j$$, otherwise the row is redundant.
If $$c_j/a_j < 0$$, then $$x_j$$ is a candidate to have its value assigned optimally. This is done greedily according to the sorted values of $$c_j/a_j$$, over all such candidates
Perhaps the $$c_j = 0$$ issue is moot, since fixing to an infinte bound leads to at least one of sumLowerFinite and sumUpperFinite being false, so set of candidates is abandoned.
Question: The greedy algorithm is only guaranteed to assign values optimally if the variables are continuous. The criterion minWeight != maxWeight (ie not all $$|a_j|$$ values being equal) leading to abandonment of stuffing if there are only integer columns overcomes this. However, is it guaranteed that with those continuous decisions the knapsack is solved optimally?
Question: Is there value in solving the knapsack problem by DP if all variables are integer, and not all $$|a_j|$$ values are equal?
Considering row as a knapsack
minimize$$c^Tx$$ st $$a^Tx <= W; l <= x <= u$$
NB minimize
If$$c_j/a_j >= 0$$ , then dual fixing means that $$x_j$$ can probably
be fixed
If$$a_j > 0$$ , then $$x_j$$ is contributing positively to the knapsack, but if $$c_j >=0$$ its optimal value would appear to be $$l_j$$ , and it must be if $$c_j > 0$$ , in which case $$l_j = -inf$$ implies dual infeasibility.
However, if$$c_j = 0$$ and $$l_j = -inf$$ , then it is not logically correct to fix it to its lower bound and claim dual infeasibility. The row is redundant since, whatever values are assigned to the other variables, $$x_j$$ can be made sufficiently negative so that $$a^Tx <= W$$ .
If$$l_j$$ is finite, then it is fair to fix $$x_j = l_j$$
If$$a_j < 0$$ then then $$x_j$$ is contributing negatively to the knapsack, and if $$c_j < 0$$ its optimal value is $$u_j$$ , in which case $$u_j = inf$$ implies dual infeasibility. If $$c_j = 0$$ then, as above, if $$u_j$$ is finite fix $$x_j = u_j$$ , otherwise the row is redundant.
If$$c_j/a_j < 0$$ , then $$x_j$$ is a candidate to have its value assigned optimally. This is done greedily according to the sorted values of $$c_j/a_j$$ , over all such candidates
Perhaps the$$c_j = 0$$ issue is moot, since fixing to an infinte bound leads to at least one of
sumLowerFiniteandsumUpperFinitebeing false, so set of candidates is abandoned.Question: The greedy algorithm is only guaranteed to assign values optimally if the variables are continuous. The criterion$$|a_j|$$ values being equal) leading to abandonment of stuffing if there are only integer columns overcomes this. However, is it guaranteed that with those continuous decisions the knapsack is solved optimally?
minWeight != maxWeight(ie not allQuestion: Is there value in solving the knapsack problem by DP if all variables are integer, and not all$$|a_j|$$ values are equal?