Faster implementation of "or" constraints in ILP

Question

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:

1. $B_{i,j}$ binary
2. $\forall i, \sum_j B_{i,j} = a$
3. $\forall j, \sum_i B_{i,j} \le b$
4. $\forall j, \sum_i B_{i,j} \ge c$ or $\sum_i B_{i,j} \le 0$

Answer 1

Answers to the linked question mention both big-M constraints and semicontinuous variables. To speed up the big-M approach, you might consider introducing the constraints dynamically only as they are violated ("row generation" or "cut generation"). Explicitly:

1. Omit all big-M constraints and the associated binary variables.
2. Solve the problem with the current set of big-M constraints and associated binary variables.
3. For any violations (variables $x_i$ with $0 < x_i < c$), introduce big-M constraints and the associated binary variables.
4. If there are no violations, stop. Else go to step 2.

Depending on the rest of your model, there might be additional ways to improve the solve time.

Answer 2

GLPK is not the best performing MILP solver. Instead, you could give one of the leading commercial MILP solvers a try (e.g. Gurobi). You can also try open-source solvers like SCIP a try. Those solvers should be faster out of the box.

You can quickly evaluate different solvers with your model by writing it out as .MPS file. Every MILP solver I know of can read these files.

Some solvers, like Gurobi, have special APIs to formulate OR constraints and indicator constraints. By using these APIs you can sidestep finding a suitable Big-M yourself and let the solver find appropriate values (which may even tightened during the solving process).

Still, a million variables is probably challenging for these solvers as well.

Answer 3

{0,1}-ILP can be rewritten as Pseudo-Boolean programming or MAX-Sat. It might be worth to explore alternative solving technologies for your problem.