Paul Rubin ask in the comments of his blog post how to exploit a Farkas certificate Dantzig-Wolfe decomposition. I will answer that question here since it is very simple and not well-known. It is also fun to answer.
So let us assume you do
min c_1' x_1 + c_2' x_2
st. A_1 x_1 + A_2 x_2 = b
B_1 x_1 = f_1 (P)
B_2 x_2 = f_2
x_1, x_2 >= 0
In DW the master problem looks like
min h_1' z_1 + h_2' z_2
st H_1 z_1 + H_2 z_2 = b [y]
e' z_1 = 1 [u_1]
e' z_2 = 1 [u_2]
z_1, z_2 >= 0
e is the vector of all ones. y, u_1 and u_2 are dual variables associated with the constraints.
So it DW you have master problem and I will *NOT* assume that it is feasible. On other hand I will assume
it is infeasible and the LP optimizer provides a Farkas certificate of infeasibility denoted y, u_1 and u_2 i.e.
b'y + u_1 + u_2 > 0,
H_1'y + e u_1 <=0,
H_2'y + e u_2 <= 0
So if you do DW you will have to add columns to the master problem that invalids infeasibility certificate of the master problem.. Finding such column you do using the sub problems
min (0-A_j^T y)' x_j - u_j
st. B_j x_j =f_j
x_j >= 0
An interpretation of the subproblem is that we find a new column to the master problem that invalidates the Fakas certificate to the master problem as much as possible.
Now it is easy to verify that
- Assume the objective value to a sub problem is negative, then the optimal solution can be used to generate a new (useful) column to the master problem.
- Now if all the objective values to the problem are nonnegative then the problem (P) is infeasible. Hint: Can you specify a Farkas certificate to (P)?
