Groupe d’études et de recherche en analyse des décisions


Improving ILP Solutions by Zooming Around an Improving Direction

, et

In this paper, we introduce a general framework for vector space decompositions that decompose the set partitioning problem into a reduced problem, defined in the vector subspace of columns corresponding to nonzero variables in the current integer solution, and a complementary problem, defined in the complementary vector subspace. We show that the integral simplex using decomposition algorithm (ISUD) developed in Zaghrouti, A., El Hallaoui, I., Soumis, F. (2014). uses a particular decomposition, in which integrality is handled mainly in the complementary problem, to find a decreasing sequence of integer solutions leading to an optimal solution. We introduce a new algorithm using a dynamic decomposition where integrality is handled only in the reduced problem, and the complementary problem is only used to provide descent directions, needed to update the decomposition. The new algorithm improves, at each iteration, the current integer solution by solving a very small reduced problem, that we define by zooming around the descent direction (provided by the complementary problem). This zooming algorithm significantly improves ISUD and works better on set partitioning instances from the transportation industry. It rapidly reaches optimal or near-optimal solutions for all instances including those considered very difficult for both ISUD and CPLEX.

, 25 pages

Ce cahier a été révisé en avril 2016