How can we efficiently solve a large MILP with dense constraint matrix?

Question

Large MILPs with block structures can be efficiently solved with decomposition methods (e.g., the Benders' decomposition), which exploit special sparse structures of the constraint matrices.

However, when a large MILP has a dense constraint matrix, it could be hard to solve directly with solvers, while existing decomposition approaches usually do not work. An example of such problems is the security-constrained unit commitment problem (SCUC) with DC power flow, where variables are tightly linked together.

Is there any mature (or emerging) method dealing with dense constraint matrix in MILP solving?

Answer 1

Unfortunately, density kills optimization performance. Many of the implementational techniques used in solvers that allow for the efficient solution of large problems specifically exploit sparsity. The solver implementations typically try to have efficient methods for dense situations as well, but there are limits to that.

The only approach I know of that might help sometimes is reformulating the problem. This typically means coming up with an extended formulation, that means a formulation that uses more variables than the original one. This leads to a larger problem but potentially with a tighter bound and a better sparsity pattern, sometimes even one that can be exploited with decomposition.

A classic reformulation approach is to frame the problem in the context of a network, often a time-space-network where the nodes are duplicated for each time period. I am not familiar with the SCUC problem you mention, but a quick search hints at the fact that MILP solvers are currently used to solve this problem, so maybe a good formulation exists.

Alternatively, if a problem is large and dense and the performance is not satisfactory, solving only parts of the problem iteratively can be a good (heuristic) approach to at least find some solutions for such a problem.