Efficient Feasibility Checking of SBBD Matrices
I have a collection of singly-bordered-block-diagonal matrices. That is, each SBBD matrix looks like:
H = [H_0 ... C_0;
H_1 ... C_1;
H_2 ... C_2;
.... ]
The number of blocks is constant for my collection. On the order of ~10 blocks. Another very relevant note: the collection arises from letting each pair (H_i, C_i) vary over some finite set of options. I want to consider all variations/combinations of variations.
For each SBBD matrix, H, I'd like to solve the feasibility problem Hx>0 for x a real vector. This is trivial to do using standard LP methods, but such methods are too slow (~0.1s per problem) for my context. Specifically, a given collection of problems might have size ~10^6 different problems. (In the worst case, it is of order 10^400, but I'm not bold/naive enough to expect to be able to solve 10^400 problems...)
I believe a good strategy is to use Bender's decomposition, for which I treat the block-diagonal part of H as the 'master problem', and the band as the 'subproblem'. By framing it in this context, I hope to be able to frontload some work (solving H_i x>0 for each i), and use that as a good starting point for each problem in my collection.
My questions:
1) is the proposed approach a good one, or should I pursue a different approach?
2) how might I implement this in GurobiPy? I know there are some posts (https://support.gurobi.com/hc/en-us/community/posts/13653393586961-Benders-decomposition-example-in-Python, https://support.gurobi.com/hc/en-us/community/posts/4415191730321-Benders-Decomposition-using-Callback, and https://support.gurobi.com/hc/en-us/community/posts/6482463141393-Benders-decomposition-in-Gurobi) discussing this, but they don't seem very relevant to my work.
This area is not my expertise, so I apologize if this question is confusing.
I would really love it if I could perform a (potentially large) upfront cost so that I can solve such problems at scale.
-
Official comment
This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
Post is closed for comments.
Comments
1 comment