I am working on a linear mixed-integer programming (MIP) optimization problem. Let's say the constraint can be denoted as $Ax\leq b$, where A is the constraint matrix.
Previously, A has a dimension roughly 1500 * 1500, and the COIN-OR CBC solver An open-source MIP solver only runs about 2 min to solve the problem. Now I need to add a new type constraint, which is only about 70 rows and yields A to be a 1570 * 1500 matrix. However, in this case, it runs about 5 hours to obtain a solution.
I understand that MIP is NP-hard and the complexity cannot simply be denoted in terms of number of constraints/variables. But this result is still surprising to me. Any suggestion? Use a commercial solver? Thanks.
Appendix: For those who are interested, the new type constraint I added is a rolling constraint to limit the number of starts per period. Here is a simple example: Suppose there are 3 kinds of appointments A, B and C, either of them can only start at 8:00, 8:30, or 9:00. The constraint is that within a 30min window ($\leq$30min), at most one appointment can start. The matrix A is like $$M= \left[ {\begin{array}{ccccccccc} 8:00 & 8:30 & 9:00 & 8:00 & 8:30 & 9:00 & 8:00 & 8:30 & 9:00\\ 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \end{array} } \right].$$ Variables are [# of A scheduled at 8:00, # of A scheduled at 8:30, # of A scheduled at 9:00, # of B scheduled at 8:00, ...]. Right hand side are [1,1] in this case.
It's really not surprising that adding even one constraint can make a problem much harder. Consider a problem with nonnegative variables where $(0,\ldots,0)$ is feasible and the objective (to be minimized) has positive coefficients. Then $(0,\ldots,0)$ is the unique optimal solution, and your MIP solver should find it almost instantly. But add the constraint $\sum_i x_i \ge 100$, and things are likely to become much more interesting.