Take the tour ×

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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

I did not find a satisfying solution for this, so I will just re-iterate what I found: Using CPlex, the problem scales somewhat better. Sadly, it does not seem possible to tell CPlex that you have a feasible solution, only that you have a (claimed to be) optimal solution, which wastes effort.

share|improve this answer
add comment

Your Answer


