# Efficiently solving a special integer linear programming with simple structure and known feasible solution

Consider an ILP of the following form: Minimize $\sum_{k=1}^N s_i$ where $\sum_{k=i}^j s_i \ge c_1 (j-i) + c_2 - \sum_{k=i}^j a_i$ for given constants $c_1, c_2 > 0$ and a given sequence of non-zero natural numbers $a_i$, for all $1 \le i \le j \le N$, and the $s_i$ are non-zero natural numbers.

Using glpk, it was no problem to solve this system in little time for $N=100$, with various parameters values. Sadly, due to the huge numbers of constraints, this does not scale well to larger values of $N$ - glpk takes forever in trying to find a feasible solution for the relaxed problem.

I know that every instance of this problem has a (non-optimal) feasible solution, e.g., $s_i = \max \{ 1, 2r - a_i \}$ for a certain constant $r$, and the matrix belonging to the system is totally unimodular. How can I make use of this information to speed up calculations? Would using a different tool help me?

Edit: I tried using CPlex instead. The program runs much faster now, but the scalability issues remain. Nevertheless, I can now handle the problem I want to address. It may be interesting to note that while it is possible to provide a feasible but non-optimal solution to CPlex (see the setVectors function in the Concert interface), this makes CPlex assume that the given solution is optimal (which is not neccesarily the case) and hence give wrong results.

It would still be interesting to know if there is a better solution that does not involve throwing more hardware at the problem.

-