5
votes
Must the Newly Generated Column be used in RMP in the Column Generation Method?
I assume that you are minimizing. If you only add one column at a time, the new column should immediately enter the basis. If you add multiple columns with negative reduced costs before doing more ...
- 37.9k
4
votes
Accepted
Can one strengthen the Lagrangian dual bound in column generation when there are multiple subproblems?
Yes, that bound is valid, and you can prove it by exhibiting a dual feasible solution with that objective value. I don’t have my copy handy, but Wolsey’s Integer Programming shows this. In fact, the ...
- 30.5k
2
votes
Accepted
Reduced cost fixing for binary programs
Assume you want to solve
$$
\begin{array}{ll}
min & c^T x \\
st & A x = b \\
& x \geq 0
\end{array}
$$
For any dual feasible solution $(\hat y,\hat s)$ it holds
$$
\hat s = c - A^T \...
- 3,046
1
vote
Accepted
The dual values and change in the variables values
Let $\bar{A}$ and $\bar{x}$ be $A$ and $x$ augmented by slack variables, so that the constraints become $\bar{A} \bar{x} = b.$ The LP solution partitions $\bar{A} = [B N]$ (after permuting columns if ...
- 37.9k
1
vote
Accepted
Understanding reduced costs and dual values
One of the best possible ways for the models with some difficulties to understand how the model can be treating in the solving process, specifically in the situations like infeasibility, comparing ...
- 8,450
Only top scored, non community-wiki answers of a minimum length are eligible