Unbounded subproblems for general decomposition problem with `dw`

[kibaekkim]

The Dantzig-Wolfe decomposition does not address unbounded subproblems and terminates with segfault for general decomposition problem instance.

Example is: https://github.com/Argonne-National-Laboratory/DSP/blob/41c3586948ef5c1653823d5d73f3c780eb4ad3b2/examples/cpp/farmer.cpp

[phumthep]

Has this issue been solved? I used the DW method to solve an MILP and the algorithm does not seem to converge after 68 iterations (kept running for 10 hours+). The DW bound did not decrease.

[kibaekkim]

@phumthep Not sure.. I have to revisit this again.. Is your comment related to #253 ?

[hideakiv]

Example is: https://github.com/Argonne-National-Laboratory/DSP/blob/41c3586948ef5c1653823d5d73f3c780eb4ad3b2/examples/cpp/farmer.cpp

The subproblem model appears to be defined improperly https://github.com/Argonne-National-Laboratory/DSP/blob/41c3586948ef5c1653823d5d73f3c780eb4ad3b2/examples/cpp/farmer.cpp#L151

[hideakiv]

When some subproblem is dual infeasible, DSP tries to use an extreme ray. However, getPrimalRays is not implemented in most solvers in Osi (except for Cplex as far as I checked).

https://github.com/Argonne-National-Laboratory/DSP/blob/41c3586948ef5c1653823d5d73f3c780eb4ad3b2/src/Solver/DantzigWolfe/DwWorker.cpp#L276

If getPrimalRays is implemented, a bundle cut may be generated by using the extreme ray of the dual infeasible subproblem. Otherwise, we would better return a message and terminate DSP gracefully.

[hideakiv]

If getPrimalRays is implemented, a bundle cut may be generated by using the extreme ray of the dual infeasible subproblem.

However, when some subproblems are primal/dual infeasible, the generated columns are not added to the master.

https://github.com/Argonne-National-Laboratory/DSP/blob/41c3586948ef5c1653823d5d73f3c780eb4ad3b2/src/Solver/DantzigWolfe/DwMaster.cpp#L788-L847

DwBundleDual needs to handle the case that no cut is added because all the generated cuts are from dual infeasible subproblems. This can possibly cause the master problem to be unbounded due to the bounds defined below, when all generated cuts are from dual infeasible solutions.

https://github.com/Argonne-National-Laboratory/DSP/blob/41c3586948ef5c1653823d5d73f3c780eb4ad3b2/src/Solver/DantzigWolfe/DwBundleDual.cpp#L240-L242

[hideakiv]

Similarly, when all generated cuts are from dual infeasible solutions, the primal form of the master problem becomes infeasible due to the following row bounds (0=1). https://github.com/Argonne-National-Laboratory/DSP/blob/41c3586948ef5c1653823d5d73f3c780eb4ad3b2/src/Solver/DantzigWolfe/DwBundleDual.cpp#L167-L168

[hideakiv]

For the dual form of the master problem, I set the column bounds to be zero.

std::fill(clbd.begin(), clbd.begin() + nrows_conv_, 0.0); 
std::fill(cubd.begin(), cubd.begin() + nrows_conv_, 0.0); 

and modified it to COIN_DBL_MAX and -COIN_DBL_MAX when dual feasible subproblem solution is discovered.

Similarly, for the primal form of the master problem, I set the row bounds to be zero.

 std::fill(rlbd.begin(), rlbd.begin() + nrows_conv_, 0.0); 
 std::fill(rubd.begin(), rubd.begin() + nrows_conv_, 0.0); 

and modified it to 1 when dual feasible subproblem solution is discovered.

[hideakiv]

I am now getting optimal status for the master problem. However, in the second round of solving the subproblem, I got optimal status for one problem but the solution is extremely large, and gets stuck at the assertion below. https://github.com/Argonne-National-Laboratory/DSP/blob/41c3586948ef5c1653823d5d73f3c780eb4ad3b2/src/Solver/DantzigWolfe/DwWorker.cpp#L320