I have implemented a set of "or" constraints in my ILP using binary decision variables (as in this method). It works fine for smaller problems, but when I try to increase the number of variables it gets very slow very fast, such that it is not feasible for the size of problem I need to solve. Is there a way to more cleverly implement this method, so that I can get a solution in hours instead of months?
Without the “or” constraint, the solution is found in a matter of seconds, even for a problem twice the size that I need, so it’s not just a matter of the number of variables (because the decision variables make the simplex no longer convex). I have assigned the big constant to be as small as possible while still satisfying the constraints, but I am not sure what else I can do. All my variables are binary, I am using a GLPK solver from R (Rglpk), running on a professional-grade laptop. I can successfully solve the problem for $1,000$ variables in a couple seconds, while $10,000$ takes a couple hours. My application calls for a maximum of $1,000,000$ variables.
Thanks for your advice.
EDITED to add information about the model:
My variables are the entries of a binary matching matrix $B$, weighted by a similarity matrix $S$, the constraints are just row sums and column sums:
Objective:
$$\max_{B} \sum_{i,j} S_{i,j} B_{i,j}$$
Constraints:
- $B_{i,j}$ binary
- $\forall i, \sum_j B_{i,j} = a$
- $\forall j, \sum_i B_{i,j} \le b$
- $\forall j, \sum_i B_{i,j} \ge c$ or $\sum_i B_{i,j} \le 0$