Add Dantzig-Wolfe Decomposition to HiGHS Solver for Improved Performance and Flexibility

[DavidPSterling]

I would like to propose the inclusion of the Dantzig-Wolfe (DW) decomposition algorithm into the HiGHS solver. The Dantzig-Wolfe decomposition is a classical column generation method that can be extremely beneficial for solving large-scale linear programming (LP) problems with a specific structure, particularly those with a block-angular structure. Several well-known solvers, such as CPLEX and Gurobi, already support Dantzig-Wolfe decomposition.

There are several reasons why incorporating Dantzig-Wolfe decomposition would be advantageous for the HiGHS solver:

1. Efficiency: Dantzig-Wolfe decomposition can significantly improve the performance of solving large-scale LP problems by exploiting their specific structure. By decomposing the problem into smaller subproblems and iteratively generating columns, the algorithm can potentially find optimal solutions faster than other methods, especially when dealing with large-scale, structured problems.

2. Flexibility: Dantzig-Wolfe decomposition is a versatile method that can be applied to a variety of problem types, such as transportation, logistics, and network design problems, among others. The flexibility of the method would extend the range of problems that the HiGHS solver can tackle efficiently.

3. Compatibility: As the HiGHS solver is designed to be a high-performance LP solver, adding the Dantzig-Wolfe decomposition method would be a natural extension of its existing capabilities. The implementation can be made compatible with the existing solver infrastructure and work in conjunction with other algorithms, such as simplex and interior-point methods.

---

Adding the Dantzig-Wolfe decomposition algorithm to the HiGHS solver would provide significant performance improvements for specific problem types and improve flexibility. I believe that incorporating this technique is crucial for maintaining HiGHS's position as a state-of-the-art LP solver.

Another open source solver project, SCIP employs DW decomp in their extension module GCG, which is a great module that helped me solve in seconds problems that would take several minutes in HiGHS. GCG requires SCIP to compile, but you can find the GCG source code here

There's also dwsolver, which adds DW support to GLPK, but it's been written 10 years ago so it's pretty outdated. The author is @nasajoey. All the C source files related to DW are in the src/ folder prefixed with dw, so it shouldn't be hard to integrate that into HiGHS for someone who has a good understanding of the HiGHS API (I don't).

[jajhall]

I can see the appeal, particularly since you have an instance where DW is effective. As you suggest, and thinking it through myself, it shouldn't be hard to implement in C++. That said, there are no resources in the HiGHS team to do all the work. The only hope I can see is if someone external were to write it. This would have to be in collaboration with me, since it would need some new data members of the Highs class, and general project oversight.

[jajhall]

Another thought is to propose it as an MSc project for this summer

[DavidPSterling]

@jajhall I'm willing to offer a bounty to get this done. 1000 USD, paid in Bitcoin.

[mathgeekcoder]

I've been thinking about adding something like GCG to HiGHS for my own research project this summer.

I can see that the basic idea for implementation is straightforward, but it can get complicated really quick, especially if we want to include the branch-and-price parts and nested/recursive decomposition support. Also, due to slightly different licensing, I don't think we can simply integrate their code into HiGHS.

I'm not particularly interested in the bitcoin, so if @jajhall is interested to collaborate with me - he's welcome to all of it.